I spent some time playing with some fundamental abstractions over the past few days. I was curious about Functor, Foldable, and Traversable, in particular. Towards this end, I explored what each of these means as well as an implementation of their corresponding interfaces for a Tree data type. Here’s the type I worked with:
It’s a binary tree with data stored at leaf and internal nodes.
Functor gives us the ability to apply a function over an arbitrary structure. The map function from Prelude is a specialization of Functor’s fmap on lists. A few other instances already defined for us include:
MaybeEitherIOHere’s what the interface looks like:
class Functor (f :: * -> *) where
fmap :: (a -> b) -> f a -> f b
(<$) :: a -> f b -> f a
(<$>) = fmapWhat does it mean to apply a function over a Tree? Ideally, it’d affect all nodes of the Tree. This is accomplished as follows:
instance Functor Tree where
fmap _ Empty = Empty
fmap f (Leaf a) = Leaf (f a)
fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)A touch of pattern matching makes this easy enough to accomplish! With the instance implemented, now we can map pure functions over our Trees:
Foldable is an abstraction that represents the ability to summarize a structure as a value using a pure, binary function. Prelude exports foldl, foldr, foldl1, foldr1 that are specialized for lists. Let’s take a look at the more general version:
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 -> aIt looks pretty intimidating! Thankfully, if you implement either of foldMap or foldr, the rest of the interface is implemented in terms of those.
A nice feature of Haskell is that if you ever encounter a typeclass with many methods, and you’re not sure what’s the minimum you need to implement to satisfy that interface, you can always do:
This will warn:
Warning: No explicit implementation for
either ‘foldMap’ or ‘foldr’
In the instance declaration for ‘Foldable Tree’Even though only one of the two is necessary, we’ll implement both foldMap and foldr below for our Tree for the sake of illustration:
import Data.Monoid (mempty, (<>))
instance Foldable Tree where
foldr _ z Empty = z
foldr f z (Leaf a) = f z a
foldr f z (Node l x r) = foldr f (f z (foldr z l)) r
foldMap _ Empty = mempty
foldMap f (Leaf a) = f a
foldMap f (Node l x r) = (foldMap f l) <> (f x) <> (foldMap f r)foldr is clever. The zero value needed to start the operation is passed in. However, what do we do when we’re folding over subtrees? Remembering that f has type (a -> b -> b), the trick is to use one of the subtrees, along with the internal node data, as part of what we’re passing to one of the folds. This way, we can recurse into both subtrees and merge the values together.
foldMap explicitly requires a Monoid instance on the values it generates. Monoid gives us access to a zero value through mempty and a means to merge values through mappend or (<>). This makes the implementation of foldMap a little easier to read than that of foldr, especially in the Node case.
Here’s folding for our Tree:
> import qualified Data.Foldable as F
> F.foldr (+) 0 $ Node (Leaf 1) 2 (Leaf 3)
6
> F.foldr (*) 1 $ Node (Leaf 2) 3 (Leaf 4)
24Now, we arrive at Traversable. Traversable generalizes several notions related to effectful iteration over a structure. For example, the NICTA course asks one to provide an implementation for a traversal that converts a [Maybe a] -> Maybe [a]. A traversal we’ll look at later is one of the form (Integer -> IO ()) -> Tree Integer -> IO (Tree ()).
Let’s take a look at the interface:
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)
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
sequence :: Monad m => t (m a) -> m (t a)For this one, the required function is one of traverse or sequenceA. This is the case because all Monads are Applicatives, as further explained in the AMP. What’s more curious is that sequenceA can be implemented in terms of traverse and vice-versa.
Take note in the implementation below that we access to the functions from Functor, Foldable, and Applicative. Briefly, I reproduce the Applicative interface below:
class Functor f => Applicative (f :: * -> *) where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f aKey to the implementation below is the use of Applicative’s pure and apply (<*>), and Functor’s fmap (<$>). I’ll only cover the implementation of traverse:
instance Traversable Tree where
traverse _ Empty = pure Empty
traverse f (Leaf a) = Leaf <$> f a
traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f rAside from the use of Applicatives, this isn’t too different than our implementation of fmap above for Tree. The flow is similar. The primary difference is that traverse generalizes to effectful functions over fmap.
Here’s Traversable in use:
What if I told you that we didn’t have to write any of this ourselves? Let me show you a little bit of compiler magic that GHC provides:
{-# LANGUAGE DerivingFunctor #-}
{-# LANGUAGE DerivingFoldable #-}
{-# LANGUAGE DerivingTraversable #-}
data Tree' a
= Empty'
| Leaf' a
| Node' (Tree' a) a (Tree' a)
deriving (Show, Functor, Foldable, Traversable)Here’s all our examples from earlier:
> fmap (+1) $ Node' (Leaf' 1) 2 (Leaf' 3)
Node' (Leaf' 2) 3 (Leaf' 4)
> import qualified Data.Foldable as F
> F.foldr (+) 0 $ Node' (Leaf' 1) 2 (Leaf' 3)
6
> F.foldr (*) 1 $ Node' (Leaf' 2) 3 (Leaf' 4)
24
> import Data.Traversable (traverse)
> traverse print $ Node' (Leaf' 1) 2 (Leaf' 3)
1
2
3How does this work? What are the limitations of deriving Functor, Foldable, and Traversable? Are there any costs?
I’ll save the details for another time. For now, I defer to the GHC manual page on deriving and attribute the ability to derive these constructs (uniquely?) as a consequence of parametricity and category theory.
It’s terribly fun to work with recursive data in languages that have support for modeling hierarchical structures at the type level. The obvious solution involving pattern matching off of all branches is always a good start towards a correct, complete implementation.