I spent some time playing with some fundamental abstractions over the past few days. I was curious about
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
fmap on lists. A few other instances already defined for us include:
Here’s what the interface looks like:
What does it mean to apply a function over a
Tree? Ideally, it’d affect all nodes of the
Tree. This is accomplished as follows:
A touch of pattern matching makes this easy enough to accomplish! With the instance implemented, now we can map pure functions over our
Foldable is an abstraction that represents the ability to summarize a structure as a value using a pure, binary function.
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 -> a
It looks pretty intimidating! Thankfully, if you implement either of
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:
Even though only one of the two is necessary, we’ll implement both
foldr below for our
Tree for the sake of illustration:
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
(<>). This makes the implementation of
foldMap a little easier to read than that of
foldr, especially in the
Here’s folding for our
Now, we arrive at
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:
For this one, the required function is one of
sequenceA. This is the case because all
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
Applicative. Briefly, I reproduce the
Applicative interface below:
Key to the implementation below is the use of
pure and apply
(<$>). I’ll only cover the implementation of
Aside 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
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:
Here’s all our examples from earlier:
How does this work? What are the limitations of deriving
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.