Traversable package:relude

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.

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.