Travesty.Bi_traversable
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.
For input and output signatures for this module's functors, see Bi_traversable_types
.
These functors build full implementations of bi-traversability given the basic minimal definitions above.
module Make2
(I : Bi_traversable_types.Basic2) :
Bi_traversable_types.S2 with type ('l, 'r) t = ('l, 'r) I.t
Make2
implements S2 for an arity-2 bi-traversable container.
module Make1_left
(I : Bi_traversable_types.Basic1_left) :
Bi_traversable_types.S1_left with type 'l t = 'l I.t and type right = I.right
Make1_left
implements S1_left for an arity-1 bi-traversable container with floating left type.
module Make1_right
(I : Bi_traversable_types.Basic1_right) :
Bi_traversable_types.S1_right with type 'r t = 'r I.t and type left = I.left
Make1_right
implements S1_right for an arity-1 bi-traversable container with floating right type.
module Make0
(I : Bi_traversable_types.Basic0) :
Bi_traversable_types.S0
with type t = I.t
and type left = I.left
and type right = I.right
Make0
implements S0 for an arity-0 bi-traversable container.
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.
module Fix2_left
(I : Bi_traversable_types.Basic2)
(Left : Base.T) :
Bi_traversable_types.S1_right
with type 'r t = (Left.t, 'r) I.t
and type left = Left.t
Fix2_left (I) (Left)
fixes the left type of I
to Left
, making it an S1_right.
module Fix2_right
(I : Bi_traversable_types.Basic2)
(Right : Base.T) :
Bi_traversable_types.S1_left
with type 'l t = ('l, Right.t) I.t
and type right = Right.t
Fix2_right (S) (Left)
fixes the right type of S
to Right
, making it an S1_left.
module Fix2_both
(I : Bi_traversable_types.Basic2)
(Left : Base.T)
(Right : Base.T) :
Bi_traversable_types.S0
with type t = (Left.t, Right.t) I.t
and type left = Left.t
and type right = Right.t
Fix2_both (S) (Left) (Right)
fixes the types of S
to Left
and Right
, making it an S0.
module Fix1_left
(I : Bi_traversable_types.Basic1_left)
(Left : Base.T) :
Bi_traversable_types.S0
with type t = Left.t I.t
and type left = Left.t
and type right = I.right
Fix1_left (S) (Left)
fixes the floating left type of S
to Left
, making it an S0.
module Fix1_right
(I : Bi_traversable_types.Basic1_right)
(Right : Base.T) :
Bi_traversable_types.S0
with type t = Right.t I.t
and type left = I.left
and type right = Right.t
Fix1_right (I) (Right)
fixes the floating right type of S
to Right
, making it an S0.
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.
module Traverse1_left
(S : Bi_traversable_types.S1_left) :
Traversable_types.S1 with type 'l t = 'l S.t
Traversing over the left type of an arity-1 bi-traversable container with a floating left type.
module Traverse1_right
(S : Bi_traversable_types.S1_right) :
Traversable_types.S1 with type 'r t = 'r S.t
Traversing over the right type of an arity-1 bi-traversable container with a floating right type.
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 Mappable
types 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.
module Traverse0_left
(L : Base.Equal.S)
(S : Bi_traversable_types.S0 with type left := L.t) :
Traversable_types.S0 with type t = S.t and module Elt = L
Traversing over the left type of an arity-0 bi-traversable container, which must have equality as witnessed by an Equal.S
module.
module Traverse0_right
(R : Base.Equal.S)
(S : Bi_traversable_types.S0 with type right := R.t) :
Traversable_types.S0 with type t = S.t and module Elt = R
Traversing over the right type. of an arity-0 bi-traversable container, which must have equality as witnessed by an Equal.S
module.
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.
module Chain_Bi2_Traverse1
(Bi : Bi_traversable_types.S2)
(Trav : Traversable_types.S1) :
Bi_traversable_types.S2 with type ('l, 'r) t = ('l, 'r) Bi.t Trav.t
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.
module Chain_Bi1_left_Traverse1
(Bi : Bi_traversable_types.S1_left)
(Trav : Traversable_types.S1) :
Bi_traversable_types.S1_left
with type 'l t = 'l Bi.t Trav.t
and type right = Bi.right
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.
module Chain_Bi1_right_Traverse1
(Bi : Bi_traversable_types.S1_right)
(Trav : Traversable_types.S1) :
Bi_traversable_types.S1_right
with type 'r t = 'r Bi.t Trav.t
and type left = Bi.left
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.
module Chain_Bi0_Traverse1
(Bi : Bi_traversable_types.S0)
(Trav : Traversable_types.S1) :
Bi_traversable_types.S0
with type t = Bi.t Trav.t
and type left = Bi.left
and type right = Bi.right
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.
These functors let us compose one or two inner traversable containers with an outer bi-traversable container, producing a bi-traversable.
module Chain_Traverse1_Bi2
(LTrav : Traversable_types.S1)
(RTrav : Traversable_types.S1)
(Bi : Bi_traversable_types.Basic2) :
Bi_traversable_types.S2 with type ('l, 'r) t = ('l LTrav.t, 'r RTrav.t) Bi.t
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
.
module Chain_Traverse1_Bi1_left
(LTrav : Traversable_types.S1)
(Bi : Bi_traversable_types.Basic1_left) :
Bi_traversable_types.S1_left
with type 'l t = 'l LTrav.t Bi.t
and type right = Bi.right
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.
module Chain_Traverse1_Bi1_right
(RTrav : Traversable_types.S1)
(Bi : Bi_traversable_types.Basic1_right) :
Bi_traversable_types.S1_right
with type 'r t = 'r RTrav.t Bi.t
and type left = Bi.left
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.