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.

Documentation

Contents

• Summary
• Installation
• Examples
• Related work
• Tasks

Summary

alg_structs is an OCaml library specifying algebraic structures useful in the design and implementation of software.

The only external dependency currently is ppx_deriving.

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.

Installation

With opam

Requires opam

opam install alg_structs

Building from source

Requires dune

git clone git@github.com:shonfeder/alg_structs.git
cd alg_structs
dune build

Examples

Applicative

Assuming you have

open Alg_structs

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"] *)

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

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

Related work

Resources consulted

I consulted the following while working on this library, and took at least some inspiration from each of them:

Joseph Abrahamson’s ocaml-cats

Abrahamson’s ocaml-cats is 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-cats is narrowly focused on specifying the structures, whereas alg_structs also provides implementations for common data types along with other utilities. ocaml-cats currently 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.

Similar projects

Projects which have not had an impact on the design of alg_structs but are related, and should be considered as alternatives to this library, and future sources of inspiration:

clarity

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_structs emphasis on functions extending the base structures.

Darin Morrison’s ocaml-cats

Morrison’s ocaml-cats is 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_structs is currently, but it is undocummented and doesn’t appear to include tests.

Tasks

Add CoC

Add CONTRIBUTING file

Add a support adapter package for integration with Base/Core

Add more structures

• [ ] Alternative (and kin)
• [ ] Monads
• [ ] Free Monads?
• [ ] Traversable

Expanded implementations of common data types

Redesign API so extending implementations won’t break backwards compatibility

Study Morrison’s ocaml-cats and incorporate relevent design and implementation choices