CMSC-16100

Honors Introduction to Programming, I

Autumn Quarter, 2017

Home Policies Lectures Notes Labs

---

Piazza

Lecture 21: 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

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.

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.

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 f:

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 it's 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.

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 disassociate 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.

• CommuteM.hs

---

© 2009–2018 Ravi Chugh, Stuart A. Kurtz
Last modified: October 02, 2018