Documentation

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.

A definition of traverse 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 ≡ traverse (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 defined as

newtype Identity a = Identity { runIdentity :: a }

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

instance Applicative Identity where
  pure = Identity
  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 = Compose . pure . pure
  Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

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.

Sequences all the actions in a structure, building a new structure with the same shape using the results of the actions.

bisequenceA ≡ bitraverse id id

As bisequenceA, but uses evidence that m is a Monad rather than an Applicative.

bisequence ≡ bimapM id id
bisequence ≡ unwrapMonad . bisequenceA . bimap WrapMonad WrapMonad

As bitraverse, but uses evidence that m is a Monad rather than an Applicative.

bimapM f g ≡ bisequence . bimap f g
bimapM f g ≡ unwrapMonad . bitraverse (WrapMonad . f) (WrapMonad . g)

bifor is bitraverse with the structure as the first argument.

biforM is bimapM with the structure as the first argument.

Traverses a structure from left to right, threading a state of type a and using the given actions to compute new elements for the structure.

Traverses a structure from right to left, threading a state of type a and using the given actions to compute new elements for the structure.

A default definition of bimap in terms of the Bitraversable operations.

A default definition of bifoldMap in terms of the Bitraversable operations.