I am a beginner at Haskell and learning from "Learn You a Haskell".
There's something I don't understand about the Tree
implementation of Foldable
.
instance F.Foldable Tree where
foldMap f Empty = mempty
foldMap f (Node x l r) = F.foldMap f l `mappend`
f x `mappend`
F.foldMap f r
Quote from LYAH: "So if we just implement foldMap
for some type, we get foldr
and foldl
on that type for free!".
Can someone explain this? I don't understand how and why do I get foldr
and foldl
for free now...
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).
foldr can always be defined as:
foldr f z t = appEndo (foldMap (Endo . f) t) z
where appEndo and Endo are just newtype unwrappers/wrappers. In fact, this code got pulled straight from the Foldable typeclass. So, by defining foldMap, you automatically get foldr.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With