# Foldable and Traversable

### From HaskellWiki

## Revision as of 13:48, 21 January 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

method, so we've already covered that.

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

Acan be 'folded' to a summary value. In other words, it is a type which

supports "representation as a list, but the order of the items may or may

not have any particular significance. However, if a**is**a well defined order and it is exposed as expected by

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

### 1.3 Traversable

Agives you the ability to go through the structure processing the

elements (to do that whilst preserving the shape and, e.g., putting new values in.

"_" versions are in a different typeclass.

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