# Lecture 19: Foldable and Traversable

## Foldable

We've been using the foldr function to crunch lists, as if its type was

 foldr :: (a -> b -> b) -> b -> [a] -> b 

This is great, but there are other collection classes that order their elements, and so could be processed in conceptually the same way. To that end, we have the Foldable type:

 class Foldable t where foldr :: (a -> b -> b) -> b -> t a -> b ... 

which is where foldr actually lives. Let's do a simple example another type that orders its elements, the BinaryTree type we've seen before:

 data BinaryTree a = Empty | Node (BinaryTree a) a (BinaryTree a) deriving Show 

We can write foldr for this type:

 instance Foldable BinaryTree where foldr f acc Empty = acc foldr f acc (Note left a right) = foldr f (f a (foldr f acc right)) left 

The equation for foldr f acc (Note left a right) takes a little thinking, but this form is easy to derive if you understand that foldr builds its result value from right-to-left.

The Foldable type class defines a number of other useful functions, e.g.,

 class Foldable t where foldr :: (a -> b -> b) -> b -> t a -> b foldr1 :: (a -> a -> a) -> t a -> a foldl :: (b -> a -> b) -> b -> t a -> b foldl1 :: (a -> a -> a) -> t a -> a fold :: Monoid m => t m -> m foldMap :: Monoid m => (a -> m) -> t a -> m toList :: t a -> [a] ... 

The foldl function does a left-to-right crunching of the list, and is often useful in processing very large data structures that are built lazily. The variants foldr1 and foldl1 deal with simple, monoid-like folds over non-empty lists (obviating the need for an explicit identity).

The Foldable type class includes many other functions we've been thinking of as list-specific, e.g., length, elem, minimum, maximum, sum, and product. A moment's reflection will reveal that each can easily be written in terms of foldr, and so their greater generality should not be a surprise.

The fold and foldMap functions deal with the case where the combining function has type m -> m -> m for some Monoid m. Default definitions exist so that a minimal complete definition of a Foldable instance must define either foldr or foldMap. What is perhaps even more surprising is that it is often easier to write the instance definition using foldMap, e.g.

 instance Foldable BinaryTree where foldMap _ Empty = mempty foldMap f (Node left a right) = foldMap f left <> f a <> foldMap f right 

This is very natural: we process the recursive parts recursively, and combine the pieces using (<>).

What may be surprising in all of this is that functions like foldr and foldl may have different execution characteristics, but because foldr is complete for Foldable, it is somehow possible to write foldl in terms of foldr. How can this be? It is useful to understand the definition of foldMap in terms of foldr, and conversely.

To get foldMap from foldr is relatively straightforward:

 foldMap f container = foldr (\a b -> f a <> b) mempty container 

Exercise 19.1 The code fairy would like you to η-reduce the definition above. She doesn't want you to eliminate f, but she thinks you should be able to eliminate a, b, and container without difficulty.

What is perhaps surprising is the other direction. The foldMap function requires an argument whose domain is a Monoid, but there's no such restriction on the combining function of foldr. Obviously, there's some sort of trick. A crucial observation is that if f is the combining function for foldr, then providing a single argument to f results in a function of type b -> b, and this may remind you of the Endo type:

 newtype Endo a = Endo { appEndo :: a -> a } 

The type Endo a is a monoid instance, where (<>) is just composition under the wrapper, and mempty is Endo id. Thus,

 foldr f acc container = appEndo (foldMap (\a -> Endo (f a)) container) acc 

i.e., we use foldMap to build a function, which, when applied to acc, reduces to foldr f acc container.

Exercise 19.2 It's the code fairy again. Do I need to tell you what to do?

This may (should?) remind you of the difference list approach to implementing the Doc type from Scalability supplementary lecture (16a).

## Traversable

The Traverable type class includes types that we can "walk across." It is a simultaneous generalization of Functor and Foldable, and as we'll see, it's especially natural and easy to implement when the underlying type is also an Applicative instance.

Let's begin with a reconsideration of the Applicative type class, which we sometimes think of as a generalization of the Functor type class that enables us to apply pure functions to zero or more fancy values, where what "apply" means depends on particular Applicative type. It is useful to think of Applicative types as defining a kind of idiom.

Consider, for example, the function mapM :: Monad m => (a -> m b) -> [a] -> m [b]. We can implement this function by "walking along the list," i.e., via a natural structural induction, as follows:

 mapM f [] = pure [] mapM f (a:as) = pure (:) <*> f a <*> mapM as 

McBride and Patterson, the authors of the original paper on Applicative, invented the idea of "idiom brackets," where

 ⟦ f a_1 ... a_n ⟧ 

represents

 pure f <*> a_1 <*> ... <*> a_n 

If we rewrite the defining of mapM using idiom brackets, we have

 mapM f [] = ⟦ [] ⟧ mapM f (a:as) = ⟦ (:) (f a) (mapM f as) ⟧ 

Contrast this, for a moment, with the definition of map:

 map f [] = [] map f (a:as) = f a : map f as 

If we rewrite the last line in prefix notation, we get

 map f [] = [] map f (a:as) = (:) (f a) (map f as) 

Thus, the definition of mapM is just the definition of map, but embellished with idiom brackets on the right-hand side. Another way of describing this is that mapM is an effectful version of map, or alternatively, that map is a pure version of mapM.

This may seem like abstract nonsense, but it makes an interesting point: mapM has the wrong constraint! We didn't need Monad, only Applicative. We'll see in a bit why this hasn't been fixed.

Our next thought about generalizing mapM is that we might be able to replace the [] type with a less restrictive type class. This leads us to

 class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 

Note that traverse is mapM, but with just the right type constraints: we've moved from Monad to Applicative as the constraint on the type of f, and we're generalizing [] to t. In fact, the implementation of mapM in the Haskell sources is just mapM = traverse!

But the curious thing is that creating instances of Traversable follows the pattern we established above for mapM. We just “implement fmap,” and then put the left hand side of the definitions in idiom brackets, i.e., add pure and (<*>) as needed.

Let's do an extended example, using the BinaryTree type as before. As we'll see, this involves an interesting and unexpected difficulty.

We have the Foldable instance above, and we've done Functor before:

 instance Functor BinaryTree where fmap _ Empty = Empty fmap f (Node left a right) = Node (fmap f left) (f a) (fmap f right) 

Let's remember that definition!

The traverse function is just an effectful fmap, intuitively,

 instance Traversable BinaryTree where traverse _ Empty = [[ Empty ]] traverse f (Node left a right) = [[ Node (traverse f left) (f a) (traverse f right) ]] 

I.e., just the definition of fmap for this type, but with idiom brackets on the left. Of course, idiom brackets aren't part of Haskell syntax, so we have to translate them out:

 instance Traversable BinaryTree where traverse _ Empty = pure Empty traverse f (Node left a right) = Node <$> traverse f left <*> f a <*> traverse f right  Of course, it's one thing to have this toy, and another to know how to play with it. Let's consider a simple problem: labelling the items in a container with an integer. To that end, we'll use a little gadget in State:  label :: a -> State Int (Int,a) label a = do ix <- get modify (+1) pure (ix,a)  We can then add labels to the values held in a Traversable container:  addLabels :: (Traversable t) => t a -> t (Int,a) addLabels ta = evalState (traverse label ta) 1  With this:  > testTree Node (Node Empty 1 (Node Empty 2 Empty)) 3 (Node Empty 4 (Node Empty 5 Empty)) > addLabels testTree Node (Node Empty (1,1) (Node Empty (2,2) Empty)) (3,3) (Node Empty (4,4) (Node Empty (5,5) Empty)) > toList (addLabels testTree) [(1,1),(2,2),(3,3),(4,4),(5,5)]  exactly as you might expect. *Exercise 19.3 The throwaway use of State here is a bit heavy-handed. Data.Traversable includes two functions, mapAccumL and mapAccumR that perform state-based traversals, albeit with an explicitly exposed state. Rewrite addLabels using one of the mapAccum{L,R} functions, rather than State. Exercise 19.4 Let's consider a different tree-based container class:  data MultiTree a = Node [MultiTree a] | Leaf a  This describes a tree, in which the values are contained in Leaf values, and the Node values can contain an arbitrary number of sub-trees. Implement the usual type classes for MultiTree: Eq , Ord, Functor, Applicative, Monad, Monoid (for MultiTree a), Alternative, MonadPlus, Foldable, Traversable, at suitable kinds and with suitable constraints. If you do this artfully, you'll see sub-expressions like fmap . fmap in the definition of fmap, and traverse . traverse in the definition of traverse. These happen because [] is a Functor and a Traversable, and both Functor and a Traversable are closed under composition. The Traversable type class is also the homes of another familiar function, sequence, which until recently had the type:  sequence :: Monad m => [m a] -> m [a]  In Traversable, the specific use of lists is revised to account for any Traversable type t:  sequence :: Monad m => t (m a) -> m (t a)  but here, as in the case of mapM, the implementation doesn't require the full power of a Monad constraint, and so we also have:  sequenceA :: Applicative f => t (f a) -> f (t a)  with  sequence = sequenceA  being merely a less generally typed version of sequenceA. ## A Bit of Wisdom There is a programming truism, evidently due to Tony Hoare but often attributed to Donald Knuth that's well worth knowing: Premature optimization is the root of all evil. There is considerable wisdom in this, but also a history of it being applied foolishly. For functional programmers, eschewing premature optimization often involves a natural preference for lists as an all-purpose container class, even when they're not entirely appropriate. Taking efficiency into consideration during the design phase of a program is timely, not premature, optimization, even if lower-level optimization is not. But we can usually get away with what otherwise would be a poor choice: by writing list-based code on a first pass, and then generalizing it to be type class dependent rather than specifically list dependent, gradually decoupling our program's code from its data representation choices, and so making it possible to revisit those choices late in program development, at a point when it would be positively painful in traditional languages. The traverse function is a good example of this. Many a traverse has begun life as a mapM where the underlying monad is IO. There's a recurring pattern here: you build a list of values, and then you want to do some IO once for each value on the list. If the IO action is simple, there's no big deal: you use mapM, or traverse if you want to placate the code fairy and/or facilitate future changes to data organization. But if you want to do anything complicated, you pretty much have to define and name a function to pass as a first argument to either. There is a better way. The Data.Traversable module has a variation of traverse called for, which takes its arguments in reversed order. This allows you to write code that looks like this:  for listOfValues$ \value -> do ... 

This is natural enough that it soon becomes a programming idiom for processing the values in a container.

For example, consider the “Collecting Permutations” problem from Lab 4. If we wanted to tackle this with more advanced data structures, we might end up using Data.Map and Data.Set to build a map from sorted keys to the set of words that generate that sort via:

 makePermutationMap :: [String] -> Map String (Set String) makePermutationMap = Map.unionsWith Set.union . map makeEntry where makeEntry word = Map.singleton (sort word) (Set.singleton word) 

We could then build main as follows:

 main :: IO (Map String ()) main = do permMap <- makePermutationMap . getWords <$> getContents for permMap$ \perms -> when (Set.size perms > 1) $do putStrLn . intercalate ", " . Set.toList$ perms 

In this case, the for iterates over the values of the Map, which is what this problem requires.

Of course, as our programmer's eye develops, there's a tendency to view the call to Set.toList with a bit of skepticism. Why do we need to convert from one container class (Set) to another ([])? In this case, it's because intercalate only works with lists. But we easily implement intercalate in terms of foldr1, and then take advantage of the fact that foldr1 :: Foldable t => (a -> a -> a) -> t a -> a is based on Foldable rather than [], mooting the need for translating the container from one form to the other:

 for permMap $\perms -> when (Set.size perms > 1)$ do putStrLn . foldr1 (\x acc -> x ++ ", " ++ acc) \$ perms 

## A Bit of Whimsy

One of the standard arguments for preferring Applicative over Monad whenever possible is that the composition of Applicative types are also Applicative in a natural way, whereas the composition of Monad types is not necessarily a Monad.

Recall that category-theoretic monads are defined in terms of join :: (Monad m) => m (m a) -> m a. The type of sequenceA hints at the fundamental difficulty. If we had a natural operator commuteM :: (Monad m, Monad n) => m (n a) -> n (m a), then we'd have a natural definition of join for the composed monads, as follows.

We start by undefining what we can't define (am I the only one who recalls the disassociated press version of the Gettysburg Address?!):

 commuteM :: (Monad m, Monad n) => m (n a) -> n (m a) commuteM = undefined 

This may seem pointless, but we want to show that this is the only obstruction, which is remarkable given the parallels with sequenceA: all we're missing is the Traversable instance for m!

Our goal is to show the we can start with m (n (m (n a))), and end with m (n a).

This sweeps under the rug a bit of the type traffic (we use Data.Functor.Compose's Compose type to represent the composition, and this requires unwrapping and re-wrapping), but gives the main idea.