Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
From Traversable to Foldable

From Traversable to Foldable

Definitions

class Functor t => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

newtype Constant m a = Constant { getConstant :: m }

foldMap implementation by Traversable

foldMap :: (Traversable f, Monoid m) => (a -> m) -> f a -> m
foldMap f = getCnstant . traverse (Constant . f)

Type Diagram

                                   f  ::  a -> m
                                               |
                        Constant      ::       m -> Constant m a
 
                        Constant . f  ::  a ->      Constant m a
                                          |         |  |
              traverse                :: (a ->      f          b ) -> t a -> f          (t b)
                                                                             |_________          
              traverse (Constant . f) ::                              t a -> Constant m (t b) 
                                                                                      |  |
getConstant                           ::                                     Constant m  a    -> m
                                                                                                 |
getConstant . traverse (Constant . f) ::                              t a ->                     m

Intuition

Constant do nothing, so ignore it, same as the tag of Constant.

traverse              :: Applicative f => (a -> f b) -> t a -> f (t b)
                                                |              |  |
                            ignore functor   <--+--------------+  +--> ignore tag
                                                                  
getConstant . traverse (Constant . f) ::  (a ->   b)    t a ->      b

Reference

http://www.corecursion.net/post/2017-01-12-Why_Traversable_is_the_real_deal

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