# Foldable and Traversable

### From HaskellWiki

(Fix line break. (We really need a better syntax highlighting engine.)) |
m (→Traversable: fix some weird line breaks) |
||

Line 47: | Line 47: | ||

===Traversable=== | ===Traversable=== | ||

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

− | gives you the ability to go through the structure processing the | + | |

− | elements (<hask>foldr</hask>) but throwing away the shape, <hask>Traversable</hask> allows you | + | |

− | to do that whilst preserving the shape and, e.g., putting new values | + | |

− | in. | + | |

− | <hask>Traversable</hask> is what we need for <hask>mapM</hask> and | + | <hask>Traversable</hask> is what we need for <hask>mapM</hask> and <hask>sequence</hask> : note the apparently surprising fact that the "_" versions are in a different [[typeclass]]. |

− | <hask>sequence</hask> : note the apparently surprising fact that the | + | |

− | "_" versions are in a different [[typeclass]]. | + | |

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

## Revision as of 20:35, 20 May 2011

**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 "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

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

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

### 1.3 Traversable

A## 2 Some trickier functions: concatMap and filter

Neithercut them out.

You can writeconcatMap :: (a -> Seq b) -> Seq a -> Seq b concatMap = foldMap

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.

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## 3 Generalising zipWith

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

interfaces forvalues 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)

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)

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)

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