On this page

Guided Exercise: Build A Publish-Quality Mini-Library in OCaml

Published on August 3, 2026

Enrico Hochkoeppler Profile

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:

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​

Extending the Project​

A few natural next steps:

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Documentation Generation

Next

Functional Design Idioms