Before we can get into the more advanced topics on Lenses, it is
important to really understand both Foldable and Traversable, which
is the motivation behind this article.
Let’s begin with Foldable. Foldable represents structures which can
be folded. What does that mean? Here are a few examples:
- Calculating the sum of a list.
- Calculating the product of a list.
- Folding a tree to get a maximum value.
We can describe a fold as taking a structure and reducing it to a
single result. That’s also why some languages have a reduce
function instead of a fold, even though they mean the same thing.
It is important to really understand the concept behind a fold in
general, not in terms of specific functions like foldl or foldr.
Whenever you see the word fold in a function name, think reducing a
larger structure to a single result.
Now comes the time to take a look at the Foldable type class.
class Foldable t where
fold :: Monoid m => t m -> m
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
foldr' :: (a -> b -> b) -> b -> t a -> b
foldl :: (b -> a -> b) -> b -> t a -> b
foldl' :: (b -> a -> b) -> b -> t a -> b
foldr1 :: (a -> a -> a) -> t a -> a
foldl1 :: (a -> a -> a) -> t a -> a
We won’t go into detail on all of these, since foldl, foldr,
foldl', foldr', foldl1 and foldr1 work the same as their
counterparts from Data.List.
What is interesting here is that fold and foldMap require the
elements of the Foldable to be Monoids. Let’s just quickly take a
look at what a Monoid is.
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
Nothing really special here, Monoid just simply defines a zero element
via mempty and an associative operation mappend for combining two
Monoids into one. mconcat is just a convenience method which has a
default implementation using mappend.
mconcat :: [a] -> a
mconcat = foldr mappend mempty
fold and foldMap
The interesting thing about fold and foldMap is that they use a
Monoid instead of a function to give us the final result. This might
not be obvious at first, but by picking the right Monoid it is
essentialy the same as passing in a function, since it will just use the
mappend defined for that Monoid instance.
One very very very important aspect to understand here is that it is the
fold function that requires the elements of Foldable to have a
Monoid instance, while Foldable itself does not have that
restriction.
The result of this is that we can have something like [Int], where the
[] is a Foldable, but Int is not a Monoid, though as long as we
don’t use any of the functions from Foldable that require a Monoid
we’ll be OK. Here’s an example
λ> foldr1 (+) [1,2,3,4]
10
λ> fold ["hello", "world"]
"helloworld" -- Strings are Monoids using concatenation
λ> fold [1,2,3,4]
<interactive>:1:1:
No instance for (Monoid a0) arising from a use of ‘it’
See how the problem only arises when we used fold with Int. We could
however wrap those Ints in a Monoid such as Sum or Product and
fold them then.
λ> fold [Sum 1, Sum 2, Sum 3, Sum 4]
Sum {getSum = 10}
This might seem tedious at first, but remember our Foldable type
class, as it also defines a function that is perfect for this particular
use case: foldMap :: Monoid m => (a -> m) -> t a -> m. We can read
this as Given a foldable containing things that aren’t Monoids, and a
function that can convert a single thing to a Monoid, I’ll give you back
a Monoid by traversing the foldable, converting everything to Monoids
and folding them together.
Here’s our previous example, but now using foldMap.
λ> foldMap Sum [1,2,3,4]
Sum {getSum = 10}
If you think about this for a little while we might even implement
fold in terms of foldMap. Why? When using foldMap we need to
provide a way to convert each item to a Monoid, but if those items
already are Monoids, we don’t need to do any conversion!
fold :: Monoid m => t m -> m
fold xs = foldMap id xs
Here’s the same in more steps.
λ> :t id
:: a -> a
λ> :t fold
:: (Monoid m, Foldable t) => t m -> m
λ> :t foldMap
:: (Monoid m, Foldable t) => (a -> m) -> t a -> m
λ> :t foldMap id
:: (Monoid m, Foldable t) => t m -> m
The actual Foldable type class requires either foldMap or foldr,
but for the sake of this article we won’t be looking into foldr.
Traversable
Now that we have an understanding of Foldable we can move on to
something more fun, Traversable. Traversable represents data
structures which can be traversed while perserving the shape. This is
why there is no filter or concatMap, since Traversable only
defines a way to move through the data structure, but not a way to
change it.
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)
If you look in the documentation for
Traversable
you might note that there is also mapM and sequence, but we won’t be
covering those in this article, since their implementation isn’t
interesting and can be done mechanically.
This might look a little intimidating at first, but don’t worry, we’ll
do this step by step by implementing a Traversable instance for a
list.
instance Traversable [] where
traverse f xs = _
Since the implementation will be recursive we first need to define the
base case for our recursion, which will be the empty list. The type that
we’re looking for is f [b], but because the list we’re traversing is
empty, we just need to wrap it in the Applicative context.
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = _
Next goes the actual recursive implementaion. We have a function f :: a -> f b and a head of the list which has the type a. The only thing we
can do at this point is apply the function.
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = f x
This won’t typecheck of course, because we’re returning f b instead of
f [b]. We could cheat here a little bit and just try to apply a some
function f b -> f [b] to get the result. We can use (:[]) which has
a type of a -> [a] and fmap it on what we have.
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = fmap (:[]) (f x)
Now we have an implementation that type checks, but it is still wrong, since it doesn’t satisfy the rule that a traversal must not change the shape of the structure it is traversing, and here we are just dropping the rest of the list. We need to find a way to use recursion and somehow combine the results.
By looking at the type of traverse :: (a -> f b) -> t a -> f (t b), or
in our case specifically traverse :: (a -> f b) -> [a] -> f [b] we can
see that using traverse recursively on the tail of the list would give
us the type we need.
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = (f x) _ traverse f xs
Now we have two values, one of type f b and one of type f [b], which
are basically the head and the tail of the list, both wrapped in an
Applicative context. We also have a function (:) :: a -> [a] -> [a],
which concatenates a head and a tail together into a single list.
Knowing all of this it just comes down to a basic use of Applicative
where we have a function of two arguments and need to apply it to two
values in the Applicative context. We can do this in two different
ways.
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = (:) <$> f x <*> traverse f xs
And an alternative definition using liftA2.
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = liftA2 (:) (f x) (traverse f xs)
It should be pretty clear now that we need the Applicative to be able
to actually implement traverse. If all we had was a Functor we
wouldn’t be able to combine the f b and f [b] together.
sequenceA
Now that we have traverse we can move on to define sequenceA. Here’s
a specific type for our list instance.
sequenceA :: Applicative f => [f a] -> f [a]
If you’re familiar with sequence :: Monad m => [m a] -> m [a] from
Control.Monad then you can see how these two functions are doing the
same thing. It simply takes the Applicative effects, runs them and
pulls them out of the list.
The implementation is really simple. Starting out with an empty list, we
just need to wrap it in the Applicative context.
sequenceA [] = pure []
Next comes the actual recursive implementaiton. If we pattern match on
the head and the tail of the list, we’ll yet again get f a and [f a].
sequenceA (x:xs) = _
We can call sequenceA recursively on the tail to get f [a].
sequenceA [] = pure []
sequenceA (x:xs) = sequenceA xs
But of course this isn’t good enough. We need a way to combine the head
and the tail while they’re both wrapped in an Applicative context.
This can be done in the same way as we did previously with traverse,
using (:) and the Applicative functions <$> and <*>.
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs
Or alternatively using liftA2 again.
sequenceA [] = pure []
sequenceA (x:xs) = liftA2 (:) x (sequenceA xs)
That’s it, we have a working implementation for sequenceA.
Implementing sequenceA with traverse and vice versa
If we now look at our implementations for traverse and sequenceA we
can definitely see some similarity there.
traverse _ [] = pure []
traverse f (x:xs) = (:) <$> f x <*> traverse f xs
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs
The only difference is that traverse takes a function and applies it
to the head of the list, while sequenceA simply uses the head as it
is. Knowing this we can actually define sequenceA using traverse and
the id function.
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA xs = traverse id xs
Could we do the same thing the other way around though? Yes! We most
certainly can define traverse by using sequenceA and the fact that
every Traversable is also a Functor. Let’s take this step by step.
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f xs = _
We only have one way of applying our function a -> f b to the t a
and that is using fmap, which would give us t (f b).
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f xs = _ $ fmap f xs
Now we’ll get an error saying that we need a function t (f b) -> f (t b), which is exactly what sequenceA does!
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f xs = sequenceA $ fmap f xs
Traversable with default implementations
Given the two implementations we just got we can rewrite our initial
Traversable type class to use those as a default implementation for
both functions.
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f xs = sequenceA $ fmap f xs
sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA xs = traverse id xs
This is actually how it’s done in the Data.Traversable module, except
that if you look at the source code you’ll see the functions defined in
point free style.
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f
sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA = traverse id
Default implementation for Functor and Foldable using Traversable
It might not be so obvious at first, but a Traversable is a very
powerful concept. So powerful that it actually allows us to define both
Functor and Foldable if we have just a single function from
Traversable. The Data.Traversable module defines two functions,
fmapDefault and foldMapDefault, which can be used as an
implementation for fmap and foldMap if we so desire.
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
The way we’re going to implement these is very similar to what we did in the Lens introduction article. If this section is too hard for you to understand I recommend reading the Lens article first and then come back here. Everything will make a lot more sense.
Let’s first compare the types of traverse and fmap.
fmap :: Functor f => (a -> b) -> f a -> f b
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
The difference is that the function passed to traverse returns a value
wrapped in Applicative context, and the result is also wrapped. If we
could find a way to wrap the value after we apply the function, and then
unwrap it at the end, we would get exactly the same type as fmap.
We can use the Identity functor to do this, which defines a way to
unwrap it using runIdentity :: Identity a -> a.
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f x = _
We don’t have that many options here. To be able to give the function
f to a traverse we need to change it’s type from a -> f a. That’s
where Identity comes in.
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f x = traverse (Identity . f) x
Now our types don’t align, since we are supposed to return t b but we
are returning Identity (t b). The solution here is the above mentioned
runIdentity which simply unwraps the value.
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f x = runIdentity $ traverse (Identity . f) x
And once more in point free style.
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f = runIdentity . traverse (Identity . f)
Compare this to the definition of over and you can see how it looks
and feels almost exactly the same.
over :: Lens s a -> (a -> a) -> s -> s
over ln f = runIdentity . ln (Identity . f)
We’ll explain how this relates to Lenses in more detail in a followup
article, but for now let’s move on to foldMapDefault.
Implementing foldMapDefault
This part is very hard to understand, so be careful.
If we compare the type of foldMapDefault with traverse we can yet
again see some similarity.
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
The difference from fmapDefault is that now we need a way to convert
each element of the Traversable to a Monoid.
We will use the Const applicative here, which as it so happens also
defines a Monoid instance.
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f x = _
As previously we can only use traverse together with a function a -> f b, but we have a -> m, where by using Const we can do the m -> f b.
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f x = traverse (Const . f) x
Again we’re faced with the problem of having Const m (t b) instead of
m, which can be solved using getConst.
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f x = getConst $ traverse (Const . f) x
And a point free version.
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)
This is also very similar to one of the functions Lens provides, in
particular view.
view :: Lens s a -> s -> a
view ln = getConst . ln Const
Implementing Functor and Foldable with Traversable
Now that we understand how both fmapDefault and foldMapDefault work,
we can use them to define a Functor and a Foldable instance for any
Traversable we might have.
We can test this out by defining a simple list type.
data List a = Nil
| Cons a (List a)
deriving Show
instance Functor List where
fmap = fmapDefault
instance Foldable List where
foldMap = foldMapDefault
instance Traversable List where
traverse _ Nil = pure Nil
traverse f (Cons x xs) = fmap Cons (f x) <*> traverse f xs
We used fmap = fmapDefault and foldMap = foldMapDefault to define
our Functor and Foldable instances, which is all made possible by
also having a Traversable instance. Let’s test this out to make sure
it works!
λ> traverse (\x -> Just (x + 1)) (Cons 1 (Cons 2 (Cons 3 Nil)))
Just (Cons 2 (Cons 3 (Cons 4 Nil)))
λ> fold (Cons "hello" (Cons "world" Nil))
"helloworld"
λ> fmap (+1) (Cons 1 (Cons 2 (Cons 3 Nil)))
Cons 2 (Cons 3 (Cons 4 Nil))
It might be a surprising, but everything works as it is supposed to.
Haskell