Skip to content

Traversable.md

Latest commit

 

History

History
132 lines (90 loc) · 3.41 KB

Traversable.md

File metadata and controls

132 lines (90 loc) · 3.41 KB

Module Data.Traversable

Traversable

class (Functor t, Foldable t) <= Traversable t where
  traverse :: forall a b m. (Applicative m) => (a -> m b) -> t a -> m (t b)
  sequence :: forall a m. (Applicative m) => t (m a) -> m (t a)

Traversable represents data structures which can be traversed, accumulating results and effects in some Applicative functor.

  • traverse runs an action for every element in a data structure, and accumulates the results.
  • sequence runs the actions contained in a data structure, and accumulates the results.

The traverse and sequence functions should be compatible in the following sense:

  • traverse f xs = sequence (f <$> xs)
  • sequence = traverse id

Traversable instances should also be compatible with the corresponding Foldable instances, in the following sense:

  • foldMap f = runConst <<< traverse (Const <<< f)

Default implementations are provided by the following functions:

  • traverseDefault
  • sequenceDefault
Instances
instance traversableArray :: Traversable Array
instance traversableMaybe :: Traversable Maybe
instance traversableFirst :: Traversable First
instance traversableLast :: Traversable Last
instance traversableAdditive :: Traversable Additive
instance traversableDual :: Traversable Dual
instance traversableConj :: Traversable Conj
instance traversableDisj :: Traversable Disj
instance traversableMultiplicative :: Traversable Multiplicative

traverseDefault

traverseDefault :: forall t a b m. (Traversable t, Applicative m) => (a -> m b) -> t a -> m (t b)

A default implementation of traverse using sequence and map.

sequenceDefault

sequenceDefault :: forall t a m. (Traversable t, Applicative m) => t (m a) -> m (t a)

A default implementation of sequence using traverse.

for

for :: forall a b m t. (Applicative m, Traversable t) => t a -> (a -> m b) -> m (t b)

A version of traverse with its arguments flipped.

This can be useful when running an action written using do notation for every element in a data structure:

For example:

for [1, 2, 3] \n -> do
  print n
  return (n * n)

Accum

type Accum s a = { accum :: s, value :: a }

scanl

scanl :: forall a b f. (Traversable f) => (b -> a -> b) -> b -> f a -> f b

Fold a data structure from the left, keeping all intermediate results instead of only the final result.

mapAccumL

mapAccumL :: forall a b s f. (Traversable f) => (s -> a -> Accum s b) -> s -> f a -> Accum s (f b)

Fold a data structure from the left, keeping all intermediate results instead of only the final result.

Unlike scanl, mapAccumL allows the type of accumulator to differ from the element type of the final data structure.

scanr

scanr :: forall a b f. (Traversable f) => (a -> b -> b) -> b -> f a -> f b

Fold a data structure from the right, keeping all intermediate results instead of only the final result.

mapAccumR

mapAccumR :: forall a b s f. (Traversable f) => (s -> a -> Accum s b) -> s -> f a -> Accum s (f b)

Fold a data structure from the right, keeping all intermediate results instead of only the final result.

Unlike scanr, mapAccumR allows the type of accumulator to differ from the element type of the final data structure.