alg_structs: Algebraic Structures in OCaml Structs

Api Reference

See the Api Reference.

Summary

An library specifying algebraic structures and category-theoretic idioms useful in the design and implementation of software.

It aims to provide useful modules that are (correctly) based on algebraic and category theoretic structures rather than mathematically precise representations.

Currently, this library should be viewed as an experiment to determine whether easy access to such mechanisms can be used to any advantage in OCaml programs.

The library is modeled after a fragment of Haskell’s rich ecosystem of algebraic structures implemented via typeclasses. However, liberties have been taken to adapt the implementations to be more amenable to idiomatic OCaml where it seemed appropriate.

Conventions

A structure's signature is named S

Each structure includes a signature S which gives its specification. S specifies the core types and operations of the structure as well any additional functions derived from those core aspects.

Note that S includes extensions which are derived from the properties of the structure, and is not a mathematically precise representation of the underlying structure

A structure can be built from its Seed

Most of the structures can be built up from a Seed. Where applicable, a structure's Seed specifies the essential types and operators needed to elaborate out the extended structure.

Users are free to implement their own fully customized versions of a structure, or to build one from a Seed and then override whichever functions they want. See each structure for relevant examples.

A structure should obey its Laws

Every structure includes a parameterized module called Law. The laws are expressed as predicates that should be true for any arguments of the specified type. The Law serves both as documentation of those necessary properties of a structure that cannot be encoded in the type system and as a tool for checking that your own implementations are lawfull.

If you implement a structure satisfying some spec, you should ensure it follows the laws. You can use the package alg_structs_qcheck to help generate property based tests for this purpose.

Some Examples

Applicative

See Applicative.

Assuming you have

open Alg_structs

applying to lists

Applicative.List.((^) <@> ["a";"b"] <*> ["1";"2"])
(* - : string list = ["a1"; "a2"; "b1"; "b2"] *)

for binding operators

on options

let some_sum =
  let open Option.Let_bind
  in
  let+ x = Some 1
  and+ y = Some 2
  and+ z = Some 3
  in
  x + y + z

let () = assert (some_sum = Some 6)

on lists

let tupples_of_list_elements =
  let open List.Let_bind in
  let+ x = [1; 2]
  and+ y = ['a'; 'b']
  in
  (x, y)

let () = assert (tupples_of_list_elements =
                 [(1, 'a'); (1, 'b');
                  (2, 'a'); (2, 'b')])

Foldable

See Foldable.

implementing a tree

module Tree = struct
  module T = struct
    type 'a t = Nil | Leaf of 'a | Node of 'a t * 'a * 'a t

    let rec fold_right ~f t ~init = match t with
      | Nil -> init
      | Leaf x -> f x init
      | Node (l, x, r) -> fold_right ~f ~init:(f x (fold_right ~f ~init r)) l
  end
  include T
  include (Make (T) : S with type 'a t = 'a T.t)
end

using the functions

let tree = Tree.T.Node(Leaf 1, 2, Node (Leaf 4, 3, Leaf 5))

Tree.max tree ~compare:Int.compare;;
(* - : int option = Some 5 *)

Tree.min tree ~compare:Int.compare;;
(* - : int option = Some 1 *)

Tree.to_list tree;;
(* - : int list = [1; 2; 4; 3; 5] *)

Tree.length tree;;
(* - : int = 5 *)