package travesty

  1. Overview
  2. Docs
package travesty
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Travesty.Bi_mappableSource

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.

Sourcemodule 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.

Sourcemodule type Basic0 = sig ... end

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

Sourcemodule 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.

Sourcemodule 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.

Sourcemodule 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.

Sourcemodule type Generic = sig ... end

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

Sourcemodule type S0 = sig ... end

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

Sourcemodule 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.

Sourcemodule 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.

Sourcemodule 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.

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

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

Sourcemodule 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.

Sourcemodule 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.

Sourcemodule 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

Sourcemodule 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.

Sourcemodule 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.

Sourcemodule 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

Sourcemodule 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.

Sourcemodule 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

Sourcemodule 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.

Sourcemodule 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

Sourcemodule 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.

Sourcemodule 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.

Sourcemodule 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.

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.

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.

Sourcemodule 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.