Traversable -is:module

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#overview. For the class laws see the Laws section of Data.Traversable#laws.

Functors representing data structures that can be traversed from left to right. A definition of traverse must satisfy the following laws:

• Naturality t . traverse f = traverse (t . f) for every applicative transformation 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 . sequenceA = sequenceA . fmap t for every applicative transformation t
• 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].) Instances are similar to Functor, e.g. given a data type

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

a suitable instance would be

instance Traversable Tree where
traverse f Empty = pure Empty
traverse f (Leaf x) = Leaf <$> f x
traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

This is suitable even for abstract types, as the laws for <*> imply a form of associativity. 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).

References: [1] The Essence of the Iterator Pattern, Jeremy Gibbons and Bruno C. d. S. Oliveira

Functors representing data structures that can be traversed from left to right. A definition of traverse must satisfy the following laws:

• naturality t . traverse f = traverse (t . f) for every applicative transformation 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 . sequenceA = sequenceA . fmap t for every applicative transformation t
• 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 (x <*> y) = t x <*> t
  y

and the identity functor Identity and composition of functors Compose are defined as

newtype Identity a = Identity a

instance Functor Identity where
fmap f (Identity x) = Identity (f x)

instance Applicative Identity where
pure x = Identity x
Identity f <*> Identity x = Identity (f x)

newtype Compose f g a = Compose (f (g a))

instance (Functor f, Functor g) => Functor (Compose f g) where
fmap f (Compose x) = Compose (fmap (fmap f) x)

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
pure x = Compose (pure (pure x))
Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

(The naturality law is implied by parametricity.) Instances are similar to Functor, e.g. given a data type

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

a suitable instance would be

instance Traversable Tree where
traverse f Empty = pure Empty
traverse f (Leaf x) = Leaf <$> f x
traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

This is suitable even for abstract types, as the laws for <*> imply a form of associativity. 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).

Equivalent of Traversable for rank 2 data types

A Traversable with an additional index. An instance must satisfy a (modified) form of the Traversable laws:

itraverse (const Identity) ≡ Identity
fmap (itraverse f) . itraverse g ≡ getCompose . itraverse (\i -> Compose . fmap (f i) . g i)

Barbie-types that can be traversed from left to right. Instances should satisfy the following laws:

t . btraverse f   = btraverse (t . f)  -- naturality
btraverse Identity = Identity           -- identity
btraverse (Compose . fmap g . f) = Compose . fmap (btraverse g) . btraverse f -- composition

There is a default btraverse implementation for Generic types, so instances can derived automatically.

Type class for inputs that can also be used for error reporting.

A Traversable with an additional index. An instance must satisfy a (modified) form of the Traversable laws:

itraverse (const Identity) ≡ Identity
fmap (itraverse f) . itraverse g ≡ getCompose . itraverse (\i -> Compose . fmap (f i) . g i)

Barbie-types that can be traversed from left to right. Instances should satisfy the following laws:

t . btraverse f   = btraverse (t . f)  -- naturality
btraverse Identity = Identity           -- identity
btraverse (Compose . fmap g . f) = Compose . fmap (btraverse g) . btraverse f -- composition

There is a default btraverse implementation for Generic types, so instances can derived automatically.

Indexed-functors that can be traversed from left to right. Instances should satisfy the following laws:

t . ttraverse f   = ttraverse (t . f)  -- naturality
ttraverse Identity = Identity           -- identity
ttraverse (Compose . fmap g . f) = Compose . fmap (ttraverse g) . ttraverse f -- composition

There is a default ttraverse implementation for Generic types, so instances can derived automatically.

Bitraversable identifies bifunctorial data structures whose elements can be traversed in order, performing Applicative or Monad actions at each element, and collecting a result structure with the same shape. As opposed to Traversable data structures, which have one variety of element on which an action can be performed, Bitraversable data structures have two such varieties of elements. A definition of bitraverse must satisfy the following laws:

• Naturality bitraverse (t . f) (t . g) ≡ t . bitraverse f g for every applicative transformation t
• Identity bitraverse Identity Identity ≡ Identity
• Composition Compose . fmap (bitraverse g1 g2) . bitraverse f1 f2 ≡ bitraverse (Compose . fmap g1 . f1) (Compose . fmap g2 . f2)

where an applicative transformation is a function

t :: (Applicative f, Applicative g) => f a -> g a

preserving the Applicative operations:

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. Some simple examples are Either and (,):

instance Bitraversable Either where
bitraverse f _ (Left x) = Left <$> f x
bitraverse _ g (Right y) = Right <$> g y

instance Bitraversable (,) where
bitraverse f g (x, y) = (,) <$> f x <*> g y

Bitraversable relates to its superclasses in the following ways:

bimap f g ≡ runIdentity . bitraverse (Identity . f) (Identity . g)
bifoldMap f g ≡ getConst . bitraverse (Const . f) (Const . g)

These are available as bimapDefault and bifoldMapDefault respectively. If the type is also an instance of Traversable, then it must satisfy (up to laziness):

traverse ≡ bitraverse pure