Implementing Functor Instance for `ITree`

Question

Looking at this Typeclassopedia exercise, I typed out foldTree on the following type:

data ITree a = Leaf (Int -> a) | Node [ITree a]

And my implementation of Functor:

instance Functor (ITree) where
    fmap = iTreeMap

iTreeMap :: (a -> b) -> ITree a -> ITree b
iTreeMap f (Leaf x)  = Leaf $ fmap f x   
iTreeMap f (Node xs) = Node $ map (iTreeMap f) xs

Please critique its signature, correctness and style.

Answer 1

This looks mostly fine to me. If you wrote this code in a real codebase, I would not have any major qualms with it. Here are some nitpicks.

• The strangest thing to me was just the way you defined a separate function, iTreeMap, then used that as the definition of fmap. I would just define fmap directly within the body of the instance definition—no need to give it a separate name.

• The parentheses around ITree in the instance head are redundant. You could just write Functor ITree instead.

• Given that the value inside of a Leaf is a function, the use of the function instance of fmap within the definition of iTreeMap is a bit of genericism that I think is unnecessary. I would probably just use (.) and make the composition explicit, but that’s really personal preference.

With those above changes in place, the instance would look like this:

data ITree a = Leaf (Int -> a) | Node [ITree a]

instance Functor ITree where
  fmap f (Leaf x) = Leaf $ f . x
  fmap f (Node xs) = Node $ map (fmap f) xs

However, in real code, I wouldn’t actually do that at all. With the DeriveFunctor language extension, you could just ask GHC to write the Functor instance for you. Therefore, in real Haskell code, I would probably just write this:

{-# LANGUAGE DeriveFunctor #-}

data ITree a = Leaf (Int -> a) | Node [ITree a]
  deriving (Functor)

But that’s probably against the spirit of the exercise. :)