- Courses
- 💻Programming Languages
- 🐫OCaml (WIP)
- Modules, Structure & Tooling
- Guided Exercise: Build a Mini Library
On this page
Guided Exercise: Build A Publish-Quality Mini-Library in OCaml
Published on August 3, 2026
By Enrico Hochkoeppler
Web Developer & TutoriaLibre Founder
This project builds a small but genuinely complete OCaml library — a functional queue — to a standard suitable for actual publication: a proper Dune project layout, an abstract public interface that hides its implementation, declared package metadata, a full Alcotest test suite, and generated odoc documentation. Every piece introduced separately elsewhere comes together here in one finished, shareable package.
The Problem, Stated Precisely
Build a library, aqueue, implementing a first-in-first-out queue with:
empty : 'a t— an empty queue.push : 'a -> 'a t -> 'a t— adds an element to the back.pop : 'a t -> ('a * 'a t) option— removes and returns the front element, orNoneif empty.peek : 'a t -> 'a option— returns the front element without removing it, orNoneif empty.is_empty : 'a t -> bool
The queue's type must be abstract, its internal representation must not be exposed, and every operation must run in amortized constant time rather than the linear time a naive single-list implementation would require. The finished project needs a passing Alcotest suite and successfully generated odoc documentation.
Step 1: Set Up the Project Layout
dune init proj aqueue
cd aqueue
The generated lib/, bin/, and test/ directories are all used, though bin/ will only hold a minimal example rather than being the project's main focus — this is a library-first project, not an application.
Step 2: Choose a Representation
A queue backed by a single list would need to append to one end and remove from the other, and one of those two operations is unavoidably linear time on a plain list. The standard fix is a two-list representation: a front list, read from directly, and a back list, pushed onto directly and reversed only when front runs out.
type 'a t = { front : 'a list; back : 'a list }
The invariant this representation depends on: whenever front is empty, back must be empty too — meaning the queue as a whole is empty. If front were allowed to run empty while back still held elements, pop would have no way to find the next element without first reversing back, which is exactly the case the representation is designed to avoid needing on every single call.
Step 3: Implement the Library
In lib/aqueue.ml:
type 'a t = { front : 'a list; back : 'a list }
let empty = { front = []; back = [] }
let normalize q =
match q.front with
| [] -> { front = List.rev q.back; back = [] }
| _ -> q
let push x q = normalize { front = q.front; back = x :: q.back }
let pop q =
match q.front with
| [] -> None
| h :: t -> Some (h, normalize { front = t; back = q.back })
let peek q =
match q.front with
| [] -> None
| h :: _ -> Some h
let is_empty q = q.front = []
let to_list q = q.front @ List.rev q.back
normalize is the function that restores the invariant: whenever front is empty, it rebuilds front from a reversed back, leaving back empty again. Both push and pop call it on their way out, which is what guarantees the invariant holds every time a caller receives a queue value back — nothing outside this file ever sees a queue where the invariant has been allowed to slip, since every path that could break it immediately restores it before returning.
The amortized-constant-time claim holds because each element is only ever reversed once: it moves from back into front exactly one time, via exactly one List.rev call, over the course of its entire lifetime in the queue, no matter how many total push and pop calls happen around it. to_list isn't part of the required interface, but it's a useful internal helper for writing tests, since it converts a queue into an ordinary list in front-to-back order regardless of how the elements happen to be split between front and back at that moment.
Step 4: Write the Public Interface
In lib/aqueue.mli:
(** A functional, amortized constant-time queue. *)
type 'a t
(** The empty queue. *)
val empty : 'a t
(** [push x q] returns a new queue with [x] added to the back of [q]. *)
val push : 'a -> 'a t -> 'a t
(** [pop q] returns the front element of [q] together with the
remaining queue, or [None] if [q] is empty. *)
val pop : 'a t -> ('a * 'a t) option
(** [peek q] returns the front element of [q] without removing it,
or [None] if [q] is empty. *)
val peek : 'a t -> 'a option
(** [is_empty q] is [true] if and only if [q] contains no elements. *)
val is_empty : 'a t -> bool
type 'a t is left abstract deliberately, with no front/back fields exposed — this is what makes the invariant from Step 3 an actual guarantee rather than just an intention, since there's no way for anything outside aqueue.ml to construct a t value except through empty, push, and pop, all three of which already preserve it. to_list is intentionally left out of this signature entirely; it remains fully usable inside aqueue.ml itself and inside the test suite, but isn't part of the library's public contract.
Step 5: Wire Up the Library in Dune
lib/dune:
(library
(name aqueue))
dune-project, with package metadata declared so the project has something for documentation and installation to attach to:
(lang dune 3.0)
(name aqueue)
(package
(name aqueue)
(synopsis "A functional, amortized constant-time queue")
(depends
(ocaml (>= 4.14))
dune
(alcotest (and (>= 1.7) :with-test))
(odoc :with-doc)))
Step 6: Write the Test Suite
test/dune:
(test
(name test_aqueue)
(libraries aqueue alcotest))
test/test_aqueue.ml:
let test_empty_is_empty () =
Alcotest.(check bool) "empty queue" true (Aqueue.is_empty Aqueue.empty)
let test_push_pop_order () =
let q = Aqueue.(empty |> push 1 |> push 2 |> push 3) in
Alcotest.(check (list int)) "FIFO order" [ 1; 2; 3 ] (Aqueue.to_list q)
let test_pop_returns_front () =
let q = Aqueue.(empty |> push 1 |> push 2) in
match Aqueue.pop q with
| Some (x, rest) ->
Alcotest.(check int) "front element" 1 x;
Alcotest.(check (list int)) "remaining queue" [ 2 ] (Aqueue.to_list rest)
| None -> Alcotest.fail "expected Some, got None"
let test_pop_empty_is_none () =
Alcotest.(check bool) "pop on empty" true (Aqueue.pop Aqueue.empty = None)
let test_peek_does_not_remove () =
let q = Aqueue.(empty |> push 1 |> push 2) in
let _ = Aqueue.peek q in
Alcotest.(check (list int)) "queue unchanged after peek" [ 1; 2 ] (Aqueue.to_list q)
let () =
Alcotest.run "Aqueue"
[ ( "core operations"
, [ Alcotest.test_case "empty is empty" `Quick test_empty_is_empty
; Alcotest.test_case "push then pop order" `Quick test_push_pop_order
; Alcotest.test_case "pop returns front" `Quick test_pop_returns_front
; Alcotest.test_case "pop on empty" `Quick test_pop_empty_is_none
; Alcotest.test_case "peek does not remove" `Quick test_peek_does_not_remove
] )
]
test_push_pop_order is the test that actually exercises the two-list rebalancing logic meaningfully: pushing three elements fills back, and reading them back out through to_list (which itself reverses back) confirms they come out in the same order they were pushed, rather than reversed by accident.
Step 7: Run the Tests and Generate Documentation
opam install . --deps-only --with-test --with-doc
dune test
A passing run confirms every test case succeeded. Generating the documentation:
dune build @doc
opens up browsable HTML under _build/default/_doc/_html/index.html, built directly from the doc comments already written into aqueue.mli in Step 4 — no additional documentation-specific code is needed beyond what was already written as part of a properly documented interface.
Step 8: Add a Package Overview
doc/index.mld:
{0 Aqueue}
A functional, amortized constant-time queue implemented with the
classic two-list technique.
See {!module:Aqueue} for the full API.
doc/dune:
(documentation)
Rebuilding the documentation now shows this page as the package's entry point, linking directly into the API reference generated from aqueue.mli.
Reviewing Against the Publish-Quality Checklist
- Abstract public interface —
aqueue.mliexposes onlyt,empty,push,pop,peek, andis_empty, with the representation and its invariant fully hidden. - Declared package metadata —
dune-projectnames the package, gives it a synopsis, and declares every dependency with appropriate:with-test/:with-doctags. - Passing test suite —
dune testexercises every public function, including the empty-queue edge cases for bothpopandpeek. - Generated documentation —
dune build @docproduces a browsable site, complete with a package overview page and a fully documented API reference.
Extending the Project
A few natural next steps:
- Add a
length : 'a t -> intfunction, and a test confirming it stays correct across a mix of pushes and pops. - Add a
Queuesubmodule-style constructor from a list,of_list : 'a list -> 'a t, and a matchingto_listexposed publicly this time, for converting a queue back into an ordinary list as part of the public interface rather than only as a private test helper. - Package the project for actual publication to the opam repository, using the metadata already declared in
dune-projectas the starting point.
Found this helpful? Share the knowledge...
... or support this project to keep it alive!
Previous
Documentation Generation
Next
Functional Design Idioms
- The Problem, Stated Precisely
- Step 1: Set Up the Project Layout
- Step 2: Choose a Representation
- Step 3: Implement the Library
- Step 4: Write the Public Interface
- Step 5: Wire Up the Library in Dune
- Step 6: Write the Test Suite
- Step 7: Run the Tests and Generate Documentation
- Step 8: Add a Package Overview
- Reviewing Against the Publish-Quality Checklist
- Extending the Project
