Foldr/Foldl for free when Tree is implementing Foldable foldMap?

by

We begin with the type of foldMap:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

foldMap works by mapping the a -> m function over the data structure and then running through it smashing the elements into a single accumulated value with mappend.

Next, we note that, given some type b, the b -> b functions form a monoid, with (.) as its binary operation (i.e. mappend) and id as the identity element (i.e. mempty. In case you haven’t met it yet, id is defined as id x = x). If we were to specialise foldMap for that monoid, we would get the following type:

foldEndo :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b)

(I called the function foldEndo because an endofunction is a function from one type to the same type.)

Now, if we look at the signature of the list foldr

foldr :: (a -> b -> b) -> b -> [a] -> b

we can see that foldEndo matches it, except for the generalisation to any Foldable and for some reordering of the arguments.

Before we get to an implementation, there is a technical complication in that b -> b can’t be directly made an instance of Monoid. To solve that, we use the Endo newtype wrapper from Data.Monoid instead: 

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

Written in terms of Endo, foldEndo is just specialised foldMap:

foldEndo :: Foldable t => (a -> Endo b) -> t a -> Endo b

So we will jump directly to foldr, and define it in terms of foldMap.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

Which is the default definition you can find in Data.Foldable. The trickiest bit is probably Endo . f; if you have trouble with that, think of f not as a binary operator, but as a function of one argument with type a -> (b -> b); we then wrap the resulting endofunction with Endo.

As for foldl, the derivation is essentially the same, except that we use a different monoid of endofunctions, with flip (.) as the binary operation (i.e. we compose the functions in the opposite direction).

More Related Contents:

  1. foldl versus foldr behavior with infinite lists
  2. Writing foldl using foldr
  3. What constitutes a fold for types other than list?
  4. How does foldr work?
  5. Implement zip using foldr
  6. An example of a Foldable which is not a Functor (or not Traversable)?
  7. `String’ is applied to too many type arguments
  8. How do I define Lisp’s apply in Haskell?
  9. Operating on a return from a Maybe that contains “Just”
  10. Is there a Haskell idiom for updating a nested data structure?
  11. What’s so bad about Lazy I/O?
  12. Explicitly import instances
  13. foldl is tail recursive, so how come foldr runs faster than foldl?
  14. How to compare two functions for equivalence, as in (λx.2*x) == (λx.x+x)?
  15. Why do 3 and x (which was assigned 3) have different inferred types in Haskell? [duplicate]
  16. How do I use fix, and how does it work?
  17. List of different types?
  18. What is Levity polymorphism
  19. How to infer the type of an expression manually
  20. Understanding the Haskell as-pattern
  21. Haskell: How to create most generic function possible that applies a function to tuple items
  22. Concrete example showing that monads are not closed under composition (with proof)?
  23. How to use (->) instances of Monad and confusion about (->)
  24. Why can a Num act like a Fractional?
  25. Non-Trivial Lazy Evaluation
  26. Is there a way to see the list of functions in a module, in GHCI?
  27. Haskell GHC: what is the time complexity of a pattern match with N constructors?
  28. Creating unique labels in Haskell
  29. Tools for analyzing performance of a Haskell program
  30. Haskell: Where vs. Let

Leave a Comment