Traversable -package:cabal-install-solver

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.

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.

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

If you have a Traversable instance of a record, you can load and store all elements, that are accessible by Traversable methods. We treat the record like an array, that is we assume, that all elements have the same size and alignment. Example:

import Foreign.Storable.Traversable as Store

data Stereo a = Stereo {left, right :: a}

instance Functor Stereo where
fmap = Trav.fmapDefault

instance Foldable Stereo where
foldMap = Trav.foldMapDefault

instance Traversable Stereo where
sequenceA ~(Stereo l r) = liftA2 Stereo l r

instance (Storable a) => Storable (Stereo a) where
sizeOf = Store.sizeOf
alignment = Store.alignment
peek = Store.peek (error "instance Traversable Stereo is lazy, so we do not provide a real value here")
poke = Store.poke

You would certainly not define the Traversable and according instances just for the implementation of the Storable instance, but there are usually similar applications where the Traversable instance is useful.

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

Generic implementation of Foldable and Traversable. There is already a naive implementation using the generic Rep's own instances of Foldable and Traversable. However, deriving then generates a lot of code that may not be simplified away by GHC, that results in unnecessary run-time overhead. In contrast, this implementation guarantees that the generated code is identical to stock-derived instances of Foldable and Traversable, which have the following syntactic properties:

• constructors with zero fields use pure once;
• constructors with one field use fmap once;
• constructors with n >= 2 fields use liftA2 once and (<*>) n-2 times.

The heavy lifting is actually done by the ap-normalize library.

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.

Equivalent of Traversable for rank 2 data types

All of the functions below work only on «interesting» subterms. It is up to the instance writer to decide which subterms are interesting and which subterms should count as immediate. This can also depend on the context c. The context, denoted c, is a constraint (of kind * -> Constraint) that provides additional facilities to work with the data. In most cases, the context cannot be inferred automatically. You need to provide it using the type application syntax:

gmap @Show f x
everywhere @Typeable f x

etc. For more information, see:

• Scrap your boilerplate with class https://www.microsoft.com/en-us/research/publication/scrap-your-boilerplate-with-class/
• Generalizing generic fold http://ro-che.info/articles/2013-03-11-generalizing-gfoldl

A Foldable instance for functions, given the input is Finite, and a Traversable instance for functions, given the input is Ord and Finite.

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)