What should a Traversable instance look like for a Tree datatype with a nested Maybe value?

Question

I have a Haskell exam in three days, so I thought I should practice a little and pulled up past exams, one of which features the following Tree datatype:

data Tree a = Leaf1 a | Leaf2 a a | Node (Tree a) (Maybe (Tree a)) deriving (Eq, Ord, Show)

It didn't seem that challenging at first, but then I realized I have to write a Traversable instance for this Tree. Dealing with the leaves were easy enough:

instance Traversable Tree where
  traverse f (Leaf1 a)   = Leaf1 <$> f a
  traverse f (Leaf2 a b) = Leaf2 <$> f a <*> f b

However, I started running into problems with the Node.

  traverse f (Node t Nothing)  = Node <$> traverse f t <*> Nothing
  traverse f (Node l (Just r)) = Node <$> traverse f l <*> Just (traverse f r)

Naturally, these don't work, and I can't wrap my head around what should come after the second <*>. I tried using holes, but the messages given to me by ghci didn't help much (I get that the problem is with types, but I have no idea how I'm supposed to fix it).

Here's the error message I got when I tried to compile it:

* Couldn't match type `f' with `Maybe'
  `f' is a rigid type variable bound by
    the type signature for:
      traverse :: forall (f :: * -> *) a b.
                  Applicative f =>
                  (a -> f b) -> Tree a -> f (Tree b)
    at exam.hs:92:3-10
  Expected type: f (Maybe (Tree b))
    Actual type: Maybe (Maybe (Tree b))
* In the second argument of `(<*>)', namely `Nothing'
  In the expression: Node <$> traverse f t <*> Nothing
  In an equation for `traverse':
      traverse f (Node t Nothing) = Node <$> traverse f t <*> Nothing
* Relevant bindings include
    f :: a -> f b (bound at exam.hs:94:12)
    traverse :: (a -> f b) -> Tree a -> f (Tree b)
      (bound at exam.hs:92:3)
   |
94 |   traverse f (Node t Nothing)  = Node <$> traverse f t <*> Nothing
   |                                                            ^^^^^^^

Could someone please give me some pointers or a possible fix for this issue?

Answer 1

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 traversed them recursively but didn't modify them otherwise.

Answer 2

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.