package alg_structs

  1. Overview
  2. Docs

An interface for types that can be mapped over.

All you need to know to use this module effectively:

given type 'a t, function map : f:('a -> 'b) -> 'a t -> 'b t will map f "over" t by taking a value of type 'a t to a value of type 'b t.

E.g., if

type 'a t = int list

then

map ~f:Int.to_string : int t -> string t

is a function which maps int lists to string lists, so

map ~f:Int.to_string [1;2;3] = ["1";"2";"3"]

A Rough Sketch of the Category Theoretic Basis

To repeat, you don't need to read any of the following in order to make use of this module.

The use of the word functor in this context refers to the category theoretic concept of Functor, which is a map between categories. A functor F: C -> D that maps category C to category D consists of two mappings:

  1. a mapping of each object in C to some object in D
  2. a mapping of each arrow in C to some arrow in D

These mappings must respect the Laws.

An "endofunctor" is a functor that is a map of one category within itself (or back onto itself).

We imagine a category CAML (analogous to Hask), where the objects are OCaml types and the arrows are functions between those types. S then specifies an interface for modules that implement an "endofunctor" on CAML, mapping types to types and functions to functions.

Seed

module type Seed = sig ... end

The Seed needed to generate an implementation of Functor.

module type UnlabeledSeed = sig ... end

Interface for a mappable type with an unlabeled map function.

Interface

module type S = sig ... end

A module satisfying S is an implementation of a functor.

Laws

module Law (F : S) : sig ... end

Law notes the laws that should be obeyed by any instantiation of Functor in the form of predicates that should be true for any arguments of the appropriate type.

Constructors

Module functors and signatures for expediting instantiation of Functors.

module Make (Seed : Seed) : S with type 'a t = 'a Seed.t
module MakeUnlabeled (Seed : UnlabeledSeed) : S with type 'a t = 'a Seed.t

MakeUnlabeled makes an module instantiating S, with a labeled S.map, out of a module instantiating UnlabeledSeed with an unlabeled map function.

Implementations

module Option : S with type 'a t = 'a Stdlib.Option.t
module List : S with type 'a t = 'a Stdlib.List.t
module Array : S with type 'a t = 'a Stdlib.Array.t