Add foldMapM to Data.Foldable

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Add foldMapM to Data.Foldable

Andrew Martin
Several coworkers and myself have independently reinvented this function several times:

    foldMapM :: (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a -> m b
    foldMapM f xs = foldlM (\b a -> mappend b <$> (f a)) mempty xs

I would like to propose that this be added to Data.Foldable. We have the triplet foldr,foldl,foldMap in the Foldable typeclass itself, and Data.Foldable provides foldrM and foldlM. It would be nice to provide foldMapM for symmetry and because it seems to be useful in a variety of applications.

--
-Andrew Thaddeus Martin

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add foldMapM to Data.Foldable

Andreas Abel
+1.

If I remember correctly, then Henning Thielemann has suggested this as
the proper generalization of mapM_.

On 06.12.2017 15:28, Andrew Martin wrote:

> Several coworkers and myself have independently reinvented this function
> several times:
>
>      foldMapM :: (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a -> m b
>      foldMapM f xs = foldlM (\b a -> mappend b <$> (f a)) mempty xs
>
> I would like to propose that this be added to Data.Foldable. We have the
> triplet foldr,foldl,foldMap in the Foldable typeclass itself, and
> Data.Foldable provides foldrM and foldlM. It would be nice to provide
> foldMapM for symmetry and because it seems to be useful in a variety of
> applications.
>
> --
> -Andrew Thaddeus Martin
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>


--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www.cse.chalmers.se/~abela/
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add foldMapM to Data.Foldable

David Feuer
In reply to this post by Andrew Martin
It seems this lazily-accumulating version should be Applicative, and a strict version Monad. Do we also need a right-to-left version of each?

On Dec 6, 2017 9:29 AM, "Andrew Martin" <[hidden email]> wrote:
Several coworkers and myself have independently reinvented this function several times:

    foldMapM :: (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a -> m b
    foldMapM f xs = foldlM (\b a -> mappend b <$> (f a)) mempty xs

I would like to propose that this be added to Data.Foldable. We have the triplet foldr,foldl,foldMap in the Foldable typeclass itself, and Data.Foldable provides foldrM and foldlM. It would be nice to provide foldMapM for symmetry and because it seems to be useful in a variety of applications.

--
-Andrew Thaddeus Martin

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add foldMapM to Data.Foldable

Andrew Martin
I had not considered that. I tried it out on a gist (https://gist.github.com/andrewthad/25d1d443ec54412ae96cea3f40411e45), and you're definitely right. I don't understand right monadic folds well enough to write those out, but it would probably be worthwhile to both variants of it as well. Here's the code from the gist:

{-# LANGUAGE ScopedTypeVariables #-}

module Folds where

import Control.Applicative

-- Lazy in the monoidal accumulator.
foldlMapM :: forall g b a m. (Foldable g, Monoid b, Applicative m) => (a -> m b) -> g a -> m b
foldlMapM f = foldr f' (pure mempty)
  where
  f' :: a -> m b -> m b
  f' x y = liftA2 mappend (f x) y

-- Strict in the monoidal accumulator. For monads strict
-- in the left argument of bind, this will run in constant
-- space.
foldlMapM' :: forall g b a m. (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a -> m b
foldlMapM' f xs = foldr f' pure xs mempty
  where
  f' :: a -> (b -> m b) -> b -> m b
  f' x k bl = do
    br <- f x
    let !b = mappend bl br
    k b


On Wed, Dec 6, 2017 at 6:11 PM, David Feuer <[hidden email]> wrote:
It seems this lazily-accumulating version should be Applicative, and a strict version Monad. Do we also need a right-to-left version of each?

On Dec 6, 2017 9:29 AM, "Andrew Martin" <[hidden email]> wrote:
Several coworkers and myself have independently reinvented this function several times:

    foldMapM :: (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a -> m b
    foldMapM f xs = foldlM (\b a -> mappend b <$> (f a)) mempty xs

I would like to propose that this be added to Data.Foldable. We have the triplet foldr,foldl,foldMap in the Foldable typeclass itself, and Data.Foldable provides foldrM and foldlM. It would be nice to provide foldMapM for symmetry and because it seems to be useful in a variety of applications.

--
-Andrew Thaddeus Martin

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries





--
-Andrew Thaddeus Martin

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add foldMapM to Data.Foldable

David Feuer
Actually, the most "natural" Applicative version is probably this:

newtype Ap f a = Ap {getAp :: f a}
instance (Applicative f, Monoid a) => Monoid (Ap f a) where
  mempty = Ap $ pure mempty
  mappend (Ap x) (Ap y) = Ap $ liftA2 mappend x y

foldMapA :: (Foldable t, Monoid m, Applicative f) => (a -> f m) -> t a -> f m
foldMapA f = getAp . foldMap (Ap . f)

Of course, we can use some Data.Coerce magic to avoid silly eta
expansion, as usual.

The "right" way to perform the actions in the opposite order is probably just

foldMapA f . Reverse

and you can accumulate the other way using getDual . foldMapA (Dual . f)

So I think the whole Applicative side of this proposal might be seen as further
motivation for my long-ago stalled proposal to add Ap to Data.Monoid.

On Wed, Dec 6, 2017 at 7:27 PM, Andrew Martin <[hidden email]> wrote:

> I had not considered that. I tried it out on a gist
> (https://gist.github.com/andrewthad/25d1d443ec54412ae96cea3f40411e45), and
> you're definitely right. I don't understand right monadic folds well enough
> to write those out, but it would probably be worthwhile to both variants of
> it as well. Here's the code from the gist:
>
> {-# LANGUAGE ScopedTypeVariables #-}
>
> module Folds where
>
> import Control.Applicative
>
> -- Lazy in the monoidal accumulator.
> foldlMapM :: forall g b a m. (Foldable g, Monoid b, Applicative m) => (a ->
> m b) -> g a -> m b
> foldlMapM f = foldr f' (pure mempty)
>   where
>   f' :: a -> m b -> m b
>   f' x y = liftA2 mappend (f x) y
>
> -- Strict in the monoidal accumulator. For monads strict
> -- in the left argument of bind, this will run in constant
> -- space.
> foldlMapM' :: forall g b a m. (Foldable g, Monoid b, Monad m) => (a -> m b)
> -> g a -> m b
> foldlMapM' f xs = foldr f' pure xs mempty
>   where
>   f' :: a -> (b -> m b) -> b -> m b
>   f' x k bl = do
>     br <- f x
>     let !b = mappend bl br
>     k b
>
>
> On Wed, Dec 6, 2017 at 6:11 PM, David Feuer <[hidden email]> wrote:
>>
>> It seems this lazily-accumulating version should be Applicative, and a
>> strict version Monad. Do we also need a right-to-left version of each?
>>
>> On Dec 6, 2017 9:29 AM, "Andrew Martin" <[hidden email]> wrote:
>>
>> Several coworkers and myself have independently reinvented this function
>> several times:
>>
>>     foldMapM :: (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a -> m
>> b
>>     foldMapM f xs = foldlM (\b a -> mappend b <$> (f a)) mempty xs
>>
>> I would like to propose that this be added to Data.Foldable. We have the
>> triplet foldr,foldl,foldMap in the Foldable typeclass itself, and
>> Data.Foldable provides foldrM and foldlM. It would be nice to provide
>> foldMapM for symmetry and because it seems to be useful in a variety of
>> applications.
>>
>> --
>> -Andrew Thaddeus Martin
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>>
>
>
>
> --
> -Andrew Thaddeus Martin
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add foldMapM to Data.Foldable

David Feuer
Actually, the key modifiers are probably Dual and Backwards, with Reverse combining them. Or something like that.

On Dec 6, 2017 8:20 PM, "David Feuer" <[hidden email]> wrote:
Actually, the most "natural" Applicative version is probably this:

newtype Ap f a = Ap {getAp :: f a}
instance (Applicative f, Monoid a) => Monoid (Ap f a) where
  mempty = Ap $ pure mempty
  mappend (Ap x) (Ap y) = Ap $ liftA2 mappend x y

foldMapA :: (Foldable t, Monoid m, Applicative f) => (a -> f m) -> t a -> f m
foldMapA f = getAp . foldMap (Ap . f)

Of course, we can use some Data.Coerce magic to avoid silly eta
expansion, as usual.

The "right" way to perform the actions in the opposite order is probably just

foldMapA f . Reverse

and you can accumulate the other way using getDual . foldMapA (Dual . f)

So I think the whole Applicative side of this proposal might be seen as further
motivation for my long-ago stalled proposal to add Ap to Data.Monoid.

On Wed, Dec 6, 2017 at 7:27 PM, Andrew Martin <[hidden email]> wrote:
> I had not considered that. I tried it out on a gist
> (https://gist.github.com/andrewthad/25d1d443ec54412ae96cea3f40411e45), and
> you're definitely right. I don't understand right monadic folds well enough
> to write those out, but it would probably be worthwhile to both variants of
> it as well. Here's the code from the gist:
>
> {-# LANGUAGE ScopedTypeVariables #-}
>
> module Folds where
>
> import Control.Applicative
>
> -- Lazy in the monoidal accumulator.
> foldlMapM :: forall g b a m. (Foldable g, Monoid b, Applicative m) => (a ->
> m b) -> g a -> m b
> foldlMapM f = foldr f' (pure mempty)
>   where
>   f' :: a -> m b -> m b
>   f' x y = liftA2 mappend (f x) y
>
> -- Strict in the monoidal accumulator. For monads strict
> -- in the left argument of bind, this will run in constant
> -- space.
> foldlMapM' :: forall g b a m. (Foldable g, Monoid b, Monad m) => (a -> m b)
> -> g a -> m b
> foldlMapM' f xs = foldr f' pure xs mempty
>   where
>   f' :: a -> (b -> m b) -> b -> m b
>   f' x k bl = do
>     br <- f x
>     let !b = mappend bl br
>     k b
>
>
> On Wed, Dec 6, 2017 at 6:11 PM, David Feuer <[hidden email]> wrote:
>>
>> It seems this lazily-accumulating version should be Applicative, and a
>> strict version Monad. Do we also need a right-to-left version of each?
>>
>> On Dec 6, 2017 9:29 AM, "Andrew Martin" <[hidden email]> wrote:
>>
>> Several coworkers and myself have independently reinvented this function
>> several times:
>>
>>     foldMapM :: (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a -> m
>> b
>>     foldMapM f xs = foldlM (\b a -> mappend b <$> (f a)) mempty xs
>>
>> I would like to propose that this be added to Data.Foldable. We have the
>> triplet foldr,foldl,foldMap in the Foldable typeclass itself, and
>> Data.Foldable provides foldrM and foldlM. It would be nice to provide
>> foldMapM for symmetry and because it seems to be useful in a variety of
>> applications.
>>
>> --
>> -Andrew Thaddeus Martin
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>>
>
>
>
> --
> -Andrew Thaddeus Martin

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add foldMapM to Data.Foldable

David Feuer
Indeed,

f g = g (\x -> putStr x >> pure x) ["hi", "I'm", "Bob"]

f foldMapA = f $ \g -> getAp . foldMap (Ap . g)
prints "hiI'mBob" and returns "hiI'mBob"
f (\g -> forwards . foldMayO (Backwards . g))
= f (\g -> forwards . getAp . foldMap (Ap . Backwards . g))
prints "BobI'mhi" and returns "hiI'mBob"
f (\g -> fmap getDual . foldMapA (fmap Dual . g))
= f (\g -> fmap getDual . foldMap (Ap . fmap Dual . g))
prints "hiI'mBob" and returns "BobI'mHi"
f (\g -> foldMapA g . Reverse)
= f (\g -> getAp . getDual . foldMap (Dual . Ap . g)
prints "BobI'mHi" and returns "BobI'mHi"

None of this affects the strict (monadic) versions, which should be defined in
terms of foldr and foldl. It's not entirely clear to me which way those monadic
versions should accumulate.


On Wed, Dec 6, 2017 at 11:15 PM, David Feuer <[hidden email]> wrote:

> Actually, the key modifiers are probably Dual and Backwards, with Reverse
> combining them. Or something like that.
>
> On Dec 6, 2017 8:20 PM, "David Feuer" <[hidden email]> wrote:
>>
>> Actually, the most "natural" Applicative version is probably this:
>>
>> newtype Ap f a = Ap {getAp :: f a}
>> instance (Applicative f, Monoid a) => Monoid (Ap f a) where
>>   mempty = Ap $ pure mempty
>>   mappend (Ap x) (Ap y) = Ap $ liftA2 mappend x y
>>
>> foldMapA :: (Foldable t, Monoid m, Applicative f) => (a -> f m) -> t a ->
>> f m
>> foldMapA f = getAp . foldMap (Ap . f)
>>
>> Of course, we can use some Data.Coerce magic to avoid silly eta
>> expansion, as usual.
>>
>> The "right" way to perform the actions in the opposite order is probably
>> just
>>
>> foldMapA f . Reverse
>>
>> and you can accumulate the other way using getDual . foldMapA (Dual . f)
>>
>> So I think the whole Applicative side of this proposal might be seen as
>> further
>> motivation for my long-ago stalled proposal to add Ap to Data.Monoid.
>>
>> On Wed, Dec 6, 2017 at 7:27 PM, Andrew Martin <[hidden email]>
>> wrote:
>> > I had not considered that. I tried it out on a gist
>> > (https://gist.github.com/andrewthad/25d1d443ec54412ae96cea3f40411e45),
>> > and
>> > you're definitely right. I don't understand right monadic folds well
>> > enough
>> > to write those out, but it would probably be worthwhile to both variants
>> > of
>> > it as well. Here's the code from the gist:
>> >
>> > {-# LANGUAGE ScopedTypeVariables #-}
>> >
>> > module Folds where
>> >
>> > import Control.Applicative
>> >
>> > -- Lazy in the monoidal accumulator.
>> > foldlMapM :: forall g b a m. (Foldable g, Monoid b, Applicative m) => (a
>> > ->
>> > m b) -> g a -> m b
>> > foldlMapM f = foldr f' (pure mempty)
>> >   where
>> >   f' :: a -> m b -> m b
>> >   f' x y = liftA2 mappend (f x) y
>> >
>> > -- Strict in the monoidal accumulator. For monads strict
>> > -- in the left argument of bind, this will run in constant
>> > -- space.
>> > foldlMapM' :: forall g b a m. (Foldable g, Monoid b, Monad m) => (a -> m
>> > b)
>> > -> g a -> m b
>> > foldlMapM' f xs = foldr f' pure xs mempty
>> >   where
>> >   f' :: a -> (b -> m b) -> b -> m b
>> >   f' x k bl = do
>> >     br <- f x
>> >     let !b = mappend bl br
>> >     k b
>> >
>> >
>> > On Wed, Dec 6, 2017 at 6:11 PM, David Feuer <[hidden email]>
>> > wrote:
>> >>
>> >> It seems this lazily-accumulating version should be Applicative, and a
>> >> strict version Monad. Do we also need a right-to-left version of each?
>> >>
>> >> On Dec 6, 2017 9:29 AM, "Andrew Martin" <[hidden email]>
>> >> wrote:
>> >>
>> >> Several coworkers and myself have independently reinvented this
>> >> function
>> >> several times:
>> >>
>> >>     foldMapM :: (Foldable g, Monoid b, Monad m) => (a -> m b) -> g a ->
>> >> m
>> >> b
>> >>     foldMapM f xs = foldlM (\b a -> mappend b <$> (f a)) mempty xs
>> >>
>> >> I would like to propose that this be added to Data.Foldable. We have
>> >> the
>> >> triplet foldr,foldl,foldMap in the Foldable typeclass itself, and
>> >> Data.Foldable provides foldrM and foldlM. It would be nice to provide
>> >> foldMapM for symmetry and because it seems to be useful in a variety of
>> >> applications.
>> >>
>> >> --
>> >> -Andrew Thaddeus Martin
>> >>
>> >> _______________________________________________
>> >> Libraries mailing list
>> >> [hidden email]
>> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> >>
>> >>
>> >
>> >
>> >
>> > --
>> > -Andrew Thaddeus Martin
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries