Adding foldMap implementation to instance Foldable Maybe

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Adding foldMap implementation to instance Foldable Maybe

Eric Mertens
Hello,

Independently of a blog post I just noticed tonight on reddit, http://www.snoyman.com/blog/2017/01/follow-up-mapm I observed a stack overflow in some code I was working with due to a recursive call inside the function argument of for_

The code was a more complicated version of:

go = for_ someMaybe $ \m -> m >> go

It was wrong in thinking that this could be efficient because there’s an extra operation to set the result to a (). I thought I might try working around this with the following code.

for__ :: (Applicative f, Foldable t) => t a -> (a -> f ()) -> f ()
for__ xs f = unApp (foldMap (coerce f) xs)

newtype App f = App { unApp :: f () }

instance Applicative f => Monoid (App f) where
  mempty                  = App (pure ())
  mappend (App x) (App y) = App (x *> y)

Unfortunately the instance for Foldable for Maybe does not provide an implementation of foldMap, it only provides foldl and foldr. This means that the derived foldMap implementation attempts to mappend an extra mempty because the default implementation of foldMap is

With an explicit implementation of foldMap for the Maybe type (and maybe there are others that we’ve missed, for__ above can be stack efficient.

So I propose that we add an explicit implementation of foldMap to the Foldable Maybe instance

  foldMap _ Nothing  = mempty
  foldMap f (Just x) = f x


Best regards,
Eric Mertens

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

Re: Adding foldMap implementation to instance Foldable Maybe

David Feuer
This does not require a proposal--it merely replaces an inefficient implementation with an efficient one. If you're set up with Phabricator, just submit a patch. Otherwise, I'll be happy to do it for you.

On Jan 19, 2017 12:22 AM, "Eric Mertens" <[hidden email]> wrote:
Hello,

Independently of a blog post I just noticed tonight on reddit, http://www.snoyman.com/blog/2017/01/follow-up-mapm I observed a stack overflow in some code I was working with due to a recursive call inside the function argument of for_

The code was a more complicated version of:

go = for_ someMaybe $ \m -> m >> go

It was wrong in thinking that this could be efficient because there’s an extra operation to set the result to a (). I thought I might try working around this with the following code.

for__ :: (Applicative f, Foldable t) => t a -> (a -> f ()) -> f ()
for__ xs f = unApp (foldMap (coerce f) xs)

newtype App f = App { unApp :: f () }

instance Applicative f => Monoid (App f) where
  mempty                  = App (pure ())
  mappend (App x) (App y) = App (x *> y)

Unfortunately the instance for Foldable for Maybe does not provide an implementation of foldMap, it only provides foldl and foldr. This means that the derived foldMap implementation attempts to mappend an extra mempty because the default implementation of foldMap is

With an explicit implementation of foldMap for the Maybe type (and maybe there are others that we’ve missed, for__ above can be stack efficient.

So I propose that we add an explicit implementation of foldMap to the Foldable Maybe instance

  foldMap _ Nothing  = mempty
  foldMap f (Just x) = f x


Best regards,
Eric Mertens

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