99 OCaml: Beginner Exercises

Problems for beginners taken from here. Instead of just being a store for solutions, this aims to actually go deeper and float all the learning takeaways that I had when completing the problem set. The code-snippets here can be tangled in emacs I will expose this code as an org-file publicly once I’ve completed the 99 problems. It will be hosted on Codeberg, hopefully it helps others. and can be executed directly.

Lists #

The exercises are grouped by classic data-structures. Naturally, List is the one we start with to build our foundation.

1. Tail of a List #

Write a function last : 'a list -> 'a option that returns the last element of a list

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

let input = ["a" ; "b" ; "c" ; "d"]

let rec last ls = match ls with
  | [] -> None
  | [x] -> Some x
  | _ :: tail -> last tail;;

last input;;
last [];;
last ["only"];;

This is a classic 3-pattern, remember the use of cons for the head-tail separation.

Tail-Recursive, Accumulator Pattern, Continuation Passing Style #

• Keeping things tail-recursive

  The rule of thumb:

  A recursive call is tail-recursive if and only if nothing happens after the recursive call returns. The result must be returned directly — no wrapping, no arithmetic, no cons-ing.

  Negative example — reversing a list naively: (reverse tail) @ [head] The @ happens after the recursive return → not tail-recursive → stack-overflows on long lists.

• Accumulator Pattern

  For functions that are naturally not tail-recursive, introduce an accumulator parameter and pass the growing result forward rather than building it on the return path.

  1 2 3 4 5 6 7 8 9

  (* non-tail-recursive: addition happens after the recursive return *) let rec sum = function | [] -> 0 | x :: rest -> x + sum rest (* tail-recursive: accumulator carries result forward *) let rec sum_tr acc = function | [] -> acc | x :: rest -> sum_tr (acc + x) rest

  Code Snippet 1: tail-recursive positive and negative examples

  The accumulator pattern is defunctionalised CPS — it’s what we get when the continuation is simple enough to collapse into a single state variable.

• Continuation Passing Style (CPS)

  The core shift: instead of returning a value, we receive the rest of the computation as a function (k) and decide how to invoke it.

  Style	Shape
  Direct	let y = f x in g y
  CPS	f x (fun y -> g y k)

  1 2 3 4 5

  (* CPS sum: continuation k receives the final result *) let rec sum_cps lst k = match lst with | [] -> k 0 | x :: rest -> sum_cps rest (fun r -> k (x + r))

  Code Snippet 2: cps-style example

  What CPS actually buys us (in order of practical importance):

  1. Tail recursion universally. Every call becomes a tail call — no hidden stack growth. This is why compilers use CPS internally.

  2. First-class control flow. “The rest of the program” is a function we hold. We can pass it, store it, call it multiple times, or not at all. This unlocks:

     • early exit without language support
     • backtracking / search (pass a k_success and k_failure)
     • exception handling without runtime magic
     • coroutines, async, generators

  3. Explicit, programmable execution order. In direct style the runtime controls when things return and how the stack unwinds. In CPS, we control all of that.

  The cost:

  • Readability drops. Nested lambdas, inverted flow — objectively harder to read.
  • Closure allocation. Each continuation is a heap-allocated closure → GC pressure.
  • Debugging is harder. Stack traces flatten; “who called who” disappears – all-too-familiar callback-hell
  • Usually not idiomatic OCaml. A simple accumulator handles 90% of cases cleanly.

  When CPS is actually worth it:

  • Complex early exits across multiple recursion layers
  • Backtracking / search (parsers, SAT solvers, Prolog-style)
  • Writing interpreters or compilers (explicit evaluation order)
  • Async / cooperative multitasking (deferred continuations)

  When to use the accumulator instead:

  • Any time the continuation is “add this to the running total” or similarly simple — collapse it into state, don’t heap-allocate a closure.

  The deeper reframe: A function doesn’t return a value. It receives the rest of the computation and decides how to proceed. Once we see it that way: exceptions = alternate continuations, loops = recursive continuations, async = deferred continuations.

  Relationship between the three:

  • Direct recursion: implicit stack, not tail-recursive
  • Accumulator: explicit state, tail-recursive, works when continuation is simple
  • CPS: explicit continuation, tail-recursive, works for arbitrary control flow
  • Accumulator = CPS with the continuation defunctionalised into a variable

2. Last Two Elements of a List #

Find the last two (last and penultimate) elements of a list.

1
2
3
4
5
6
7
8
9

let input = ["a" ; "b" ; "c" ; "d"];;

let rec last_two = function
  | [] | [_] -> None (* <-- collapsed the insufficient data cases into one arm *)
  | [x; y] -> Some (x, y)
  | _ :: tl -> last_two tl;;

last_two input;;
last_two ["a"];;

The list literal pattern [x; y] is sugar for x :: y :: []. When we need to look ahead by k elements, we write k binders in the terminal arm. This generalises cleanly to “last three”, “last four”, etc. — same skeleton, wider terminal arm.

3. N’th Element of a List #

Find the N’th element of a list.

1
2
3
4
5
6
7
8

let input = ["a"; "b"; "c"; "d"; "e"];;
let rec at i = function
  | _ when i < 0 -> None
  | [] -> None
  | x :: _ when i = 0 -> Some x
  | _ :: tl -> at (i - 1) tl;;

at 3 input;;

1
2
3

let rec at k = function
    | [] -> None
    | h :: t -> if k = 0 then Some h else at (k - 1) t;; (* -- the arithmetic pattern is encoded within an if-else *)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

let input = ["a"; "b"; "c"; "d"; "e"];;

let rec at i ls = match ( i, ls ) with
  | (x, _) when x < 0 -> None
  | (_, []) -> None
  | (0, x :: _) -> Some x
  | (k, _ :: tl) when k > 0 -> at ( k - 1 ) tl;;

at 12 input;;
at 3 input;;
at ( -1 ) input;;

Singleton matches cons pattern #

My attempt had some redundancies:

1. | (0, [x]) -> Some x gets subsumed into | (0, x :: _) -> Some x
   • this is because a singleton (i.e. [x]) will match the pattern: =x: _=

Balancing Guards #

The idiomatic OCaml preference: Encode constraints in the structure of the pattern (the shape of the data), not in guards.

Reach for guards only when the constraint is genuinely arithmetic or relational — something the type system cannot express structurally.

Reminders #

• the negative input case needs to be handled

4. Length of a List #

Find the number of elements of a list.

OCaml standard library has List.length but we ask that you re-implement it. Bonus for a tail recursive solution.

Solutions:

1
2
3
4
5
6

let length list =
    let rec aux n = function
      | [] -> n
      | _ :: t -> aux (n + 1) t
    in
    aux 0 list;;

This is the most idiomatic version. It keeps the name space clean by making the aux helper function scoped to the same function. It is tail-recursive based on our elaboration above on what tail-recursive means.

1
2
3

let rec len ?(acc=0) = function
  | [] -> acc
  | _ :: tl -> len ~acc:(acc+1) tl

I prefer this solution.

1
2
3
4
5
6
7
8

let input = ["a"; "b"; "c"];;
let rec len_ acc = function
    | [] -> acc
    | hd :: tl -> len_ (acc + 1) tl;;

let len ls = len_ 0 ls;;

len input

5. Reverse a List #

Reverse a list.

OCaml standard library has List.rev but we ask that you re implement it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

let input = [1;2;3];;

let rev ls =
  let rec aux ls acc = match ls with
      | [] -> acc
      | hd :: tl -> aux tl (hd :: acc)
    in
    aux ls [];;

rev input;;

Accumulator is the reversed prefix #

The mental model to lock in:

When reversing with an accumulator, the accumulator is the reversed prefix so far.

Each step takes the head of the remaining list and prepends it to that reversed prefix.

Toplevel evaluation is all-or-nothing #

If a let binding fails to typecheck, it is not defined at all. Subsequent errors (like “unbound value”) are often downstream symptoms, not the root cause.

This feels like a REPL-quirk where in the broken snippet below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

let input = [1;2;3];;

let rev ls =
  let rec aux ls acc = match ls with
      | [] -> acc
      | hd :: tl -> aux tl (acc :: hd) (* <-- this isn't right, can't cons list :: elem; should throw type error *)
    in
    aux ls [];;

rev input;;

(* actual error:
: Line 2, characters 0-3:
: 2 | rev input;;;;
:     ^^^
: Error: Unbound value rev
: Hint:   Did you mean ref?
*)

6. Palindrome #

Find out whether a list is a palindrome.

Hint: A palindrome is its own reverse.

1
2
3
4
5
6
7
8
9

let pos_input = ["x"; "a"; "m"; "a"; "x"]
let neg_input = ["a"; "b"];;

let is_palindrome ls =
    Stdlib.(=) ls (List.rev ls);; (* -- note: this explicit call is only because we're using top-level with Base defaults*)
    (* One can use either the rev function from the previous problem, or the built-in List.rev *)

is_palindrome pos_input;;
not (is_palindrome neg_input);;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

let pos_input = ["x"; "a"; "m"; "a"; "x"];;
let neg_input = ["a"; "b"]

let is_palindrome ls =
  let rev ls =
    let rec aux ls acc = match ls with
        | [] -> acc
        | hd :: tl -> aux tl (hd :: acc)
        in
        aux ls [] in
  let rec cmp a b = match (a, b) with
      | [], [] -> true
      | h_a :: t_a, h_b :: t_b -> if Stdlib.(=) h_a h_b then cmp t_a t_b else false (* -- namespacing cuz Base is default for my toplevel*)
  in
  if ls == [] then false else cmp ls (rev ls);;

is_palindrome pos_input

Structural = vs Physical Inequality == #

• Implicit behaviour: == may force int when ambiguous

  In the example below, we manually implement the cmp function but there’s an area that implicitly type-restricts the arguments to int:

  • ls = [ ]= \(\implies\) tries to make the type concrete and make it an int list
  Negative example

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  let pos_input = ["x"; "a"; "m"; "a"; "x"];; let neg_input = ["a"; "b"] let is_palindrome ls = let rev ls = let rec aux ls acc = match ls with | [] -> acc | hd :: tl -> aux tl (hd :: acc) in aux ls [] in let rec cmp a b = match (a, b) with | [], [] -> true | h_a :: t_a, h_b :: t_b -> if h_a = h_b then cmp t_a t_b else false in if ls == [] then false else cmp ls (rev ls);; is_palindrome pos_input

  Line 2, characters 14-23:
  2 | is_palindrome pos_input;;
                    ^^^^^^^^^
  Error: The value pos_input has type string/2 list/2
         but an expression was expected of type int/2 list/2
         Type string/2 is not compatible with type int/2
         File "_none_", line 1:
           Definition of type int/2
         File "_none_", line 1:
           Definition of type list/2
         File "_none_", line 1:
           Definition of type string/2

• Language Provides the Structural Equality Logic

  The = recursively walks the data structure and compares element by element. For [1;2;3] = [1;2;3], the runtime traverses both lists in lockstep, comparing heads, recursing on tails, returning true only if every element matches and both lists terminate simultaneously. We don’t write that logic because the language provides it generically for any type.

• toplevel quirks: Base vs Stdlib equality gotcha

  So in my utop, I’ve originally defaulted to JaneStreet’s Base, where the = differs from Stdlib.(=). This is an annoying gotcha.

  Jane Street’s Base library replaces polymorphic (=) with a version that requires explicit type-specific comparators. If utop is loaded with Base, writing ls = List.rev ls fails because Base(=) won’t accept 'a list without a compactor.

  Fix: use Stdlib.()= explicitly to get OCaml’s built-in structural equality.

  let is_palindrome ls = Stdlib.() ls (List.rev ls)=

  This only surfaces in a Base-defaulted utop session. In a normal .ml file without open Base, plain ()= works fine.

7. Run-Length Encoding #

Run-length encoding (RLE) is a form of lossless data compression in which runs of data (consecutive occurrences of the same data value) are stored as a single occurrence of that data value and a count of its consecutive occurrences, rather than as the original run. For example, a sequence of “green green green green green” in an image built up from colored dots could be shortened to “green x 5”.

# encode ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;
- : (int * string) list =
[(4, "a"); (1, "b"); (2, "c"); (2, "a"); (1, "d"); (4, "e")]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

let input = ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;

let encode ls =
  let rec aux accum ls =
    match (accum, ls) with
      | _, [] -> accum
      | [] , hd :: tl -> aux [(1, hd)] tl
      | (freq, symbol) :: a_tl, hd :: tl -> if Stdlib.(=) hd symbol
                                            then aux ( (freq + 1, symbol) :: a_tl ) tl (* prepend @ O(1)*)
                                            else  aux ((1, hd) :: accum ) tl (* prepend @ O(1) *)
  in
  ls |> aux [] |> List.rev;; (* List.rev @ O(n) *)

encode input;;

The official answer:

1
2
3
4
5
6
7

let encode list =
    let rec aux count acc = function
      | [] -> [] (* Can only be reached if original list is empty *)
      | [x] -> (count + 1, x) :: acc
      | a :: (b :: _ as t) -> if a = b then aux (count + 1) acc t
                              else aux 0 ((count + 1, a) :: acc) t in
    List.rev (aux 0 [] list);;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

let pack list =
    let rec aux current acc = function
      | [] -> []    (* Can only be reached if original list is empty *)
      | [x] -> (x :: current) :: acc
      | a :: (b :: _ as t) ->
         if a = b then aux (a :: current) acc t
         else aux [] ((a :: current) :: acc) t  in
    List.rev (aux [] [] list);;

let encode list =
    List.map (fun l -> (List.length l, List.hd l)) (pack list);;

Idiom: Accumulator head as “current working state” #

This is a general idiom, where the in-process group being built (the (freq, symbol) :: a_tl, hd :: tl pattern arm) has the accumulator’s head within it.

The accumulator is doing 2 things here:

1. the completed-groups history
2. the live group at the front

We’ll see this idiom show up again when doing grouping problems, run-detection, segmentation over a list

Recognition signal for this idiom: when we need to “look at the last thing we committed” while processing the next element.

Idiom: as binding for peek/lookahead pattern-matching #

The as binding we see in the model ans (ref) – b :: _ as t allows us to:

• lookahead at the structure of the tail t, and still have access to its head, b
• we’re doing a next-element peek, we don’t need to reconstruct t again when we pass the tail to the recursive call .

We see a similar idiom later, where using such as binding helps us avoid unnecessary \(O(k)\) list constructions.

Cost Trade-offs and why pre-pending + List.rev @ the end is correct #

1. We have a trade-off where at each step, our prepend happens @ \(O(1)\) and then we do a List.rev that runs at \(O(n)\)
2. We shouldn’t be tempted and:
   1. append at front accum @ [(1, hd)] to avoid the final reverse because that append happens at \(O(n)\) per step \(\implies\) the whole function would end up being \(O(n^{2})\)

Using sentinel values #

We could attempt to use a sentinel that would generalise the init arm into the general case arm – it’s like instead of saying “if no current group, start one”, we say “pretend there’s always a current group, even before the first element” – and that “pretend” value is the sentinel.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

let encode ls =
  let rec aux accum ls =
    match (accum, ls) with
    | (freq, symbol) :: a_tl, hd :: tl ->
        if Stdlib.(=) hd symbol
        then aux ((freq + 1, symbol) :: a_tl) tl
        else aux ((1, hd) :: accum) tl
    | _, [] -> accum
    | [], _ -> failwith "unreachable"
  in
  match ls with
  | [] -> []
  | hd :: tl ->
      aux [(1, hd)] tl |> List.rev

failwith "unreachable" is a code smell #

It converts a static guarantee into a runtime assertion.

The compiler cannot verify it. Refactoring can silently invalidate it. If we ever refactor the match structure and our assertion becomes wrong, we get a runtime crash instead of a compile error.

When we reach for it, treat it as a signal to restructure the match so the impossible arm simply doesn’t exist.

Design lession: the pack decomposition #

The pack decomposition is a design lesson.

The pack-then-map approach reveals an important learning:

• encode is actually two separable concerns

  1. grouping (pack) and

  2. summarising each group (map over length + head).

     Our single-pass solution fuses these, which is more efficient but less composable.

     The pack version is:

     • easier to test
     • easier to modify (what if you wanted the groups themselves, not the counts?),
     • easier to reason about

• The tradeoff is one extra \(O(n)\) pass.

8. Modified Run-Length Encoding #

Modify the result of the previous problem in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.

Since OCaml lists are homogeneous, one needs to define a type to hold both single elements and sub-lists.

We wish to make a modification. The beauty of the previous model answer is that we don’t make the struct until we know (based on the lookahead) that the upcoming value will be different. This deferred construction is useful for us because it means that we can just focus on construction and not any kind of immutable update. To construct a custom variant type, we just call a dedicated constructor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

type 'a rle =
  | One of 'a
  | Many of int * 'a

let encode list =
    let make_rle count v = if count = 1 then One v else Many (count, v) in
    let rec aux count acc = function
      | [] -> [] (* Can only be reached if original list is empty *)
      | [x] ->  (make_rle (count + 1) x ) :: acc
      | a :: (b :: _ as t) -> if Stdlib.(=) a  b then aux (count + 1) acc t
                              else aux 0 ( (make_rle (count + 1) a ) :: acc ) t in
    List.rev (aux 0 [] list);;

encode ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"];;

Using variant type as an output discriminator #

Our output type is heterogeneous by construction: some elements are singletons, some are pairs, and you need the type system to enforce that distinction rather than just convention.

Here, make_rle centralises the count = 1 decision. If we change what “single” means, it’s at that boundary.

The idiom becomes:

When output elements differ structurally based on runtime data, define a variant type.

Don’t use tuples with sentinel values (like (1, x) for singles vs (n, x) for multiples) — that’s stringly-typed thinking in disguise.

The variant makes invalid states unrepresentable at the type level.

Design Principle on Deferred Construction #

We accumulate count as a raw integer and only resolve it into One or Many at the moment we commit a group (the else branch and the [x] base case). This means the variant decision is made exactly once per group, at the group boundary.

The alternative: deciding One vs Many eagerly and then updating it — would require mutation or reconstruction.

Deferring to the boundary avoids both.

9. Duplicate the Elements of a List #

Duplicate the elements of a list.

This is still tail-recursive.

1
2
3
4
5

let rec duplicate = function
    | [] -> []
    | h :: t -> h :: h :: duplicate t;;

duplicate ["a"; "b"; "c"; "c"; "d"];;

1
2
3
4
5
6

let duplicate ls =
    let rec aux acc = function
        | [] -> acc
        | hd :: tl -> aux ( hd :: hd :: acc ) tl in
    ls |> aux [] |> List.rev ;;
duplicate ["a"; "b"; "c"; "c"; "d"];;

1
2
3
4
5
6
7
8

(* replicate each element n times *)
let replicate ls n =
  let rec aux acc = function
    | [] -> acc
    | hd :: tl ->
        let rec rep i a = if i = 0 then a else rep (i-1) (hd :: a) in
        aux (rep n acc) tl in
  ls |> aux [] |> List.rev

10. Split a List Into Two Parts; The Length of the First Part Is Given #

Split a list into two parts; the length of the first part is given.

If the length of the first part is longer than the entire list, then the first part is the list and the second part is empty.

1
2
3
4
5
6
7

let split ls k =
  let rec aux left right k = match k, right with
      | 0, _ | _, [] -> List.rev left, right
      | x, hd :: tl -> aux (hd::left) tl (x - 1)  in
  aux [] ls k;;
split ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"; "i"; "j"] 3;;
split ["a"; "b"; "c"; "d"] 5;;

the model solution looks like:

1
2
3
4
5
6

let split list n =
  let rec aux i acc = function
      | [] -> List.rev acc, []
      | h :: t as l -> if i = 0 then List.rev acc, l else aux (i - 1) (h :: acc) t;;

split ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"; "i"; "j"] 3;;

What’s interesting:

1. the i = 0 is the commit point. we don’t want to consume h, we want to return the whole remaining list

2. the as l bindst the entire h :: t pattern to l without any reconstruction – no allocation no h :: t rebuild.

   – this is exactly what we had seen before for the as binding for lookahead

   initial flawed approach

   1 2 3 4 5 6 7 8 9 10 11

   let split ls k = let rec aux left right k = match k, right with | 0, _ | _, [] -> Some (left, right) | x, hd :: tl -> if x > 0 then aux (hd::left) tl (x - 1) else None in match aux [] ls k with | None -> ls, [] | Some l, r -> (Stdlib.List.rev l, r) ;; split ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"; "i"; "j"] 3;; (* split ["a"; "b"; "c"; "d"] 5;; *)

   This gives the correct answer but it has 2 problems:

   problem
   syntax err: Some l r	The pattern matching arm Some l r doesn’t match the option-wrapped tuple correctly, it should be Some (l, r). The flawed version implies that Some takes in 2 arguments, which is not correct.
   logic issue: the None branch	We return None when x <= 0 which is redundant because the 0, _ arm catches it already so that’s a dead-path

   Also, there’s no need to option-wrap here.

   version	remark
   my flawed	option-wrapped, negative-k guard, List.rev at call site
   model ans	no wrapper, commit at i=0, h :: t as l for lookahead-free return

as binding to avoid unnecessary list construction – space-saving #

We saw earlier before for the as binding for lookahead what we could do with the h :: t as l.

To generalise a pattern, when our function needs to return a suffix of the original list unchanged, don’t deconstruct and reconstruct it.

Instead, bind it with as and return the binding directly. Reconstruction is \(O(k)\) allocation for nothing.

rule of thumb: failure cases are better candidates for option-wrapping vs boundary conditions #

In my own initial approach, I reached for the option-wrapping naturally to signal “invalid k”.

That’s alright when the caller genuinely needs to distinguish success from failure. But here the spec says “if k is too large, return the whole list and empty” — there’s no failure case, just a boundary condition.

When every input has a valid output, option adds wrapping/unwrapping overhead for no semantic gain.

The model handles the over-length case implicitly: when i > 0 and the list empties, | [] -> List.rev acc, [] fires naturally.

11. Remove the K’th Element From a List #

Remove the K’th element from a list.

The first element of the list is numbered 0, the second 1,…

This is a build-up version, we use an index counter and build it up to k.

1
2
3
4
5
6
7
8
9

let remove_at k ls =
  let rec aux i acc = function
      | [] -> List.rev acc
      | h :: t ->
         if i = k then aux (i + 1) acc t
         else aux (i + 1) (h :: acc) t in
  aux 0 [] ls;;

remove_at 1 ["a"; "b"; "c"; "d"];;

1
2
3
4
5
6
7
8

let remove_at k ls =
  let rec aux k acc = function
    | [] -> List.rev acc
    | h :: t ->
        if k = 0 then List.rev acc @ t
        else aux (k - 1) (h :: acc) t
  in
  aux k [] ls

1
2
3
4
5
6
7
8

let remove_at k ls =
  let rec aux k acc = function
    | [] -> List.rev acc
    | h :: t ->
        if k = 0 then List.rev_append acc t
        else aux (k - 1) (h :: acc) t
  in
  aux k [] ls

1
2
3
4
5
6
7
8

let remove_at k ls =
  let rec aux k l  = function
      | [] -> l
      | [x] -> if k = 0 then l else x :: l
      | (h1 :: h2 :: t) -> if k = 0 then aux (k - 1) (h2 :: l) t else aux (k - 1) (h1 :: l) (h2 :: t) in
  ls |> aux k [] |> List.rev;;

remove_at 1 ["a"; "b"; "c"; "d"];;

the model solution:

1
2
3
4
5

let rec remove_at n = function
  | [] -> []
  | h :: t -> if n = 0 then t else h :: remove_at (n - 1)  t;;

remove_at 1 ["a"; "b"; "c"; "d"];;

Notes:

1. some interesting design considerations:
   • does it early exit?
   • does it require an explicit reverse of the accumulator at the end of it?

Careful about using @ #

@ is \(O(n)\) where n is the length of the left operand — it has to walk the entire left list to find the end before appending. In our countdown version, List.rev acc @ t is \(O(k)\) for the rev plus \(O(k)\) for the @, so \(O(k)\) total. That’s fine here since it happens once at the commit point. Nevertheless, there’s a way for us to use List.rev_append to avoid using @.

It’s especially dangerous if we use it inside a recursive loop e.g.

(* O(n²) — don't do this *)
| h :: t -> aux (k-1) (acc @ [h]) t

Each step would pay \(O(current acc length)\) – summing to \(O(n^{2})\) total.

12. Insert an Element at a Given Position Into a List #

Start counting list elements with 0.

If the position is larger or equal to the length of the list, insert the element at the end. (The behavior is unspecified if the position is negative.)

1
2
3
4
5
6
7

let insert_at v k ls =
  let rec aux k acc = function
      | [] -> if k > 0 then List.rev ( v :: acc ) else List.rev acc
      | ( h :: t as l) -> if k = 0 then List.rev_append (v :: acc) l else aux (k - 1) ( h :: acc ) (t) in
  aux k [] ls;;

insert_at "alfa" 1 ["a"; "b"; "c"; "d"];;

1
2
3

let rec insert_at x n = function
    | [] -> [x]
    | h :: t as l -> if n = 0 then x :: l else h :: insert_at x (n - 1) t;;

Notes:

1. I realise that I prefer the aux helper pattern, together with the accumulator / index counter. It keeps me happy that it’s tail recursive vs not being tail recursive. At the same time, all the solutions so far have been recursive in nature an I’m wondering if there are non-recursive implementations that are possible for these problems.
2. this is good because @ the commit point, we exit (early-exit) so we don’t unnecessarily walk the list.

Iterative approaches (via List.fold_left) and when to use them #

For most of the problems so far, we could have solved it with a list fold List.fold_left and that would have been a non-recursive implementation.

“Non-recursive” typically is just hidden recursion within the library function though.

1
2
3
4
5
6
7
8
9

let insert_at v k ls =
  let _, result = List.fold_left
    (fun (i, acc) h ->
      if i = k then (i + 1, h :: v :: acc)
      else (i + 1, h :: acc))
    (0, []) ls in
  (* handle k >= length case *)
  let result = if k >= List.length ls then v :: result else result in
  List.rev result

Library combinators vs using custom, recursive aux functions #

For these exercises, we’re training the structural recursion muscle. Once that’s automatic, we’ll reach for fold/map/filter when they fit and aux when they don’t, without having to think about it.

The point where explicit aux becomes unnecessary:

• When the problem reduces cleanly to a standard traversal with no early exit and no index state. That’s the signal to reach for a library combinator instead.

13. Create a List Containing All Integers Within a Given Range #

If first argument is greater than second, produce a list in decreasing order.

1
2
3
4
5
6

let range l r =
  let rec aux acc curr final = if curr = final then curr :: acc else aux ( curr :: acc ) ( curr + 1 ) final in
  if l > r then aux [] r l else List.rev (aux [] l r);;

range 4 9;;
range 9 4;;

1
2
3
4
5
6
7

let range a b =
    let rec aux acc high low =
      if high >= low then
        aux (high :: acc) (high - 1) low
      else acc
    in
      if a < b then aux [] b a else List.rev (aux [] a b);;

1
2
3
4
5

let range a b =
    let rec aux a b =
      if a > b then [] else a :: aux (a + 1) b
    in
      if a > b then List.rev (aux b a) else aux a b;;

value of building in descending order #

we count down to the accumulator:

1
2
3
4
5
6
7
8

let range l r =
  let lo, hi = min l r, max l r in
  let rec aux acc i =
    if i < lo
    then acc
    else aux (i :: acc) (i - 1) in
  let ascending = aux [] hi in
  if l <= r then ascending else List.rev ascending

The use of lo, high variable names and the ascending alias makes this version clear to read.

stdlib approaches #

List.init n f      — generate n elements by index formula
List.filteri       — filter with index
Seq.unfold         — generate potentially infinite sequence from state

1. we could use Seq.init

   1 2 3 4

   let range l r = let lo, hi = min l r, max l r in let ascending = List.init (hi - lo + 1) (fun i -> lo + i) in if l <= r then ascending else List.rev ascending

2. we could use List.init n f as a standard list generation of n elements by a formula

   • careful on the Base vs stdlib usage though.

NOTE:

1. Seq.unfold is the functional equivalent of a stateful iterator / generator.
   • useful for things like “generate Fib seq” or “generate primes lazily”

14. Lotto: Draw N Different Random Numbers From the Set 1..M #

Draw N different random numbers from the set 1..M.

The selected numbers shall be returned in a list.

Oddly, this depends on the rand_select problem that is actually in the intermediate set of questions (TODO: permalink to the intermediate problem)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Random.init 0;

let range l r =
  let rec aux acc curr final = if curr = final then curr :: acc else aux ( curr :: acc ) ( curr + 1 ) final in
  if l > r then aux [] r l else List.rev (aux [] l r);;

let rand_select list n =
  let rec extract acc n = function
    | [] -> invalid_arg "extract: empty list"
    | h :: t -> if n = 0 then (h, acc @ t) else extract (h :: acc) (n - 1) t
  in
  let extract_rand list len =
    extract [] (Random.int len) list
  in
  let rec aux n acc list len =
    if n = 0 then acc else
      let picked, rest = extract_rand list len in
      aux (n - 1) (picked :: acc) rest (len - 1)
  in
  let len = List.length list in
  aux (min n len) [] list len;;


let lotto_select n m = rand_select ( range 1 m ) n;;

lotto_select 6 49;;

1
2
3
4
5
6
7

let lotto_select n m =
  Stdlib.Random.init 0;
  let rec aux acc n =
    if n = 0 then acc else aux (Stdlib.Random.int_in_range ~min:1 ~max:m :: acc) ( n - 1 ) in
  aux [] n;;

lotto_select 6 49;;

Careful @ the init for Random #

If we use a fixed salt for the init for the Random (i.e. Random.init(0)) then we need to be careful. If we place it within the function, then all the randoms end up being deterministic – so every output for that function ends up being the same (and being deterministic).

15. Generate a Random Permutation of the Elements of a List #

Generate a random permutation of the elements of a list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

Random.init 0;

let range l r =
  let rec aux acc curr final = if curr = final then curr :: acc else aux ( curr :: acc ) ( curr + 1 ) final in
  if l > r then aux [] r l else List.rev (aux [] l r);;

let rand_select list n =
  let rec extract acc n = function
    | [] -> invalid_arg "extract: empty list"
    | h :: t -> if n = 0 then (h, acc @ t) else extract (h :: acc) (n - 1) t
  in
  let extract_rand list len =
    extract [] (Random.int len) list
  in
  let rec aux n acc list len =
    if n = 0 then acc else
      let picked, rest = extract_rand list len in
      aux (n - 1) (picked :: acc) rest (len - 1)
  in
  let len = List.length list in
  aux (min n len) [] list len;;


let lotto_select n m = rand_select ( range 1 m ) n;;

let permutation ls =
  let arr = ls |> Array.of_list in
  let a_length = arr |> Array.length in
  let orders = lotto_select a_length a_length in
  let rec aux acc = function
      | [] -> acc
      | [x] -> ( Array.get arr (x - 1) ) :: acc
      | h :: t -> aux ( ( Array.get arr (h - 1) ) :: acc ) t
  in
  aux [] orders;;

permutation ["a"; "b"; "c"; "d"; "e"; "f"];;

The model answer modifies how the extraction logic works, it doesn’t compose things, just uses the destructive extraction like we did before.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

let permutation list =
    let rec extract acc n = function
      | [] -> raise Not_found
      | h :: t -> if n = 0 then (h, acc @ t) else extract (h :: acc) (n - 1) t
    in
    let extract_rand list len =
      extract [] (Random.int len) list
    in
    let rec aux acc list len =
      if len = 0 then acc else
        let picked, rest = extract_rand list len in
        aux (picked :: acc) rest (len - 1)
    in
    aux [] list (List.length list);;

Arithmetic #

16. Determine Whether Two Positive Integer Numbers Are Coprime #

Determine whether two positive integer numbers are coprime.

Two numbers are coprime if their greatest common divisor equals 1.

It’s odd that this is labelled a beginner question AND it depends on the gcd problem, which is tagged as an intermediate question ( see solution here).

1
2
3
4
5

let rec gcd a b =
    if b = 0 then a else gcd b (a mod b);;
let coprime a b = ( gcd a b ) = 1;;
not (coprime 20536 7826);;
coprime 13 27;;

17. Compare the Two Methods of Calculating Euler’s Totient Function #

Use the solutions of problems “Calculate Euler’s totient function \(\phi(m)\)” and “Calculate Euler’s totient function \(\phi(m)\) (improved)” to compare the algorithms.

Take the number of logical inferences as a measure for efficiency. Try to calculate \(\phi(10090)\) as an example.

Yet again, this question (though it’s a beginner question), depends on the two intermediate questions: this and this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#require "unix";;
let factors n =
    let rec aux d n =
      if n = 1 then [] else
        if n mod d = 0 then
          match aux d (n / d) with
          | (h, n) :: t when h = d -> (h, n + 1) :: t
          | l -> (d, 1) :: l
        else aux (d + 1) n
    in
      aux 2 n;;
let pow base exp =
  let rec aux acc b e =
    if e = 0 then acc else aux (acc * b) b (e - 1) in
  aux 1 base exp;; (*--- naive power fn, tail recursive*)
let phi_improved n =
  let rec aux acc = function
    | [ ] -> acc
    | (p, m) :: t -> aux ( (p - 1) * (pow p (m - 1)) * acc ) t
  in
  aux 1 (factors n);;
let phi n =
  let rec count_coprime acc d =
    if d < n then
      count_coprime (if coprime n d then acc + 1 else acc) (d + 1)
    else acc
  in
  if n = 1 then 1 else count_coprime 0 1;;

let timeit f a =
  let start = Unix.gettimeofday() in
     a |> f |> ignore;
  let stop = Unix.gettimeofday() in
     stop -. start;;

let v0 = timeit phi 10090;;
let v1 = timeit phi_improved 10090;;
v1 -. v0;;

An improvement for this would be that single-sample timing is unreliable beacuse the function Unix.gettimeofday() has a microsecond resolution and so the GC, OCaml runtime, OS scheduling would be sources of noise for that scale.

1
2
3
4
5

let timeit ?(reps=100) f a =
  let start = Unix.gettimeofday () in
  for _ = 1 to reps do f a |> ignore done;
  let stop = Unix.gettimeofday () in
  (stop -. start) /. float_of_int reps;;

18. A List of Prime Numbers #

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

let is_prime n =
  let n = max n (-n) in
  let rec aux d =
    ((d * d) > n) || (n % d <> 0 && aux (d + 1)) in
  aux 2;;
let all_primes a b =
  if a > b then [] else
  let rec aux acc curr = match (curr = b, is_prime curr)  with
      | true, true -> curr :: acc
      | true, false -> acc
      | false, true -> aux ( curr::acc ) ( curr + 1 )
      | false, false -> aux acc ( curr + 1 ) in
  aux [] a;;
List.length (all_primes 2 7920);;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

let is_prime n =
  let n = max n (-n) in
  let rec is_not_divisor d =
    d * d > n || (n mod d <> 0 && is_not_divisor (d + 1))
  in
  is_not_divisor 2

let rec all_primes a b =
  if a > b then [] else
    let rest = all_primes (a + 1) b in
    if is_prime a then a :: rest else rest;;

List.length (all_primes 2 7920);;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

let is_prime n =
  let n = max n (-n) in
  let rec aux d =
    ((d * d) > n) || (n % d <> 0 && aux (d + 1)) in
  aux 2;;
let all_primes a b =
  if a > b then [] else
    let rec aux acc curr
      = if curr > b then acc
        else if is_prime curr then aux (curr :: acc) (curr + 1)
        else aux acc (curr + 1)
    in
    aux [] a;;

List.length (all_primes 2 7920);;

TODO Binary Trees #

TODO Multi-way Trees #

TODO Graphs #

brb #

nice.