# Foldable and Traversable

### From HaskellWiki

(Difference between revisions)

(Added an alternative implementation of generic zipWith) |
m (→Foldable: Fixed subjective.) |

(18 intermediate revisions by 9 users not shown) |

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