alg_structs: Algebraic Structures in OCaml Structs
NOTE: The API is currently unstable: “Major version zero (0.y.z) is for initial development. Anything MAY change at any time. The public API SHOULD NOT be considered stable.” (semver)
An OCaml library specifying algebraic structures useful in the design and implementation of software.
alg_structs is an OCaml library specifying algebraic structures useful in the
design and implementation of software.
The only external dependency currently is
I wrote this library because I needed these structures for other projects, and they were not available via any packages published on opam at the time.
I view this library as an experiment to determine whether easy access to such mechanisms can be used to any advantage in OCaml programs. Subsequent versions are subject to breaking changes as the usefulness of the current implementation is tested and evaluated, however proper semantic versioning will be used to signal any breaking changes.
The library is modeled after a fragment of Haskell’s rich ecosystem of algebraic structures, implemented via typeclasses. Most of the code in here started out as direct ports of the corresponding Haskell typeclasses. However, I have taken liberties to adapt the implementations to be more amenable to idiomatic OCaml where it seemed appropriate.
opam install alg_structs
Building from source
git clone email@example.com:shonfeder/alg_structs.git cd alg_structs dune build
Assuming you have
applying to optional values
Applicative.Option.((^) <@> Some "a" <*> Some "b") - : string option = Option.Some "ab"
Applicative.Option.((^) <@> Some "a" <*> None) - : string option = Option.None
applying to all combinations of list elements
Applicative.List.((^) <@> ["a";"b"] <*> ["1";"2"]) (* - : string list = ["a1"; "a2"; "b1"; "b2"] *)
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)
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')])
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 *)
I consulted the following while working on this library, and took at least some inspiration from each of them:
- Joseph Abrahamson’s ocaml-cats
ocaml-catsis a well structured and well documented collection of signatures specifying a number of category theoretic structures. Had I discovered that work prior to making substantial progress here, I would have considered forking it or basing the structure of this library more closely off of that one. There is an essential difference between the aims of these libraries however,
ocaml-catsis narrowly focused on specifying the structures, whereas
alg_structsalso provides implementations for common data types along with other utilities.
ocaml-catscurrently has a more extensive catalog of specifications, and the specifications are more principled.
- Yaron Minsky, Anil Madhavapeddy, Jason Hickey’s Real World Ocaml (2nd Edition)
- Specifically the chapter on first-class modules, which had to refer back to several times.
- Joel Björnson’s More type classes
- This post provided some helpful guidance on hacking the module system to ape typeclasses.
Projects which have not had an impact on the design of
but are related, and should be considered as alternatives to this library, and
future sources of inspiration:
- The stated goal of clarity is “to make pure functional programming
idioms as useful as possible given OCaml’s absence of higher-kinded types and
typeclasses”. Currently this library is slightly more extensive than
alg_structs. Two differentiating factors are
clarity’s focus on purity and use of laziness and
alg_structsemphasis on functions extending the base structures.
- Darin Morrison’s ocaml-cats
ocaml-catsis an impressive collection of category theoretic constructs. It includes specifications and implementations, and even support for (still experimental) modular implicits. I wish I had found this work earlier. If I had, I may have forked from it or simply done the work to package it up and use it in my other projects. Morrison’s library is significantly more extensive than
alg_structsis currently, but it is undocummented and doesn’t appear to include tests.
Add CONTRIBUTING file
Add a support adapter package for integration with Base/Core
Add more structures
- [ ] Alternative (and kin)
- [ ] Monads
- [ ] Free Monads?
- [ ] Traversable