Signatures and functors for containers and data structures that can be mapped across in two different ways with a monadic side-effect.
Bi_traversable is to Bi_mappable what Traversable is to Mappable. It approximates the concept with the same name that appears in various Haskell bifunctor libraries.
Signatures
For input and output signatures for this module's functors, see Bi_traversable_types.
Making full bi-traversable type modules
These functors build full implementations of bi-traversability given the basic minimal definitions above.
Make2 implements S2 for an arity-2 bi-traversable container.
Make1_left implements S1_left for an arity-1 bi-traversable container with floating left type.
Make1_right implements S1_right for an arity-1 bi-traversable container with floating right type.
Make0 implements S0 for an arity-0 bi-traversable container.
Fixing types
We can convert arity-2 modules to arity-1 modules, and arity-1 modules to arity-0 modules, by fixing types. The various FixX_Y functors achieve this.
Arity-2
Fix2_left (I) (Left) fixes the left type of I to Left, making it an S1_right.
Fix2_right (S) (Left) fixes the right type of S to Right, making it an S1_left.
Fix2_both (S) (Left) (Right) fixes the types of S to Left and Right, making it an S0.
Arity-1
Fix1_left (S) (Left) fixes the floating left type of S to Left, making it an S0.
Fix1_right (I) (Right) fixes the floating right type of S to Right, making it an S0.
Converting bi-traversable modules to traversable modules
By ignoring values of either the left or the right type, we can derive traversable modules from bi-traversable ones. Since the various S n signatures contain functions for doing this on an ad-hoc basis, the functors below are mainly for use when one needs actual Traversable instances.
The various caveats that apply to fixing bi-mappable types apply. Note also that the various Traverse0 functors are more restrictive than their arity-1 and arity-2 counterparts.
Arity-1
Traversing over the left type of an arity-1 bi-traversable container with a floating left type.
Traversing over the right type of an arity-1 bi-traversable container with a floating right type.
Arity-0
Since arity-0 Base-style containers require their element to implement equality, the same restriction applies to arity-0 traversables. This means that the arity-0 functors need to carry an extra parameter that witnesses this equality.
As mappables don't have this restriction, if one requires only non-monadic mappable functionality down one side of an arity 0 bi-traversable, one can use the Map0 functors in Bi_mappable with an S0.
Traversing over the left type of an arity-0 bi-traversable container, which must have equality as witnessed by an Equal.S module.
Traversing over the right type. of an arity-0 bi-traversable container, which must have equality as witnessed by an Equal.S module.
Chaining containers
Chaining a traversable on the outside of a bi-traversable
These functors let us compose an inner bi-traversable container with an outer traversable container, producing a bi-traversable.
For example, we can make associative lists bi-traversable by composing a bi-traversable over pairs (a * b) with a traversable over lists.
Chain_Bi2_Traverse1 (Bi) (Trav) composes a bi-traversal Bi on an inner arity-2 container over a traversal Trav over an outer arity-1 container.
Chain_Bi1_left_Traverse1 (Bi) (Trav) composes a bi-traversal Bi on an inner arity-1 container with floating left type over a traversal Trav over an outer arity-1 container.
Chain_Bi1_right_Traverse1 (Bi) (Trav) composes a bi-traversal Bi on an inner arity-1 container with floating right type over a traversal Trav over an outer arity-1 container.
Chain_Bi0_Traverse1 (Bi) (Trav) composes a bi-traversal Bi on an inner arity-0 container over a traversal Trav over an outer arity-1 container.
Chaining traversables on the inside of a bi-traversable
These functors let us compose one or two inner traversable containers with an outer bi-traversable container, producing a bi-traversable.
Chain_Traverse1_Bi2 (LTrav) (RTrav) (Bi) composes an inner arity-1 traversal LTrav on the left, and another such traversal RTrav on the right, of an arity-2 bi-traversal Bi.
Chain_Traverse1_Bi1_left (LTrav) (Bi) composes an inner arity-1 traversal LTrav on the left of an arity-1 bi-traversal Bi with floating left type.
Chain_Traverse1_Bi1_right (RTrav) (Bi) composes an inner arity-1 traversal LTrav on the right of an arity-1 bi-traversal Bi with floating right type.