# Foldable and Traversable

### From HaskellWiki

(Difference between revisions)

m (→Traversable: fix some weird line breaks) |
m (→Foldable: Fixed subjective.) |
||

(4 intermediate revisions by one user not shown) | |||

Line 41: | Line 41: | ||

technically require <hask>Functor</hask>, interesting <hask>Foldable</hask>s are all <hask>Functor</hask>s). 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 "<hask>foldr</hask>". | technically require <hask>Functor</hask>, interesting <hask>Foldable</hask>s are all <hask>Functor</hask>s). 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 "<hask>foldr</hask>". | ||

− | Once you support <hask>foldr</hask>, of course, | + | Once you support <hask>foldr</hask>, of course, it can be turned into a list, by using <hask>toList = foldr (:) []</hask>. This means that all <hask>Foldable</hask>s have a representation as a list, but the order of the items may or may not have any particular significance. However, if a <hask>Foldable</hask> is also a <hask>Functor</hask>, [[parametricity]] and the [[Functor law]] guarantee that <hask>toList</hask> and <hask>fmap</hask> commute. Further, in the case of <hask>Data.Sequence</hask>, there '''is''' a well defined order and it is exposed as expected by <hask>toList</hask>. |

A particular kind of fold well-used by Haskell programmers is <hask>mapM_</hask>, which is a kind of fold over <hask>(>>)</hask>, and <hask>Foldable</hask> provides this along with the related <hask>sequence_</hask>. | A particular kind of fold well-used by Haskell programmers is <hask>mapM_</hask>, which is a kind of fold over <hask>(>>)</hask>, and <hask>Foldable</hask> provides this along with the related <hask>sequence_</hask>. | ||

Line 53: | Line 53: | ||

== Some trickier functions: concatMap and filter == | == Some trickier functions: concatMap and filter == | ||

− | Neither <hask>Traversable</hask> nor <hask>Foldable</hask> contain elements for <hask>concatMap</hask> and <hask>filter</hask>. That is because <hask>Foldable</hask> is about tearing down the structure | + | Neither <hask>Traversable</hask> nor <hask>Foldable</hask> contain elements for <hask>concatMap</hask> and <hask>filter</hask>. That is because <hask>Foldable</hask> is about tearing down the structure completely, while <hask>Traversable</hask> is about preserving the structure exactly as-is. On the other hand <hask>concatMap</hask> tries to 'squeeze more elements in' at a place and <hask>filter</hask> tries to cut them out. |

− | completely, while <hask>Traversable</hask> is about preserving the structure | + | |

− | exactly as-is. On the other hand <hask>concatMap</hask> tries to | + | |

− | 'squeeze more elements in' at a place and <hask>filter</hask> tries to | + | |

− | cut them out. | + | |

You can write <hask>concatMap</hask> for <hask>Sequence</hask> as follows: | You can write <hask>concatMap</hask> for <hask>Sequence</hask> as follows: | ||

Line 66: | Line 62: | ||

</haskell> | </haskell> | ||

− | But why does it work? It works because sequence is an instance of <hask>Monoid</hask>, where the [[monoid]]al operation is "appending". The same | + | But why does it work? It works because sequence is an instance of <hask>Monoid</hask>, where the [[monoid]]al operation is "appending". The same definition works for lists, and we can write it more generally as: |

− | definition works for lists, and we can write it more generally as: | + | |

<haskell> | <haskell> | ||

Line 74: | Line 69: | ||

</haskell> | </haskell> | ||

− | And that works with lists and sequences both. Does it work with any | + | 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 have <hask>toList (f `mappend` g) = toList f ++ toList g</hask> then it definitely makes sense. In fact this easy to write condition is stronger than needed; it would be good enough if they were permutations of each other. |

− | Monoid which is Foldable? Only if the Monoid 'means the right | + | |

− | thing'. If you have <hask>toList (f `mappend` g) = toList f ++ toList g</hask> then it definitely makes sense. In fact this easy to write | + | |

− | condition is stronger than needed; it would be good enough if they | + | |

− | were permutations of each other. | + | |

− | <hask>filter</hask> turns out to be slightly harder still. You need | + | <hask>filter</hask> turns out to be slightly harder still. You need something like 'singleton' (from <hask>Sequence</hask>), or <hask>\a -> [a]</hask> for lists. We can use <hask>pure</hask> from <hask>Applicative</hask>, although it's not really right to bring <hask>Applicative</hask> in for this, and get: |

− | something like 'singleton' (from <hask>Sequence</hask>), or <hask>\a -> [a]</hask> | + | |

− | for lists. We can use <hask>pure</hask> from <hask>Applicative</hask>, although | + | |

− | it's not really right to bring <hask>Applicative</hask> in for this, and get: | + | |

<haskell> | <haskell> | ||

Line 91: | Line 79: | ||

</haskell> | </haskell> | ||

− | It's interesting to note that, under these conditions, we have a candidate | + | It's interesting to note that, under these conditions, we have a candidate to help us turn the <hask>Foldable</hask> into a <hask>Monad</hask>, since <hask>concatMap</hask> is a good definition for <hask>>>=</hask>, and we can use <hask>pure</hask> for <hask>return</hask>. |

− | to help us turn the <hask>Foldable</hask> into a <hask>Monad</hask>, since <hask>concatMap</hask> is a good | + | |

− | definition for <hask>>>=</hask>, and we can use <hask>pure</hask> for <hask>return</hask>. | + | |

== Generalising zipWith == | == Generalising zipWith == | ||

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

− | interfaces for <hask>Sequence</hask>, <hask>Foldable</hask> or <hask>Traversable</hask> is <hask>zipWith</hask>. The most general kind of <hask>zipWith</hask> over <hask>Traversable</hask>s will keep the exact shape of | + | |

− | the <hask>Traversable</hask> on the left, whilst zipping against the values on the right. It turns out you can get away with a <hask>Foldable</hask> on the right, but you need to use a <hask>Monad</hask> (or an <hask>Applicative</hask>, actually) to thread the | + | |

− | values through: | + | |

<haskell> | <haskell> | ||

Line 216: | Line 199: | ||

where map_one (x:xs) y = (xs, g y x) | where map_one (x:xs) y = (xs, g y x) | ||

</haskell> | </haskell> | ||

− | Replace <hask>mapAccumL</hask> with <hask>mapAccumR</hask> and the elements of the Foldable are zipped in reverse order. | + | Replace <hask>mapAccumL</hask> with <hask>mapAccumR</hask> and the elements of the Foldable are zipped in reverse order. Similarly, we can define a generalization of <hask>reverse</hask> on Traversables, which preserves the shape but reverses the left-to-right position of the elements: |

− | Similarly, we can define a generalization of <hask>reverse</hask> on Traversables, which preserves the shape but reverses the left-to-right position of the elements: | + | |

<haskell> | <haskell> | ||

reverseT :: (Traversable t) => t a -> t a | reverseT :: (Traversable t) => t a -> t a | ||

reverseT t = snd (mapAccumR (\ (x:xs) _ -> (xs, x)) (toList t) t) | reverseT t = snd (mapAccumR (\ (x:xs) _ -> (xs, x)) (toList t) t) | ||

</haskell> | </haskell> |

## Revision as of 08:05, 12 September 2012

**Notes on Foldable, Traversable and other useful classes**

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

Data.Sequence is recommended as an efficient alternative to [list]s, 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

toList

The answer to these lies in the long list of instances which Sequence has:

- The Sequence version of map is "", which comes from the Functor class.fmap
- The Sequence version of is in thetoListclass.Foldable

Sequence

Foldable

Traversable

Functor

## Contents |

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

### 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 "Functor

map

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.2 Foldable

AFoldable

Functor

Foldable

Functor

foldr

foldr

toList = foldr (:) []

Foldable

Foldable

Functor

toList

fmap

Data.Sequence

**is**a well defined order and it is exposed as expected by

toList

mapM_

(>>)

Foldable

sequence_

### 1.3 Traversable

ATraversable

Foldable

Foldable

foldr

Traversable

Traversable

mapM

sequence

## 2 Some trickier functions: concatMap and filter

NeitherTraversable

Foldable

concatMap

filter

Foldable

Traversable

concatMap

filter

concatMap

Sequence

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

Monoid

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

toList (f `mappend` g) = toList f ++ toList g

filter

Sequence

\a -> [a]

pure

Applicative

Applicative

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)

Foldable

Monad

concatMap

>>=

pure

return

## 3 Generalising zipWith

Another really useful list combinator that doesn't appear in the interfaces forSequence

Foldable

Traversable

zipWith

zipWith

Traversable

Traversable

Foldable

Monad

Applicative

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)

Foldable

State

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)

Data.Traversable

mapAccumL

mapAccumR

mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)

Using these, the first version above can be written as

zipWithTF :: (Traversable t, Foldable f) => (a -> b -> c) -> t a -> f b -> t c zipWithTF g t f = snd (mapAccumL map_one (toList f) t) where map_one (x:xs) y = (xs, g y x)

mapAccumL

mapAccumR

reverse

reverseT :: (Traversable t) => t a -> t a reverseT t = snd (mapAccumR (\ (x:xs) _ -> (xs, x)) (toList t) t)