Skip to content

No foldMap in Vector.Unboxed or Vector.Primitive #263

Closed

Description

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

Activity

  1. cartazio commented on Dec 18, 2019

    @cartazio
    Contributor
  2. cartazio commented on Jan 7, 2020

    @cartazio
    Contributor

    @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

  3. cartazio commented on Jan 31, 2020

    @cartazio
    Contributor

    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

  4. added this to the 0.13 milestone on Jun 11, 2020
  5. Shimuuar commented on Jun 13, 2020

    @Shimuuar
    Contributor

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

  6. Bodigrim commented on Jun 13, 2020

    @Bodigrim
    Contributor

    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)
  7. Shimuuar commented on Jun 14, 2020

    @Shimuuar
    Contributor

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

  8. merijn commented on Jun 14, 2020

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

  9. Bodigrim commented on Jun 14, 2020

    @Bodigrim
    Contributor

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions