Copyright | Conor McBride and Ross Paterson 2005 |
---|---|
License | BSD-style (see the LICENSE file in the distribution) |
Maintainer | libraries@haskell.org |
Stability | experimental |
Portability | portable |
Safe Haskell | Trustworthy |
Language | Haskell2010 |
Class of data structures that can be traversed from left to right, performing an action on each element. Instances are expected to satisfy the listed laws.
Synopsis
- class (Functor t, Foldable t) => Traversable t where
- traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
- sequenceA :: Applicative f => t (f a) -> f (t a)
- mapM :: Monad m => (a -> m b) -> t a -> m (t b)
- sequence :: Monad m => t (m a) -> m (t a)
- for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
- forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
- mapAccumL :: forall t s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
- mapAccumR :: forall t s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
- fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b
- foldMapDefault :: forall t m a. (Traversable t, Monoid m) => (a -> m) -> t a -> m
The Traversable
class
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 :: Applicative f => (a -> f b) -> t a -> f (t b) Source #
Map each element of a structure to an action, evaluate these actions
from left to right, and collect the results. For a version that ignores
the results see traverse_
.
Examples
Basic usage:
In the first two examples we show each evaluated action mapping to the output structure.
>>>
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]
In the next examples, we show that Nothing
and Left
values short
circuit the created structure.
>>>
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 :: Applicative f => t (f a) -> f (t a) Source #
Evaluate each action in the structure from left to right, and
collect the results. For a version that ignores the results
see sequenceA_
.
Examples
Basic usage:
For the first two examples we show sequenceA fully evaluating a a structure and collecting the results.
>>>
sequenceA [Just 1, Just 2, Just 3]
Just [1,2,3]
>>>
sequenceA [Right 1, Right 2, Right 3]
Right [1,2,3]
The next two example show Nothing
and Just
will short circuit
the resulting structure if present in the input. For more context,
check the Traversable
instances for Either
and Maybe
.
>>>
sequenceA [Just 1, Just 2, Just 3, Nothing]
Nothing
>>>
sequenceA [Right 1, Right 2, Right 3, Left 4]
Left 4
mapM :: Monad m => (a -> m b) -> t a -> m (t b) Source #
Map each element of a structure to a monadic action, evaluate
these actions from left to right, and collect the results. For
a version that ignores the results see mapM_
.
Examples
sequence :: Monad m => t (m a) -> m (t a) Source #
Evaluate each monadic action in the structure from left to
right, and collect the results. For a version that ignores the
results see sequence_
.
Examples
Basic usage:
The first two examples are instances where the input and
and output of sequence
are isomorphic.
>>>
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]
The following examples demonstrate short circuit behavior
for sequence
.
>>>
sequence $ Left [1,2,3,4]
Left [1,2,3,4]
>>>
sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
Left 0
Instances
Traversable ZipList Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
Traversable Complex Source # | Since: base-4.9.0.0 |
Defined in Data.Complex | |
Traversable Identity Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
Traversable First Source # | Since: base-4.8.0.0 |
Traversable Last Source # | Since: base-4.8.0.0 |
Traversable Down Source # | Since: base-4.12.0.0 |
Traversable First Source # | Since: base-4.9.0.0 |
Traversable Last Source # | Since: base-4.9.0.0 |
Traversable Max Source # | Since: base-4.9.0.0 |
Traversable Min Source # | Since: base-4.9.0.0 |
Traversable Dual Source # | Since: base-4.8.0.0 |
Traversable Product Source # | Since: base-4.8.0.0 |
Defined in Data.Traversable | |
Traversable Sum Source # | Since: base-4.8.0.0 |
Traversable Par1 Source # | Since: base-4.9.0.0 |
Traversable NonEmpty Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
Traversable Maybe Source # | Since: base-2.1 |
Traversable Solo Source # | Since: base-4.15 |
Traversable [] Source # | Since: base-2.1 |
Traversable (Either a) Source # | Since: base-4.7.0.0 |
Defined in Data.Traversable | |
Traversable (Proxy :: Type -> Type) Source # | Since: base-4.7.0.0 |
Traversable (Arg a) Source # | Since: base-4.9.0.0 |
Ix i => Traversable (Array i) Source # | Since: base-2.1 |
Defined in Data.Traversable | |
Traversable (U1 :: Type -> Type) Source # | Since: base-4.9.0.0 |
Traversable (UAddr :: Type -> Type) Source # | Since: base-4.9.0.0 |
Traversable (UChar :: Type -> Type) Source # | Since: base-4.9.0.0 |
Traversable (UDouble :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
Traversable (UFloat :: Type -> Type) Source # | Since: base-4.9.0.0 |
Traversable (UInt :: Type -> Type) Source # | Since: base-4.9.0.0 |
Traversable (UWord :: Type -> Type) Source # | Since: base-4.9.0.0 |
Traversable (V1 :: Type -> Type) Source # | Since: base-4.9.0.0 |
Traversable ((,) a) Source # | Since: base-4.7.0.0 |
Traversable (Const m :: Type -> Type) Source # | Since: base-4.7.0.0 |
Defined in Data.Traversable | |
Traversable f => Traversable (Ap f) Source # | Since: base-4.12.0.0 |
Traversable f => Traversable (Alt f) Source # | Since: base-4.12.0.0 |
Traversable f => Traversable (Rec1 f) Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
(Traversable f, Traversable g) => Traversable (Product f g) Source # | Since: base-4.9.0.0 |
Defined in Data.Functor.Product traverse :: Applicative f0 => (a -> f0 b) -> Product f g a -> f0 (Product f g b) Source # sequenceA :: Applicative f0 => Product f g (f0 a) -> f0 (Product f g a) Source # mapM :: Monad m => (a -> m b) -> Product f g a -> m (Product f g b) Source # sequence :: Monad m => Product f g (m a) -> m (Product f g a) Source # | |
(Traversable f, Traversable g) => Traversable (Sum f g) Source # | Since: base-4.9.0.0 |
Defined in Data.Functor.Sum | |
(Traversable f, Traversable g) => Traversable (f :*: g) Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
(Traversable f, Traversable g) => Traversable (f :+: g) Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
Traversable (K1 i c :: Type -> Type) Source # | Since: base-4.9.0.0 |
(Traversable f, Traversable g) => Traversable (Compose f g) Source # | Since: base-4.9.0.0 |
Defined in Data.Functor.Compose traverse :: Applicative f0 => (a -> f0 b) -> Compose f g a -> f0 (Compose f g b) Source # sequenceA :: Applicative f0 => Compose f g (f0 a) -> f0 (Compose f g a) Source # mapM :: Monad m => (a -> m b) -> Compose f g a -> m (Compose f g b) Source # sequence :: Monad m => Compose f g (m a) -> m (Compose f g a) Source # | |
(Traversable f, Traversable g) => Traversable (f :.: g) Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable | |
Traversable f => Traversable (M1 i c f) Source # | Since: base-4.9.0.0 |
Defined in Data.Traversable |
Utility functions
for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b) Source #
forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b) Source #
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
Basic usage:
>>>
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
Basic usage:
>>>
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"])
General definitions for superclass methods
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 #
Overview
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.
The traverse
and mapM
methods
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.
Their Foldable
, just the effects, analogues.
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
when it is Left
e
.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).
Result multiplicity
When traverse
or mapM
is applied to an empty structure ts
(one for
which
is null
tsTrue
) 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 -> [1..n]) $ [0..6] -- [1..0] is empty
[]
The sequenceA
and sequence
methods
The sequenceA
and sequence
methods are useful when what you have is a
container of pending applicative or monadic effects, and you want to combine
them into a single effect that produces zero or more containers with the
computed values.
sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a) sequence :: (Monad m, Traversable t) => t (m a) -> m (t a) sequenceA = traverse id -- default definition sequence = sequenceA -- default definition
When the monad m
is IO
, applying sequence
to a list of
IO actions, performs each in turn, returning a list of the results:
sequence [putStr "Hello ", putStrLn "World!"] = (\a b -> [a,b]) <$> putStr "Hello " <*> putStrLn "World!" = do u1 <- putStr "Hello " u2 <- putStrLn "World!" return [u1, u2] -- In this case [(), ()]
For sequenceA
, the non-deterministic behaviour of List
is most easily
seen in the case of a list of lists (of elements of some common fixed type).
The result is a cross-product of all the sublists:
>>>
sequenceA [[0, 1, 2], [30, 40], [500]]
[[0,30,500],[0,40,500],[1,30,500],[1,40,500],[2,30,500],[2,40,500]]
Because the input list has three (sublist) elements, the result is a list of triples (same shape).
Care with default method implementations
The traverse
method has a default implementation in terms of sequenceA
:
traverse g = sequenceA . fmap g
but relying on this default implementation is not recommended, it requires
that the structure is already independently a Functor
. The definition of
sequenceA
in terms of traverse id
is much simpler than traverse
expressed via a composition of sequenceA
and fmap
. Instances should
generally implement traverse
explicitly. It may in some cases also make
sense to implement a specialised mapM
.
Because fmapDefault
is defined in terms of traverse
(whose default
definition in terms of sequenceA
uses fmap
), you must not use
fmapDefault
to define the Functor
instance if the Traversable
instance
directly defines only sequenceA
.
Monadic short circuits
When the monad m
is Either
or Maybe
(more generally any
MonadPlus
), the effect in question is to short-circuit the
result on encountering Left
or Nothing
(more generally
mzero
).
>>>
sequence [Just 1,Just 2,Just 3]
Just [1,2,3]>>>
sequence [Just 1,Nothing,Just 3]
Nothing>>>
sequence [Right 1,Right 2,Right 3]
Right [1,2,3]>>>
sequence [Right 1,Left "sorry",Right 3]
Left "sorry"
The result of sequence
is all-or-nothing, either structures of exactly the
same shape as the input or none at all. The sequence
function does not
perform selective filtering as with e.g. catMaybes
or
rights
:
>>>
catMaybes [Just 1,Nothing,Just 3]
[1,3]>>>
rights [Right 1,Left "sorry",Right 3]
[1,3]
Example binary tree instance
The definition of a Traversable
instance for a binary tree is rather
similar to the corresponding instance of Functor
, given the data type:
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
a canonical Functor
instance would be
instance Functor Tree where fmap g Empty = Empty fmap g (Leaf x) = Leaf (g x) fmap g (Node l k r) = Node (fmap g l) (g k) (fmap g r)
a canonical Traversable
instance would be
instance Traversable Tree where traverse g Empty = pure Empty traverse g (Leaf x) = Leaf <$> g x traverse g (Node l k r) = Node <$> traverse g l <*> g k <*> traverse g r
This definition works for any g :: a -> f b
, with f
an
Applicative functor, as the laws for (
imply the requisite
associativity.<*>
)
We can add an explicit non-default mapM
if desired:
mapM g Empty = return Empty mapM g (Leaf x) = Leaf <$> g x mapM g (Node l k r) = do ml <- mapM g l mk <- g k mr <- mapM g r return $ Node ml mk mr
See Construction below for a more detailed exploration of
the general case, but as mentioned in Overview above, instance
definitions are typically rather simple, all the interesting behaviour is a
result of an interesting choice of Applicative
functor for a traversal.
Pre-order and post-order tree traversal
It is perhaps worth noting that the traversal defined above gives an in-order sequencing of the elements. If instead you want either pre-order (parent first, then child nodes) or post-order (child nodes first, then parent) sequencing, you can define the instance accordingly:
inOrderNode :: Tree a -> a -> Tree a -> Tree a inOrderNode l x r = Node l x r preOrderNode :: a -> Tree a -> Tree a -> Tree a preOrderNode x l r = Node l x r postOrderNode :: Tree a -> Tree a -> a -> Tree a postOrderNode l r x = Node l x r -- Traversable instance with in-order traversal instance Traversable Tree where traverse g t = case t of Empty -> pure Empty Leaf x -> Leaf <$> g x Node l x r -> inOrderNode <$> traverse g l <*> g x <*> traverse g r -- Traversable instance with pre-order traversal instance Traversable Tree where traverse g t = case t of Empty -> pure Empty Leaf x -> Leaf <$> g x Node l x r -> preOrderNode <$> g x <*> traverse g l <*> traverse g r -- Traversable instance with post-order traversal instance Traversable Tree where traverse g t = case t of Empty -> pure Empty Leaf x -> Leaf <$> g x Node l x r -> postOrderNode <$> traverse g l <*> traverse g r <*> g x
Since the same underlying Tree structure is used in all three cases, it is
possible to use newtype
wrappers to make all three available at the same
time! The user need only wrap the root of the tree in the appropriate
newtype
for the desired traversal order. Tne associated instance
definitions are shown below (see coercion if unfamiliar with
the use of coerce
in the sample code):
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-} -- Default in-order traversal import Data.Coerce (coerce) import Data.Traversable data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) instance Functor Tree where fmap = fmapDefault instance Foldable Tree where foldMap = foldMapDefault instance Traversable Tree where traverse _ Empty = pure Empty traverse g (Leaf a) = Leaf <$> g a traverse g (Node l a r) = Node <$> traverse g l <*> g a <*> traverse g r -- Optional pre-order traversal newtype PreOrderTree a = PreOrderTree (Tree a) instance Functor PreOrderTree where fmap = fmapDefault instance Foldable PreOrderTree where foldMap = foldMapDefault instance Traversable PreOrderTree where traverse _ (PreOrderTree Empty) = pure $ preOrderEmpty traverse g (PreOrderTree (Leaf x)) = preOrderLeaf <$> g x traverse g (PreOrderTree (Node l x r)) = preOrderNode <$> g x <*> traverse g (coerce l) <*> traverse g (coerce r) preOrderEmpty :: forall a. PreOrderTree a preOrderEmpty = coerce (Empty @a) preOrderLeaf :: forall a. a -> PreOrderTree a preOrderLeaf = coerce (Leaf @a) preOrderNode :: a -> PreOrderTree a -> PreOrderTree a -> PreOrderTree a preOrderNode x l r = coerce (Node (coerce l) x (coerce r)) -- Optional post-order traversal newtype PostOrderTree a = PostOrderTree (Tree a) instance Functor PostOrderTree where fmap = fmapDefault instance Foldable PostOrderTree where foldMap = foldMapDefault instance Traversable PostOrderTree where traverse _ (PostOrderTree Empty) = pure postOrderEmpty traverse g (PostOrderTree (Leaf x)) = postOrderLeaf <$> g x traverse g (PostOrderTree (Node l x r)) = postOrderNode <$> traverse g (coerce l) <*> traverse g (coerce r) <*> g x postOrderEmpty :: forall a. PostOrderTree a postOrderEmpty = coerce (Empty @a) postOrderLeaf :: forall a. a -> PostOrderTree a postOrderLeaf = coerce (Leaf @a) postOrderNode :: PostOrderTree a -> PostOrderTree a -> a -> PostOrderTree a postOrderNode l r x = coerce (Node (coerce l) x (coerce r))
With the above, given a sample tree:
inOrder :: Tree Int inOrder = Node (Node (Leaf 10) 3 (Leaf 20)) 5 (Leaf 42)
we have:
import Data.Foldable (toList) print $ toList inOrder [10,3,20,5,42] print $ toList (coerce inOrder :: PreOrderTree Int) [5,3,10,20,42] print $ toList (coerce inOrder :: PostOrderTree Int) [10,20,3,42,5]
You would typically define instances for additional common type classes,
such as Eq
, Ord
, Show
, etc.
Making construction intuitive
In order to be able to reason about how a given type of Applicative
effects will be sequenced through a general Traversable
structure by its
traversable
and related methods, it is helpful to look more closely
at how a general traverse
method is implemented. We'll look at how
general traversals are constructed primarily with a view to being able
to predict their behaviour as a user, even if you're not defining your
own Traversable
instances.
Traversable structures t a
are assembled incrementally from their
constituent parts, perhaps by prepending or appending individual elements of
type a
, or, more generally, by recursively combining smaller composite
traversable building blocks that contain multiple such elements.
As in the tree example above, the components being combined are typically pieced together by a suitable constructor, i.e. a function taking two or more arguments that returns a composite value.
The traverse
method enriches simple incremental construction with
threading of Applicative
effects of some function g :: a -> f b
.
The basic building blocks we'll use to model the construction of traverse
are a hypothetical set of elementary functions, some of which may have
direct analogues in specific Traversable
structures. For example, the
(
constructor is an analogue for lists of :
)prepend
or the more
general combine
.
empty :: t a -- build an empty container singleton :: a -> t a -- build a one-element container prepend :: a -> t a -> t a -- extend by prepending a new initial element append :: t a -> a -> t a -- extend by appending a new final element combine :: a1 -> a2 -> ... -> an -> t a -- combine multiple inputs
An empty structure has no elements of type
a
, so there's nothing to whichg
can be applied, but since we need an output of typef (t b)
, we just use thepure
instance off
to wrap an empty of typet b
:traverse _ (empty :: t a) = pure (empty :: t b)
With the List monad, empty is
[]
, while withMaybe
it isNothing
. WithEither e a
we have an empty case for each value ofe
:traverse _ (Left e :: Either e a) = pure $ (Left e :: Either e b)
A singleton structure has just one element of type
a
, andtraverse
can take thata
, applyg :: a -> f b
getting anf b
, thenfmap singleton
over that, getting anf (t b)
as required:traverse g (singleton a) = fmap singleton $ g a
Note that if
f
isList
andg
returns multiple values the result will be a list of multiplet b
singletons!Since
Maybe
andEither
are either empty or singletons, we havetraverse _ Nothing = pure Nothing traverse g (Just a) = Just <$> g a
traverse _ (Left e) = pure (Left e) traverse g (Right a) = Right <$> g a
For
List
, empty is[]
andsingleton
is(:[])
, so we have:traverse _ [] = pure [] traverse g [a] = fmap (:[]) (g a) = (:) <$> (g a) <*> traverse g [] = liftA2 (:) (g a) (traverse g [])
When the structure is built by adding one more element via
prepend
orappend
, traversal amounts to:traverse g (prepend a t0) = prepend <$> (g a) <*> traverse g t0 = liftA2 prepend (g a) (traverse g t0)
traverse g (append t0 a) = append <$> traverse g t0 <*> g a = liftA2 append (traverse g t0) (g a)
The origin of the combinatorial product when
f
isList
should now be apparent, whentraverse g t0
hasn
elements andg a
hasm
elements, the non-deterministicApplicative
instance ofList
will produce a result withm * n
elements.When combining larger building blocks, we again use
(
to combine the traversals of the components. With bare elements<*>
)a
mapped tof b
viag
, and composite traversable sub-structures transformed viatraverse g
:traverse g (combine a1 a2 ... an) = combine <$> t1 <*> t2 <*> ... <*> tn where t1 = g a1 -- if a1 fills a slot of type @a@ = traverse g a1 -- if a1 is a traversable substructure ... ditto for the remaining constructor arguments ...
The above definitions sequence the Applicative
effects of f
in the
expected order while producing results of the expected shape t
.
For lists this becomes:
traverse g [] = pure [] traverse g (x:xs) = liftA2 (:) (g a) (traverse g xs)
The actual definition of traverse
for lists is an equivalent
right fold in order to facilitate list fusion.
traverse g = foldr (\x r -> liftA2 (:) (g x) r) (pure [])
Advanced traversals
In the sections below we'll examine some advanced choices of Applicative
effects that give rise to very different transformations of Traversable
structures.
These examples cover the implementations of fmapDefault
, foldMapDefault
,
mapAccumL
and mapAccumR
functions illustrating the use of Identity
,
Const
and stateful Applicative
effects. The ZipList example
illustrates the use of a less-well known Applicative
instance for lists.
This is optional material, which is not essential to a basic understanding of
Traversable
structures. If this is your first encounter with Traversable
structures, you can come back to these at a later date.
Coercion
Some of the examples make use of an advanced Haskell feature, namely
newtype
coercion. This is done for two reasons:
- Use of
coerce
makes it possible to avoid cluttering the code with functions that wrap and unwrap newtype terms, which at runtime are indistinguishable from the underlying value. Coercion is particularly convenient when one would have to otherwise apply multiple newtype constructors to function arguments, and then peel off multiple layers of same from the function output. - Use of
coerce
can produce more efficient code, by reusing the original value, rather than allocating space for a wrapped clone.
If you're not familiar with coerce
, don't worry, it is just a shorthand
that, e.g., given:
newtype Foo a = MkFoo { getFoo :: a } newtype Bar a = MkBar { getBar :: a } newtype Baz a = MkBaz { getBaz :: a } f :: Baz Int -> Bar (Foo String)
makes it possible to write:
x :: Int -> String x = coerce f
instead of
x = getFoo . getBar . f . MkBaz
Identity: the fmapDefault
function
The simplest Applicative functor is Identity
, which just wraps and unwraps
pure values and function application. This allows us to define
fmapDefault
:
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-} import Data.Coercible (coerce) fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b fmapDefault = coerce (traverse @t @Identity @a @b)
The use of coercion avoids the need to explicitly wrap and
unwrap terms via Identity
and runIdentity
.
As noted in Overview, fmapDefault
can only be used to define
the requisite Functor
instance of a Traversable
structure when the
traverse
method is explicitly implemented. An infinite loop would result
if in addition traverse
were defined in terms of sequenceA
and fmap
.
State: the mapAccumL
, mapAccumR
functions
Applicative functors that thread a changing state through a computation are
an interesting use-case for traverse
. The mapAccumL
and mapAccumR
functions in this module are each defined in terms of such traversals.
We first define a simplified (not a monad transformer) version of
State
that threads a state s
through a
chain of computations left to right. Its (
operator passes the
input state first to its left argument, and then the resulting state is
passed to its right argument, which returns the final state.<*>
)
newtype StateL s a = StateL { runStateL :: s -> (s, a) } instance Functor (StateL s) where fmap f (StateL kx) = StateL $ \ s -> let (s', x) = kx s in (s', f x) instance Applicative (StateL s) where pure a = StateL $ \s -> (s, a) (StateL kf) <*> (StateL kx) = StateL $ \ s -> let { (s', f) = kf s ; (s'', x) = kx s' } in (s'', f x) liftA2 f (StateL kx) (StateL ky) = StateL $ \ s -> let { (s', x) = kx s ; (s'', y) = ky s' } in (s'', f x y)
With StateL
, we can define mapAccumL
as follows:
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-} mapAccumL :: forall t s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) mapAccumL g s ts = coerce (traverse @t @(StateL s) @a @b) (flip g) ts s
The use of coercion avoids the need to explicitly wrap and
unwrap newtype
terms.
The type of flip g
is coercible to a -> StateL b
, which makes it
suitable for use with traverse
. As part of the Applicative
construction of StateL (t b)
the state updates will
thread left-to-right along the sequence of elements of t a
.
While mapAccumR
has a type signature identical to mapAccumL
, it differs
in the expected order of evaluation of effects, which must take place
right-to-left.
For this we need a variant control structure StateR
, which threads the
state right-to-left, by passing the input state to its right argument and
then using the resulting state as an input to its left argument:
newtype StateR s a = StateR { runStateR :: s -> (s, a) } instance Functor (StateR s) where fmap f (StateR kx) = StateR $ \s -> let (s', x) = kx s in (s', f x) instance Applicative (StateR s) where pure a = StateR $ \s -> (s, a) (StateR kf) <*> (StateR kx) = StateR $ \ s -> let { (s', x) = kx s ; (s'', f) = kf s' } in (s'', f x) liftA2 f (StateR kx) (StateR ky) = StateR $ \ s -> let { (s', y) = ky s ; (s'', x) = kx s' } in (s'', f x y)
With StateR
, we can define mapAccumR
as follows:
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-} mapAccumR :: forall t s a b. Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) mapAccumR g s0 ts = coerce (traverse @t @(StateR s) @a @b) (flip g) ts s0
The use of coercion avoids the need to explicitly wrap and
unwrap newtype
terms.
Various stateful traversals can be constructed from mapAccumL
and
mapAccumR
for suitable choices of g
, or built directly along similar
lines.
Const: the foldMapDefault
function
The Const
Functor enables applications of traverse
that summarise the
input structure to an output value without constructing any output values
of the same type or shape.
As noted above, the Foldable
superclass constraint is
justified by the fact that it is possible to construct foldMap
, foldr
,
etc., from traverse
. The technique used is useful in its own right, and
is explored below.
A key feature of folds is that they can reduce the input structure to a summary value. Often neither the input structure nor a mutated clone is needed once the fold is computed, and through list fusion the input may not even have been memory resident in its entirety at the same time.
The traverse
method does not at first seem to be a suitable building block
for folds, because its return value f (t b)
appears to retain mutated
copies of the input structure. But the presence of t b
in the type
signature need not mean that terms of type t b
are actually embedded
in f (t b)
. The simplest way to elide the excess terms is by basing
the Applicative functor used with traverse
on Const
.
Not only does Const a b
hold just an a
value, with the b
parameter merely a phantom type, but when m
has a Monoid
instance,
Const m
is an Applicative
functor:
import Data.Coerce (coerce) newtype Const a b = Const { getConst :: a } deriving (Eq, Ord, Show) -- etc. instance Functor (Const m) where fmap = const coerce instance Monoid m => Applicative (Const m) where pure _ = Const mempty (<*>) = coerce (mappend :: m -> m -> m) liftA2 _ = coerce (mappend :: m -> m -> m)
The use of coercion avoids the need to explicitly wrap and
unwrap newtype
terms.
We can therefore define a specialisation of traverse
:
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-} traverseC :: forall t a m. (Monoid m, Traversable t) => (a -> Const m ()) -> t a -> Const m (t ()) traverseC = traverse @t @(Const m) @a @()
For which the Applicative construction of traverse
leads to:
null ts ==> traverseC g ts = Const mempty
traverseC g (prepend x xs) = Const (g x) <> traverseC g xs
In other words, this makes it possible to define:
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-} foldMapDefault :: forall t a m. (Monoid m, Traversable t) => (a -> m) -> t a -> m foldMapDefault = coerce (traverse @t @(Const m) @a @())
Which is sufficient to define a Foldable
superclass instance:
The use of coercion avoids the need to explicitly wrap and
unwrap newtype
terms.
instance Traversable t => Foldable t where foldMap = foldMapDefault
It may however be instructive to also directly define candidate default
implementations of foldr
and foldl'
, which take a bit more machinery
to construct:
{-# LANGUAGE ScopedTypeVariables, TypeApplications #-} import Data.Coerce (coerce) import Data.Functor.Const (Const(..)) import Data.Semigroup (Dual(..), Endo(..)) import GHC.Exts (oneShot) foldrDefault :: forall t a b. Traversable t => (a -> b -> b) -> b -> t a -> b foldrDefault f z = \t -> coerce (traverse @t @(Const (Endo b)) @a @()) f t z foldlDefault' :: forall t a b. Traversable t => (b -> a -> b) -> b -> t a -> b foldlDefault' f z = \t -> coerce (traverse @t @(Const (Dual (Endo b))) @a @()) f' t z where f' :: a -> b -> b f' a = oneShot $ \ b -> b `seq` f b a
In the above we're using the Endo
bMonoid
and its
Dual
to compose a sequence of b -> b
accumulator updates in either
left-to-right or right-to-left order.
The use of seq
in the definition of foldlDefault'
ensures strictness
in the accumulator.
The use of coercion avoids the need to explicitly wrap and
unwrap newtype
terms.
The oneShot
function gives a hint to the compiler that aids in
correct optimisation of lambda terms that fire at most once (for each
element a
) and so should not try to pre-compute and re-use
subexpressions that pay off only on repeated execution. Otherwise, it is
just the identity function.
ZipList: transposing lists of lists
As a warm-up for looking at the ZipList
Applicative
functor, we'll first
look at a simpler analogue. First define a fixed width 2-element Vec2
type, whose Applicative
instance combines a pair of functions with a pair of
values by applying each function to the corresponding value slot:
data Vec2 a = Vec2 a a instance Functor Vec2 where fmap f (Vec2 a b) = Vec2 (f a) (f b) instance Applicative Vec2 where pure x = Vec2 x x liftA2 f (Vec2 a b) (Vec2 p q) = Vec2 (f a p) (f b q) instance Foldable Vec2 where foldr f z (Vec2 a b) = f a (f b z) foldMap f (Vec2 a b) = f a <> f b instance Traversable Vec2 where traverse f (Vec2 a b) = Vec2 <$> f a <*> f b
Along with a similar definition for fixed width 3-element vectors:
data Vec3 a = Vec3 a a a instance Functor Vec3 where fmap f (Vec3 x y z) = Vec3 (f x) (f y) (f z) instance Applicative Vec3 where pure x = Vec3 x x x liftA2 f (Vec3 p q r) (Vec3 x y z) = Vec3 (f p x) (f q y) (f r z) instance Foldable Vec3 where foldr f z (Vec3 a b c) = f a (f b (f c z)) foldMap f (Vec3 a b c) = f a <> f b <> f c instance Traversable Vec3 where traverse f (Vec3 a b c) = Vec3 <$> f a <*> f b <*> f c
With the above definitions,
(same as sequenceA
) acts
as a matrix transpose operation on traverse
id
Vec2 (Vec3 Int)
producing a
corresponding Vec3 (Vec2 Int)
:
Let t = Vec2 (Vec3 1 2 3) (Vec3 4 5 6)
be our Traversable
structure,
and g = id :: Vec3 Int -> Vec3 Int
be the function used to traverse
t
. We then have:
traverse g t = Vec2 <$> (Vec3 1 2 3) <*> (Vec3 4 5 6) = Vec3 (Vec2 1 4) (Vec2 2 5) (Vec2 3 6)
This construction can be generalised from fixed width vectors to variable
length lists via ZipList
. This gives a transpose
operation that works well for lists of equal length. If some of the lists
are longer than others, they're truncated to the longest common length.
We've already looked at the standard Applicative
instance of List
for
which applying m
functions f1, f2, ..., fm
to n
input
values a1, a2, ..., an
produces m * n
outputs:
>>>
:set -XTupleSections
>>>
[("f1",), ("f2",), ("f3",)] <*> [1,2]
[("f1",1),("f1",2),("f2",1),("f2",2),("f3",1),("f3",2)]
There are however two more common ways to turn lists into Applicative
control structures. The first is via
, since lists are
monoids under concatenation, and we've already seen that Const
[a]
is
an Const
mApplicative
functor when m
is a Monoid
. The second, is based
on zipWith
, and is called ZipList
:
{-# LANGUAGE GeneralizedNewtypeDeriving #-} newtype ZipList a = ZipList { getZipList :: [a] } deriving (Show, Eq, ..., Functor) instance Applicative ZipList where liftA2 f (ZipList xs) (ZipList ys) = ZipList $ zipWith f xs ys pure x = repeat x
The liftA2
definition is clear enough, instead of applying f
to each
pair (x, y)
drawn independently from the xs
and ys
, only
corresponding pairs at each index in the two lists are used.
The definition of pure
may look surprising, but it is needed to ensure
that the instance is lawful:
liftA2 f (pure x) ys == fmap (f x) ys
Since ys
can have any length, we need to provide an infinite supply
of x
values in pure x
in order to have a value to pair with
each element y
.
When ZipList
is the Applicative
functor used in the
construction of a traversal, a ZipList holding a partially
built structure with m
elements is combined with a component holding
n
elements via zipWith
, resulting in min m n
outputs!
Therefore traverse
with g :: a -> ZipList b
will produce a ZipList
of t b
structures whose element count is the minimum length of the
ZipLists g a
with a
ranging over the elements of t
. When
t
is empty, the length is infinite (as expected for a minimum of an
empty set).
If the structure t
holds values of type ZipList a
, we can use
the identity function id :: ZipList a -> ZipList a
for the first
argument of traverse
:
traverse (id :: ZipList a -> ZipList a) :: t (ZipList a) -> ZipList (t a)
The number of elements in the output ZipList
will be the length of the
shortest ZipList
element of t
. Each output t a
will have the
same shape as the input t (ZipList a)
, i.e. will share its number of
elements.
If we think of the elements of t (ZipList a)
as its rows, and the
elements of each individual ZipList
as the columns of that row, we see
that our traversal implements a transpose operation swapping the rows
and columns of t
, after first truncating all the rows to the column
count of the shortest one.
Since in fact
is just traverse
idsequenceA
the above boils down
to a rather concise definition of transpose, with coercion
used to implicily wrap and unwrap the ZipList
newtype
as neeed, giving
a function that operates on a list of lists:
>>>
{-# LANGUAGE ScopedTypeVariables #-}
>>>
import Control.Applicative (ZipList(..))
>>>
import Data.Coerce (coerce)
>>>
>>>
transpose :: forall a. [[a]] -> [[a]]
>>>
transpose = coerce (sequenceA :: [ZipList a] -> ZipList [a])
>>>
>>>
transpose [[1,2,3],[4..],[7..]]
[[1,4,7],[2,5,8],[3,6,9]]
The use of coercion avoids the need to explicitly wrap and
unwrap ZipList
terms.
Laws
A definition of traverse
must satisfy the following laws:
- Naturality
t .
for every applicative transformationtraverse
f =traverse
(t . f)t
- Identity
traverse
Identity
=Identity
- Composition
traverse
(Compose
.fmap
g . f) =Compose
.fmap
(traverse
g) .traverse
f
A definition of sequenceA
must satisfy the following laws:
- Naturality
t .
for every applicative transformationsequenceA
=sequenceA
.fmap
tt
- Identity
sequenceA
.fmap
Identity
=Identity
- Composition
sequenceA
.fmap
Compose
=Compose
.fmap
sequenceA
.sequenceA
where an applicative transformation is a function
t :: (Applicative f, Applicative g) => f a -> g a
preserving the Applicative
operations, i.e.
t (pure
x) =pure
x t (f<*>
x) = t f<*>
t x
and the identity functor Identity
and composition functors
Compose
are from Data.Functor.Identity and
Data.Functor.Compose.
A result of the naturality law is a purity law for traverse
traverse
pure
=pure
(The naturality law is implied by parametricity and thus so is the purity law [1, p15].)
The superclass instances should satisfy the following:
- In the
Functor
instance,fmap
should be equivalent to traversal with the identity applicative functor (fmapDefault
). - In the
Foldable
instance,foldMap
should be equivalent to traversal with a constant applicative functor (foldMapDefault
).
Note: the Functor
superclass means that (in GHC) Traversable structures
cannot impose any constraints on the element type. A Haskell implementation
that supports constrained functors could make it possible to define
constrained Traversable
structures.
See also
- [1] "The Essence of the Iterator Pattern", by Jeremy Gibbons and Bruno Oliveira, in Mathematically-Structured Functional Programming, 2006, online at http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator.
- "Applicative Programming with Effects", by Conor McBride and Ross Paterson, Journal of Functional Programming 18:1 (2008) 1-13, online at http://www.soi.city.ac.uk/~ross/papers/Applicative.html.
- "An Investigation of the Laws of Traversals", by Mauro Jaskelioff and Ondrej Rypacek, in Mathematically-Structured Functional Programming, 2012, online at http://arxiv.org/pdf/1202.2919.