class (Functor t, Foldable t) => Traversable t where Source

Functors representing data structures that can be transformed to structures of the same shape by performing an Applicative (or, therefore, Monad) action on each element from left to right.

A more detailed description of what same shape means, the various methods, how traversals are constructed, and example advanced use-cases can be found in the Overview section of Data.Traversable.

For the class laws see the Laws section of Data.Traversable.

>>> traverse Just [1,2,3,4]
Just [1,2,3,4]

>>> traverse id [Right 1, Right 2, Right 3, Right 4]
Right [1,2,3,4]

>>> traverse (const Nothing) [1,2,3,4]
Nothing

>>> traverse (\x -> if odd x then Just x else Nothing)  [1,2,3,4]
Nothing

>>> traverse id [Right 1, Right 2, Right 3, Right 4, Left 0]
Left 0

>>> sequenceA [Just 1, Just 2, Just 3]
Just [1,2,3]

>>> sequenceA [Right 1, Right 2, Right 3]
Right [1,2,3]

>>> sequenceA [Just 1, Just 2, Just 3, Nothing]
Nothing

>>> sequenceA [Right 1, Right 2, Right 3, Left 4]
Left 4

>>> sequence $ Right [1,2,3,4]
[Right 1,Right 2,Right 3,Right 4]

>>> sequence $ [Right 1,Right 2,Right 3,Right 4]
Right [1,2,3,4]

>>> sequence $ Left [1,2,3,4]
Left [1,2,3,4]

>>> sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
Left 0

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b) Source

for is traverse with its arguments flipped. For a version that ignores the results see for_.

forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b) Source

forM is mapM with its arguments flipped. For a version that ignores the results see forM_.

mapAccumL :: forall t s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) Source

The mapAccumL function behaves like a combination of fmap and foldl; it applies a function to each element of a structure, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.

Examples

>>> mapAccumL (\a b -> (a + b, a)) 0 [1..10]
(55,[0,1,3,6,10,15,21,28,36,45])

>>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5]
("012345",["0","01","012","0123","01234"])

mapAccumR :: forall t s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) Source

The mapAccumR function behaves like a combination of fmap and foldr; it applies a function to each element of a structure, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new structure.

Examples

>>> mapAccumR (\a b -> (a + b, a)) 0 [1..10]
(55,[54,52,49,45,40,34,27,19,10,0])

>>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5]
("054321",["05432","0543","054","05","0"])

fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b Source

This function may be used as a value for fmap in a Functor instance, provided that traverse is defined. (Using fmapDefault with a Traversable instance defined only by sequenceA will result in infinite recursion.)

fmapDefault f ≡ runIdentity . traverse (Identity . f)

foldMapDefault :: forall t m a. (Traversable t, Monoid m) => (a -> m) -> t a -> m Source

This function may be used as a value for foldMap in a Foldable instance.

foldMapDefault f ≡ getConst . traverse (Const . f)

Traversable structures support element-wise sequencing of Applicative effects (thus also Monad effects) to construct new structures of the same shape as the input.

To illustrate what is meant by same shape, if the input structure is [a], each output structure is a list [b] of the same length as the input. If the input is a Tree a, each output Tree b has the same graph of intermediate nodes and leaves. Similarly, if the input is a 2-tuple (x, a), each output is a 2-tuple (x, b), and so forth.

It is in fact possible to decompose a traversable structure t a into its shape (a.k.a. spine) of type t () and its element list [a]. The original structure can be faithfully reconstructed from its spine and element list.

The implementation of a Traversable instance for a given structure follows naturally from its type; see the Construction section for details. Instances must satisfy the laws listed in the Laws section. The diverse uses of Traversable structures result from the many possible choices of Applicative effects. See the Advanced Traversals section for some examples.

Every Traversable structure is both a Functor and Foldable because it is possible to implement the requisite instances in terms of traverse by using fmapDefault for fmap and foldMapDefault for foldMap. Direct fine-tuned implementations of these superclass methods can in some cases be more efficient.

For an Applicative functor f and a Traversable functor t, the type signatures of traverse and fmap are rather similar:

fmap     :: (a -> f b) -> t a -> t (f b)
traverse :: (a -> f b) -> t a -> f (t b)

The key difference is that fmap produces a structure whose elements (of type f b) are individual effects, while traverse produces an aggregate effect yielding structures of type t b.

For example, when f is the IO monad, and t is List, fmap yields a list of IO actions, whereas traverse constructs an IO action that evaluates to a list of the return values of the individual actions performed left-to-right.

traverse :: (a -> IO b) -> [a] -> IO [b]

The mapM function is a specialisation of traverse to the case when f is a Monad. For monads, mapM is more idiomatic than traverse. The two are otherwise generally identical (though mapM may be specifically optimised for monads, and could be more efficient than using the more general traverse).

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)
mapM     :: (Monad       m, Traversable t) => (a -> m b) -> t a -> m (t b)

When the traversable term is a simple variable or expression, and the monadic action to run is a non-trivial do block, it can be more natural to write the action last. This idiom is supported by for and forM, which are the flipped versions of traverse and mapM, respectively.

The traverse and mapM methods have analogues in the Data.Foldable module. These are traverse_ and mapM_, and their flipped variants for_ and forM_, respectively. The result type is f (), they don't return an updated structure, and can be used to sequence effects over all the elements of a Traversable (any Foldable) structure just for their side-effects.

If the Traversable structure is empty, the result is pure (). When effects short-circuit, the f () result may, for example, be Nothing if f is Maybe, or Left e when it is Either e.

It is perhaps worth noting that Maybe is not only a potential Applicative functor for the return value of the first argument of traverse, but is also itself a Traversable structure with either zero or one element. A convenient idiom for conditionally executing an action just for its effects on a Just value, and doing nothing otherwise is:

-- action :: Monad m => a -> m ()
-- mvalue :: Maybe a
mapM_ action mvalue -- :: m ()

which is more concise than:

maybe (return ()) action mvalue

The mapM_ idiom works verbatim if the type of mvalue is later refactored from Maybe a to Either e a (assuming it remains OK to silently do nothing in the Left case).

When traverse or mapM is applied to an empty structure ts (one for which null ts is True) the return value is pure ts regardless of the provided function g :: a -> f b. It is not possible to apply the function when no values of type a are available, but its type determines the relevant instance of pure.

null ts ==> traverse g ts == pure ts

Otherwise, when ts is non-empty and at least one value of type b results from each f a, the structures t b have the same shape (list length, graph of tree nodes, ...) as the input structure t a, but the slots previously occupied by elements of type a now hold elements of type b.

A single traversal may produce one, zero or many such structures. The zero case happens when one of the effects f a sequenced as part of the traversal yields no replacement values. Otherwise, the many case happens when one of sequenced effects yields multiple values.

The traverse function does not perform selective filtering of slots in the output structure as with e.g. mapMaybe.

>>> let incOdd n = if odd n then Just $ n + 1 else Nothing
>>> mapMaybe incOdd [1, 2, 3]
[2,4]
>>> traverse incOdd [1, 3, 5]
Just [2,4,6]
>>> traverse incOdd [1, 2, 3]
Nothing

In the above examples, with Maybe as the Applicative f, we see that the number of t b structures produced by traverse may differ from one: it is zero when the result short-circuits to Nothing. The same can happen when f is List and the result is [], or f is Either e and the result is Left (x :: e), or perhaps the empty value of some Alternative functor.

When f is e.g. List, and the map g :: a -> [b] returns more than one value for some inputs a (and at least one for all a), the result of mapM g ts will contain multiple structures of the same shape as ts:

length (mapM g ts) == product (fmap (length . g) ts)

For example:

>>> length $ mapM (\n -> [1..n]) [1..6]
720
>>> product $ length . (\n -> [1..n]) <$> [1..6]
720

In other words, a traversal with a function g :: a -> [b], over an input structure t a, yields a list [t b], whose length is the product of the lengths of the lists that g returns for each element of the input structure! The individual elements a of the structure are replaced by each element of g a in turn:

>>> mapM (\n -> [1..n]) $ Just 3
[Just 1,Just 2,Just 3]
>>> mapM (\n -> [1..n]) [1..3]
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3]]

If any element of the structure t a is mapped by g to an empty list, then the entire aggregate result is empty, because no value is available to fill one of the slots of the output structure:

>>> mapM (\n -> [