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 Law
s
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 *)