On this page

Project: Implement Your Own List Module

Published on July 21, 2026

Enrico Hochkoeppler Profile

By Enrico Hochkoeppler

Web Developer & TutoriaLibre Founder

This project rebuilds four of the most commonly used List functions — map, filter, fold_left, fold_right, and a working sort — entirely from primitives: pattern matching and recursion, with no calls to the real List module anywhere in the implementation. The goal isn't to produce something faster or better than the standard library; it's to turn "I know how to call List.map" into "I know exactly what List.map is doing underneath," by rebuilding it by hand.

The Problem, Stated Precisely​

Build a module, MyList, that implements:

Every function must be written using only pattern matching ([] and h :: t) and recursion — no calls to List.map, List.fold_left, or any other function from the real List module are allowed anywhere in the solution.

Step 1: Set Up the Project​


dune init proj mylist

cd mylist

The implementation goes in lib/mylist.ml, replacing its generated placeholder content, so it can be exercised from bin/main.ml afterward.

Step 2: Implement map​

map f lst applies f to every element, preserving order and length. The base case handles the empty list directly; the recursive case applies f to the head and recurses on the tail:


let rec map f = function

  | [] -> []

  | h :: t -> f h :: map f t

Each recursive call handles a strictly shorter list, with [] guaranteed to be reached eventually, which is what makes this structurally recursive and guaranteed to terminate on any finite list.

Step 3: Implement filter​

filter p lst keeps only the elements satisfying the predicate p. The base case is identical to map's; the recursive case decides whether to keep the head before recursing on the tail:


let rec filter p = function

  | [] -> []

  | h :: t -> if p h then h :: filter p t else filter p t

Notice both branches of the if still recurse on t — the only difference is whether h gets attached to the front of that recursive result.

Step 4: Implement fold_left and fold_right​

fold_right combines the head with the recursive result on the tail, after that recursive call returns:


let rec fold_right f lst acc =

  match lst with

  | [] -> acc

  | h :: t -> f h (fold_right f t acc)

fold_left instead folds the head into the accumulator immediately, before recursing, which is what makes it tail-recursive:


let rec fold_left f acc lst =

  match lst with

  | [] -> acc

  | h :: t -> fold_left f (f acc h) t

Step 5: Implement sort, Building on fold_right​

Rather than writing a sorting algorithm entirely from scratch, this step builds sort directly on top of the fold_right already implemented, using a classic technique: insertion sort. First, a helper function that inserts a single element into an already-sorted list, at the correct position, using a comparator function to decide ordering:


let rec insert cmp x = function

  | [] -> [x]

  | h :: t -> if cmp x h <= 0 then x :: h :: t else h :: insert cmp x t

insert cmp x sorted walks sorted until it finds the first element x should come before (cmp x h <= 0), inserting x right there; if no such element exists, x belongs at the very end.

Sorting an entire list is now just repeatedly inserting each element into an initially empty list, which is exactly what fold_right already expresses:


let sort cmp lst = fold_right (insert cmp) lst []

Reading this the same way fold_right was read earlier — replacing every :: with the given function, and [] with the given initial value — sort cmp lst folds insert cmp into the list from the right, building up a fully sorted list one insertion at a time, starting from an empty sorted list.

Step 6: Assemble the Module​

Putting every step together in lib/mylist.ml:


let rec map f = function

  | [] -> []

  | h :: t -> f h :: map f t



let rec filter p = function

  | [] -> []

  | h :: t -> if p h then h :: filter p t else filter p t



let rec fold_right f lst acc =

  match lst with

  | [] -> acc

  | h :: t -> f h (fold_right f t acc)



let rec fold_left f acc lst =

  match lst with

  | [] -> acc

  | h :: t -> fold_left f (f acc h) t



let rec insert cmp x = function

  | [] -> [x]

  | h :: t -> if cmp x h <= 0 then x :: h :: t else h :: insert cmp x t



let sort cmp lst = fold_right (insert cmp) lst []

Step 7: Test Every Function​

From bin/main.ml, or directly in utop with the library loaded:


# Mylist.map (fun x -> x * 2) [1; 2; 3];;

- : int list = [2; 4; 6]



# Mylist.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5; 6];;

- : int list = [2; 4; 6]



# Mylist.fold_left ( + ) 0 [1; 2; 3; 4];;

- : int = 10



# Mylist.fold_right ( ^ ) ["a"; "b"; "c"] "";;

- : string = "abc"



# Mylist.sort compare [5; 3; 1; 4; 2];;

- : int list = [1; 2; 3; 4; 5]



# Mylist.sort (fun a b -> compare b a) [5; 3; 1; 4; 2];;

- : int list = [5; 4; 3; 2; 1]

The last two calls confirm that sort genuinely depends on the comparator passed in: reversing the comparator's result reverses the sort order, without changing a single line of sort or insert itself.

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

Reading Unfamiliar Type Signatures

Next

Modules, Structure & Tooling