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

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.