You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
No foldMap in Vector.Unboxed or Vector.Primitive #263
Both Data.Vector.Primitive and Data.Vector.Unboxed do not have a foldMap function. There is no particularly compelling technical reason this doesn't exist. It has the following implementation for example:
Note that this is the default implementation in the Foldable typeclass. The main downside to adding this definition is that is adds a potential namespace clash but both of these modules are already drowning in such namespace clashes and so I don't see this as a serious objection.
Reacted by recursion-ninja, Emily Pillmore and sheaf
On Tue, Dec 17, 2019 at 4:08 PM Callan McGill ***@***.***> wrote:
Both Data.Vector.Primitive and Data.Vector.Unboxed do not have a foldMap
function. There is no particularly compelling technical reason this doesn't
exist. It has the following default implementation for example:
foldMap :: forall m a . (Unbox a, Monoid m) => (a -> m) -> Vector a -> m
{-# INLINE foldMap #-}
foldMap f = foldr (mappend . f) mempty
foldMap :: forall m a. (Prim a, Monoid m) => (a -> m) -> Vector a -> m
{-# INLINE foldMap #-}
foldMap f = foldr (mappend . f) mempty
Note that this is the default implementation in the Foldable typeclass.
The main downside to adding this definition is that is adds a potential
namespace clash but both of these modules are already drowning in such
namespace clashes and so I don't see this as a serious objection.
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<#263?email_source=notifications&email_token=AAABBQRMNMAH6F63JKTCWSDQZE5U5A5CNFSM4J4BR6Z2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4IBFHNCQ>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAABBQWO3VQFL7ZE6GDNUJDQZE5U5ANCNFSM4J4BR6ZQ>
.
one design direction suggested by @merijn this summer and I think makes sense in the next major release is have most vector boxed/unboxed/storable functions just be reexports from the .generics modules. I'm not sure if theres any good examples (outside of ghci usage, which doesn't get stream fusion), where the extra inline wrapper with a more specific type helps out in extant vector code
seems like this ties into a good suggestion by @merijn that all these definitions should just live in .Generic and have the concrete modules just reexport the generic api
foldMap::Monoidm=> (a->m) ->Vectora->mfoldMap f v =caseV.length v of0->mempty1-> f (V.head v)
l ->foldMap (V.take (l `div`2) v) <>foldMap (V.drop (l `div`2) v)
What would the tree fold accomplish? I discussed it with Carter some time, but we concluded that, in the absence of parallelism you end up doing the same number of operations.
2 elements: 1 operation for linear fold, 1 operation for tree fold
4 elements: 3 operations for linear fold, 3 operations for tree fold (first tree layer of 2 merges returns 2 new values, so another final merge for 3 total)
8 elements: 7 operations for linear fold, 7 operations for tree fold (first tree layer of 4 merges, giving 4 new values, 2 merges for those 4 new values, plus a final merge for a total of 7)
I don't think tree fold ever does less operations.
Activity
cartazio commentedon Dec 18, 2019
cartazio commentedon Jan 7, 2020
@Boarders thanks for this and the other tickets!j
one design direction suggested by @merijn this summer and I think makes sense in the next major release is have most vector boxed/unboxed/storable functions just be reexports from the .generics modules. I'm not sure if theres any good examples (outside of ghci usage, which doesn't get stream fusion), where the extra inline wrapper with a more specific type helps out in extant vector code
cartazio commentedon Jan 31, 2020
seems like this ties into a good suggestion by @merijn that all these definitions should just live in .Generic and have the concrete modules just reexport the generic api
Shimuuar commentedon Jun 13, 2020
I wonder whether we should define foldMap via left of right fold.
Bodigrim commentedon Jun 13, 2020
We can also define it as a tree fold:
Shimuuar commentedon Jun 14, 2020
Right question is which variant will play better with fusion. Tree fold will require to materialize complete vector
merijn commentedon Jun 14, 2020
What would the tree fold accomplish? I discussed it with Carter some time, but we concluded that, in the absence of parallelism you end up doing the same number of operations.
2 elements: 1 operation for linear fold, 1 operation for tree fold
4 elements: 3 operations for linear fold, 3 operations for tree fold (first tree layer of 2 merges returns 2 new values, so another final merge for 3 total)
8 elements: 7 operations for linear fold, 7 operations for tree fold (first tree layer of 4 merges, giving 4 new values, 2 merges for those 4 new values, plus a final merge for a total of 7)
I don't think tree fold ever does less operations.
Bodigrim commentedon Jun 14, 2020
Actually, let's mimic
Data.Foldableand definefoldMapviafoldrandfoldMap'viafoldl'.