No foldMap in Vector.Unboxed or Vector.Primitive

[Boarders]

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:

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.

[cartazio]

This is a good feature request. Thx for reporting it. Getting the apis all synchronized is definitely valuable.

…

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> .

[cartazio]

@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]

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]

I wonder whether we should define foldMap via left of right fold.

[Bodigrim]

We can also define it as a tree fold:

foldMap :: Monoid m => (a -> m) -> Vector a -> m 
foldMap f v = case V.length v of 
  0 -> mempty 
  1 -> f (V.head v)
  l -> foldMap (V.take (l `div` 2) v) <> foldMap (V.drop (l `div` 2) v)

[Shimuuar]

Right question is which variant will play better with fusion. Tree fold will require to materialize complete vector

[merijn]

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]

I wonder whether we should define foldMap via left of right fold.

Actually, let's mimic Data.Foldable and define foldMap via foldr and foldMap' via foldl'.