package travesty
Module Travesty.Bi_traversableSource
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.
Source
module Make2
(I : Bi_traversable_types.Basic2) :
Bi_traversable_types.S2 with type ('l, 'r) t = ('l, 'r) I.tMake2 implements S2 for an arity-2 bi-traversable container.
Source
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.rightMake1_left implements S1_left for an arity-1 bi-traversable container with floating left type.
Source
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.leftMake1_right implements S1_right for an arity-1 bi-traversable container with floating right type.
Source
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.rightMake0 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
Source
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.tFix2_left (I) (Left) fixes the left type of I to Left, making it an S1_right.
Source
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.tFix2_right (S) (Left) fixes the right type of S to Right, making it an S1_left.
Source
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.tFix2_both (S) (Left) (Right) fixes the types of S to Left and Right, making it an S0.
Arity-1
Source
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.rightFix1_left (S) (Left) fixes the floating left type of S to Left, making it an S0.
Source
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.tFix1_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
Source
module Traverse1_left
(S : Bi_traversable_types.S1_left) :
Traversable_types.S1 with type 'l t = 'l S.tTraversing over the left type of an arity-1 bi-traversable container with a floating left type.
Source
module Traverse1_right
(S : Bi_traversable_types.S1_right) :
Traversable_types.S1 with type 'r t = 'r S.tTraversing 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 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.
Source
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 = LTraversing over the left type of an arity-0 bi-traversable container, which must have equality as witnessed by an Equal.S module.
Source
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 = RTraversing 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.
Source
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.tChain_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.
Source
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.rightChain_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.
Source
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.leftChain_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.
Source
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.rightChain_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.
Source
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.tChain_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.
Source
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.rightChain_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.
Source
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.leftChain_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.