travesty 0.5.1 · OCaml Package

Mapping for containers with two element types.

Bi_mappable implements the Haskell notion of a bifunctor: a container that contains two distinct element types, both of which can be non-monadically, covariantly mapped over.

Common examples include:

maps and associative lists, where the two types are keys and values;
result types, where the two types are success and failure.

Signatures

Basic signatures

The generic signature

As with Traversable, we define the basic signature of bi-mappable structures in an arity-generic way, then specialise it for the various arities.

module type Basic_generic = sig ... end

Basic_generic describes bi-mapping on any arity of type.

Arity-specific basic signatures

The basic signatures are Basic0, which defines mapping across an arity-0 type t (with a fixed, associated element type elt); Basic1_left and Basic1_right, which fix the right and left element type respectively (leaving the named type floating); and Basic2, which defines mapping across an arity-2 type ('l, 'r) t with left element type 'l and right element type 'r.

module type Basic0 = sig ... end

Basic0 is the basic signature of an arity-0 bi-mappable type.

module type Basic1_left = sig ... end

Basic1_left is the basic signature of an arity-1 bi-mappable type with a floating left type and fixed right type.

module type Basic1_right = sig ... end

Basic1_right is the signature of an arity-1 bi-mappable type with a floating right type and fixed left type.

module type Basic2 = sig ... end

Basic2 is the signature of an arity-2 bi-mappable type with floating left and right types.

Signatures for bi-mappable types

The signatures below include various functions we can derive from bi-mappable types.

module type Generic = sig ... end

Generic is a generic interface for bi-mappable types, used to build S0 (arity-0) and S1 (arity-1).

module type S0 = sig ... end

S0 is the full signature of an arity-0 bi-mappable type.

module type S1_left = sig ... end

S1_left is the full signature of an arity-1 bi-mappable type with a floating left type and fixed right type.

module type S1_right = sig ... end

S1_right is the full signature of an arity-1 bi-mappable type with a floating right type and fixed left type.

module type S2 = sig ... end

S2 is the full signature of an arity-2 bi-mappable type with floating left and right types.

Making full bi-mappable type modules

These functors build full implementations of bi-mappability given the basic minimal definitions above.

module Make2 (I : Basic2) : S2 with type ('l, 'r) t := ('l, 'r) I.t

Make2 implements S2 for an arity-2 bi-mappable container.

module Make1_left
  (I : Basic1_left) : 
  S1_left with type 'l t = 'l I.t and type right = I.right

Make1_left implements S1_left for an arity-1 bi-mappable container with floating left type.

module Make1_right
  (I : Basic1_right) : 
  S1_right with type 'r t = 'r I.t and type left = I.left

Make1_right implements S1_right for an arity-1 bi-mappable container with floating right type.

module Make0
  (I : Basic0) : 
  S0 with type t = I.t and type left = I.left and type right = I.right

Make0 implements S0 for an arity-0 bi-mappable 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

module Fix2_left
  (I : Basic2)
  (Left : Base.T) : 
  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 : Basic2)
  (Right : Base.T) : 
  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 : Basic2)
  (Left : Base.T)
  (Right : Base.T) : 
  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.

Arity-1

module Fix1_left
  (I : Basic1_left)
  (Left : Base.T) : 
  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 : Basic1_right)
  (Right : Base.T) : 
  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.

Converting bi-mappable modules to mappable modules

By ignoring values of either the left or the right type, we can derive mappable modules from bi-mappable 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 Mappable instances.

This reflects the 'clowns to the left of me, jokers to the right' (the technical term!) set-up in Haskell; each Map_leftX functor implements a Clown; each Map_rightX functor implements a a Joker.

Since, unlike Haskell, we can't partially apply type constructors in OCaml, there are no arity-2 conversions available, and the arity-1 conversions only work if their direction is the one with a floating type. To rectify this, use Fix2_left and friends.

Arity-1

module Map1_left (S : S1_left) : Mappable.S1 with type 'l t = 'l S.t

Mapping over the left type of an arity-1 bi-mappable container with a floating left type.

module Map1_right (S : S1_right) : Mappable.S1 with type 'r t = 'r S.t

Mapping over the right type of an arity-1 bi-mappable container with a floating right type.

Arity-0

module Map0_left (S : S0) : Mappable.S0 with type t = S.t and type elt = S.left

Mapping over the left type of an arity-0 bi-mappable container.

module Map0_right
  (S : S0) : 
  Mappable.S0 with type t = S.t and type elt = S.right

Mapping over the right type. of an arity-0 bi-mappable container.

Chaining containers

Chaining a mappable on the outside of a bi-mappable

These functors let us compose an inner bi-mappable container with an outer mappable container, producing a bi-map.

For example, we can make associative lists bi-mappable by composing a bi-map over pairs (a * b) with a map over lists.

In Haskell terms, this is a Tannen.

module Chain_Bi2_Map1
  (Bi : S2)
  (Map : Mappable.S1) : 
  S2 with type ('l, 'r) t = ('l, 'r) Bi.t Map.t

Chain_Bi2_Map1 (Bi) (Map) composes a bi-map Bi on an inner arity-2 container over a map Map over an outer arity-1 container.

module Chain_Bi1_left_Map1
  (Bi : S1_left)
  (Map : Mappable.S1) : 
  S1_left with type 'l t = 'l Bi.t Map.t

Chain_Bi1_left_Map1 (Bi) (Map) composes a bi-map Bi on an inner arity-1 container with floating left type over a map Map over an outer arity-1 container.

module Chain_Bi1_right_Map1
  (Bi : S1_right)
  (Map : Mappable.S1) : 
  S1_right with type 'r t = 'r Bi.t Map.t

Chain_Bi1_right_Map1 (Bi) (Map) composes a bi-map Bi on an inner arity-1 container with floating right type over a map Map over an outer arity-1 container.

module Chain_Bi0_Map1
  (Bi : S0)
  (Map : Mappable.S1) : 
  S0 with type t = Bi.t Map.t

Chain_Bi0_Map1 (Bi) (Map) composes a bi-map Bi on an inner arity-0 container over a map Map over an outer arity-1 container.

package travesty

Signatures

Basic signatures

The generic signature

Arity-specific basic signatures

Signatures for bi-mappable types

Making full bi-mappable type modules

Fixing types

Arity-2

Arity-1

Converting bi-mappable modules to mappable modules

Arity-1

Arity-0

Chaining containers

Chaining a mappable on the outside of a bi-mappable