What should a Traversable instance look like for a Tree datatype with a nested Maybe value?
traverse
lets you apply a "function with an effect" to every "slot" of a data structure, maintaining the structure's shape. It has the type:
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
It relies crucially on the fact that the type of the "effects" is an Applicative
. What operations does Applicatve
provide?
- it lets us lift pure functions and apply them to effectful actions with
<$>
. - it lets us combine effectful actions with
(<*>) :: f (a -> b) -> f a -> f b
. Notice that the second parameter is an effectful action, not a pure value. - it lets us take any pure value and put it in an effectful context, using
pure :: a -> f a
.
Now, when the node has a Nothing
, there's no effect to perform because there aren't any values, but the <*>
still requires an effectful action on the right. We can use pure Nothing
to make the types fit.
When the node has a Just t
, we can traverse
the subtree t
of type Tree a
with the function a -> f b
and end up with an action f (Tree b)
. But the <*>
is actually expecting an f (Maybe (Tree b))
. The lifted Node
constructor makes us expect that. What can we do?
The solution is to lift the Just
constructor into the action using <$>
, which is another name for fmap
.
Notice that we haven't changed the overall "shape" of the value: the Nothing
is still Nothing
, the Just
is still Just
. The structure of the subtrees didn't change either: we traverse
d them recursively but didn't modify them otherwise.
The short answer is that you need to use traverse
to get inside the Maybe
.
The Traversable
and Foldable
instances for a type often have a similar structure to its Functor
instance. Whereas fmap
maps a pure function over a structure, combining the results back up with the pure constructors:
instance Functor Tree where
fmap f (Leaf1 a) = Leaf1 (f a)
fmap f (Leaf2 a1 a2) = Leaf2 (f a1) (f a2)
fmap f (Node ta mta) = Node (fmap f ta) (fmap (fmap f) mta)
Note the (fmap (fmap f) mta)
: the outer fmap
maps over the Maybe
, while the inner one maps over the Tree
:
(fmap
:: (Tree a -> Tree b)
-> Maybe (Tree a) -> Maybe (Tree b))
((fmap
:: (a -> b)
-> Tree a -> Tree b)
f)
mta
traverse
instead maps an effectful function over the structure, and correspondingly lifts the constructors into Applicative
with the <$>
and <*>
operators:
instance Traversable Tree where
traverse f (Leaf1 a) = Leaf1 <$> f a
traverse f (Leaf2 a1 a2) = Leaf2 <$> f a1 <*> f a2
traverse f (Node ta mta) = Node <$> traverse f ta <*> traverse (traverse f) mta
Again, notice that we must traverse
the Maybe
, and within that, traverse
the Tree
, but instead of a pure function a -> b
, we just have an effectful function a -> f b
, given Applicative f
:
(traverse
:: (Tree a -> f (Tree b))
-> Maybe (Tree a) -> f (Maybe (Tree b)))
((traverse
:: (a -> f b)
-> Tree a -> f (Tree b))
f)
mta
Likewise, foldMap
has a similar structure, but instead of reconstructing the data type, it combines results using a Monoid
instance:
instance Foldable Tree where
foldMap f (Leaf1 a) = f a
foldMap f (Leaf2 a1 a2) = f a1 <> f a2
foldMap f (Node ta mta) = foldMap f ta <> foldMap (foldMap f) mta
And here’s a simple example usage of traverse
:
> traverse (\ x -> print x *> pure (x + 1)) (Node (Leaf1 10) (Just (Leaf2 20 30)))
10
20
30
Node (Leaf1 11) (Just (Leaf2 21 31))
With the DeriveFoldable
, DeriveFunctor
, and DeriveTraversable
extensions, you may add a deriving (Foldable, Functor, Traversable)
clause to a data type and use the -ddump-deriv
flag of GHC to see the generated code.