# Foldable and Traversable

### From HaskellWiki

(Added an alternative implementation of generic zipWith) |
BrettGiles (Talk | contribs) m (FoldableAndTraversable moved to Foldable and Traversable) |

## Revision as of 15:41, 20 April 2008

## Contents |

# 1 Notes on Foldable, Traversable and other useful classes

*or "Where is Data.Sequence.toList?"*

Data.Sequence is recommended as an efficient alternative to lists, with a more symmetric feel and better complexity on various operations.

When you've been using it for a little while, there seem to be some baffling omissions from the API. The first couple you are likely to notice are the absence of "map" and "toList".

The answer to these lies in the long list of instances which Sequence has. The Sequence version of map is "fmap", which comes from the Functor class. The Sequence version of toList is in the Foldable class.

When working with Sequence you also want to refer to the documentation for at least Foldable and Traversable. Functor only has the single method, so we've already covered that.

## 1.1 What do these classes all mean? A brief tour:

### 1.1.1 Functor

A functor is simply a container. Given a container, and a function which works on the elements, we can apply that function to each element. For lists, the familiar "map" does exactly this.

Note that the function can produce elements of a different type, so we may have a different type at the end.

Examples:

Prelude Data.Sequence> map (\n -> replicate n 'a') [1,3,5] ["a","aaa","aaaaa"] Prelude Data.Sequence> fmap (\n -> replicate n 'a') (1 <| 3 <| 5 <| empty) fromList ["a","aaa","aaaaa"]

### 1.1.2 Foldable

A Foldable type is also a container (although the class does not technically require Functor, interesting Foldables are all Functors). It is a container with the added property that its items can be 'folded' to a summary value. In other words, it is a type which supports "foldr".

Once you support foldr, of course, you can be turned into a list, by

usingrepresentation as a list; however the order of the items may or may
not have any particular significance. In particular if a Foldable is
also a Functor, toList and fmap need not perfectly commute; the list
given *after* the fmap may be in a different order to the list
*before* the fmap. In the particular case of Data.Sequence, though,
there *is* a well defined order and it is preserved as expected by
fmap and exposed by toList.

A particular kind of fold well-used by haskell programmers is

### 1.1.3 Traversable

A Traversable type is a kind of upgraded Foldable. Where Foldable gives you the ability to go through the structure processing the elements (foldr) but throwing away the shape, Traversable allows you to do that whilst preserving the shape and, e.g., putting new values in.

Traversable is what we need for"_" versions are in a different typeclass.

## 1.2 Some trickier functions: concatMap and filter

Neither Traversable nor Foldable contain elements for concatMap and filter. That is because Foldable is about tearing down the structure completely, while Traversable is about preserving the structure

exactly as-is. On the other handcut them out.

You can write concatMap for Sequence as follows:

concatMap :: (a -> Seq b) -> Seq a -> Seq b concatMap = foldMap

But why does it work? It works because sequence is an instance of Monoid, where the monoidal operation is "appending". The same definition works for lists, and we can write it more generally as:

concatMap :: (Foldable f, Monoid (f b)) => (a -> f b) -> f a -> f b concatMap = foldMap

And that works with lists and sequences both. Does it work with any Monoid which is Foldable? Only if the Monoid 'means the right

thing'. If you havecondition is stronger than needed; it would be good enough if they were permutations of each other.

it's not really right to bring Applicative in for this, and get:

filter :: (Applicative f, Foldable f, Monoid (f a)) => (a -> Bool) -> f a -> f a filter p = foldMap (\a -> if p a then pure a else mempty)

It's interesting to note that, under these conditions, we have a candidate to help us turn the Foldable into a Monad, since concatMap is a good

definition for## 1.3 Generalising zipWith

Another really useful list combinator that doesn't appear in the interfaces for Sequence, Foldable or Traversable is zipWith. The most general kind of zipWith over Traversables will keep the exact shape of the Traversable on the left, whilst zipping against the values on the right. It turns out you can get away with a Foldable on the right, but you need to use a Monad (or an Applicative, actually) to thread the values through:

import Prelude hiding (sequence) import Data.Sequence import Data.Foldable import Data.Traversable import Control.Applicative data Supply s v = Supply { unSupply :: [s] -> ([s],v) } instance Functor (Supply s) where fmap f av = Supply (\l -> let (l',v) = unSupply av l in (l',f v)) instance Applicative (Supply s) where pure v = Supply (\l -> (l,v)) af <*> av = Supply (\l -> let (l',f) = unSupply af l (l'',v) = unSupply av l' in (l'',f v)) runSupply :: (Supply s v) -> [s] -> v runSupply av l = snd $ unSupply av l supply :: Supply s s supply = Supply (\(x:xs) -> (xs,x)) zipTF :: (Traversable t, Foldable f) => t a -> f b -> t (a,b) zipTF t f = runSupply (traverse (\a -> (,) a <$> supply) t) (toList f) zipWithTF :: (Traversable t,Foldable f) => (a -> b -> c) -> t a -> f b -> t c zipWithTF g t f = runSupply (traverse (\a -> g a <$> supply) t) (toList f) zipWithTFM :: (Traversable t,Foldable f,Monad m) => (a -> b -> m c) -> t a -> f b -> m (t c) zipWithTFM g t f = sequence (zipWithTF g t f) zipWithTFA :: (Traversable t,Foldable f,Applicative m) => (a -> b -> m c) -> t a -> f b -> m (t c) zipWithTFA g t f = sequenceA (zipWithTF g t f)

The code above fails with a pattern match error when the foldable container doesn't have enough input. Here is an alternative version which provides friendlier error reports and makes use of State instead of the self defined Supply monad.

module GenericZip (zipWithTF, zipTF, zipWithTFA, zipWithTFM) where import Data.Foldable import Data.Traversable import qualified Data.Traversable as T import Control.Applicative import Control.Monad.State -- | The state contains the list of values obtained form the foldable container -- and a String indicating the name of the function currectly being executed data ZipState a = ZipState {fName :: String, list :: [a]} -- | State monad containing ZipState type ZipM l a = State (ZipState l) a -- | pops the first element of the list inside the state pop :: ZipM l l pop = do st <- get let xs = list st n = fName st case xs of (a:as) -> do put st{list=as} return a [] -> error $ n ++ ": insufficient input" -- | pop a value form the state and supply it to the second -- argument of a binary function supplySecond :: (a -> b -> c) -> a -> ZipM b c supplySecond f a = do b <- pop return $ f a b zipWithTFError :: (Traversable t,Foldable f) => String -> (a -> b -> c) -> t a -> f b -> t c zipWithTFError str g t f = evalState (T.mapM (supplySecond g) t) (ZipState str (toList f)) zipWithTF :: (Traversable t,Foldable f) => (a -> b -> c) -> t a -> f b -> t c zipWithTF = zipWithTFError "GenericZip.zipWithTF" zipTF :: (Traversable t, Foldable f) => t a -> f b -> t (a,b) zipTF = zipWithTFError "GenericZip.zipTF" (,) zipWithTFM :: (Traversable t,Foldable f,Monad m) => (a -> b -> m c) -> t a -> f b -> m (t c) zipWithTFM g t f = T.sequence (zipWithTFError "GenericZip.zipWithTFM" g t f) zipWithTFA :: (Traversable t,Foldable f,Applicative m) => (a -> b -> m c) -> t a -> f b -> m (t c) zipWithTFA g t f = sequenceA (zipWithTFError "GenericZip.zipWithTFA" g t f)