Practice: recursion, higher-order functions, and syntax trees

This is a Practice chapter, not a Tutorial. There are no slides and there is no video; it is a worksheet. The tutorial walked through worked examples on screen. Here you solve the problems yourself, directly in the browser. Each problem has an editable cell seeded with failwith "not implemented" and a test cell that prints all tests passed when your solution is correct. A reference solution sits below each problem behind a collapsed Reference solution panel: try the problem first, then reveal the solution to compare.

The worksheet comes in two parts:

• Part 1: list recursion and basics (Problems 1 to 9). Pattern matching on lists and options, hand-written recursion, and tail recursion. Hand-rolling the recursion is the point here; reach for the standard library only where a problem says so.
• Part 2: the higher-order toolkit (Problems 10 to 15). The same problems you could solve with raw recursion, now done with map, filter, fold, |>, and composition. These follow on from the pipelines lecture and the fold-everywhere tutorial.
• Part 3: optimising a syntax tree (Problems 16 to 17). Recursion over a custom algebraic data type: the little arithmetic expression AST you met in the variants tutorial and the interpreter tutorial, this time rewritten to a simpler equivalent tree (constant folding and algebraic identities).

Nothing here needs anything from Module 7 or later. Difficulty rises roughly as you go, but not strictly; if you get stuck on one, skip ahead and come back.

Part 1: list recursion and basics

Problem 1: cond_dup

Write a function

cond_dup : 'a list -> ('a -> bool) -> 'a list

that takes a list and a predicate, duplicating every element that satisfies the predicate and leaving the rest unchanged. For example,

cond_dup [3; 4; 5] (fun x -> x mod 2 = 1) = [3; 3; 4; 5; 5]

let rec cond_dup l f =
  match l with
  | [] -> []
  | x :: xs ->
      if f x then x :: x :: cond_dup xs f
      else x :: cond_dup xs f

Problem 2: n_times

Write a function

n_times : ('a -> 'a) * int * 'a -> 'a

such that n_times (f, n, v) applies f to v exactly n times. For example, n_times ((fun x -> x + 1), 50, 0) = 50. If n <= 0 return v unchanged.

The argument is a tuple, not three curried arguments. Most OCaml code prefers currying, but a tuple is a fine shape too. If n_times were curried (n_times f n v), you could partially apply it; with a tuple you cannot. The signature here is deliberately the tupled one.

let rec n_times (f, n, v) =
  if n <= 0 then v
  else n_times (f, n - 1, f v)

Problem 3: range

Write a function

range : int -> int -> int list

such that range num1 num2 returns the ordered list of all integers from num1 to num2 inclusive. For example, range 2 5 = [2; 3; 4; 5] and range 7 7 = [7]. If num2 < num1, call failwith "Incorrect range".

(failwith raises a generic failure exception; you have used it since Module 1 as the placeholder body for unimplemented functions. Exceptions are introduced properly in the exceptions lecture; here we just use failwith as a signal.)

let rec range num1 num2 =
  if num2 < num1 then failwith "Incorrect range"
  else if num1 = num2 then [num1]
  else num1 :: range (num1 + 1) num2

Problem 4: unzip

Write a function

unzip : ('a * 'b) list -> 'a list * 'b list

that splits a list of pairs into a pair of lists, preserving order: the first list holds every first component, the second list every second component. For example, unzip [(1, 'a'); (2, 'b'); (3, 'c')] = ([1; 2; 3], ['a'; 'b'; 'c']).

The standard library calls this List.split; write it yourself with direct recursion. (Hint: destructure the recursive call's result with a let (xs, ys) = ... in ... pattern.)

let rec unzip = function
  | [] -> ([], [])
  | (a, b) :: rest ->
      let (xs, ys) = unzip rest in
      (a :: xs, b :: ys)

Problem 5: buckets

Write a function

buckets : ('a -> 'a -> bool) -> 'a list -> 'a list list

that partitions a list into equivalence classes. buckets equiv lst returns a list of lists, where each sublist contains mutually equivalent elements (the supplied equiv returns true between them). For example,

buckets (=) [1; 2; 3; 4] = [[1]; [2]; [3]; [4]]
buckets (=) [1; 2; 3; 4; 2; 3; 4; 3; 4]
  = [[1]; [2; 2]; [3; 3; 3]; [4; 4; 4]]
buckets (fun x y -> x mod 3 = y mod 3) [1; 2; 3; 4; 5; 6]
  = [[1; 4]; [2; 5]; [3; 6]]

The order of buckets in the output must reflect the order in which the first element of each bucket appeared in the input. The order of elements within a bucket must reflect the order in which they appeared in the input.

Assume equiv is reflexive, symmetric, and transitive (a proper equivalence relation). Just use lists; do not reach for sets or hash tables.

let buckets p l =
  let rec insert x = function
    | [] -> [[x]]
    | (y :: _ as b) :: rest when p x y -> (b @ [x]) :: rest
    | b :: rest -> b :: insert x rest
  in
  List.fold_left (fun bs x -> insert x bs) [] l

Problem 6: remove_stutter

Write a function

remove_stutter : 'a list -> 'a list

that removes stuttering (consecutive runs of the same element collapsed to one). For example,

remove_stutter [1; 2; 2; 3; 1; 1; 1; 4; 4; 2; 2] = [1; 2; 3; 1; 4; 2]

The output keeps the first element of each run and drops the rest of that run. Note this is not the same as removing all duplicates: the 1 near the end stays because it is not adjacent to the earlier 1s. (The option type may come in handy as the running "previous element seen.")

let remove_stutter l =
  let rec aux prev acc = function
    | [] -> List.rev acc
    | x :: xs ->
        (match prev with
         | Some y when y = x -> aux prev acc xs
         | _ -> aux (Some x) (x :: acc) xs)
  in
  aux None [] l

Problem 7: pairwise

Write a function

pairwise : 'a list -> ('a * 'a) list

that pairs each element with its immediate successor. For example, pairwise [1; 2; 3; 4] = [(1, 2); (2, 3); (3, 4)]. Lists with fewer than two elements have no adjacent pairs: return [].

Note each middle element appears in two pairs (once on the right, once on the left), so this is not a chunking of the list. The shape is useful whenever a computation compares neighbours: detecting ascending runs, computing differences, drawing line segments between consecutive points.

(Hint: the nested pattern x :: (y :: _ as rest) from the nested-patterns lecture matches a list with at least two elements and keeps a name for everything after x.)

let rec pairwise = function
  | x :: (y :: _ as rest) -> (x, y) :: pairwise rest
  | _ -> []

Problem 8: fold_inorder

Given a binary tree

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

write a function

fold_inorder : ('a -> 'b -> 'a) -> 'a -> 'b tree -> 'a

that performs an in-order fold over the tree: visit the left subtree, then the root, then the right subtree, threading the accumulator through. For example,

fold_inorder (fun acc x -> acc @ [x]) []
  (Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)))
  = [1; 2; 3]

The tree-folds section of the tutorial walked through this. Here, write it yourself before peeking.

let rec fold_inorder f acc t =
  match t with
  | Leaf -> acc
  | Node (l, v, r) ->
      let acc = fold_inorder f acc l in
      let acc = f acc v in
      fold_inorder f acc r

Problem 9: tail-recursive Fibonacci

The textbook recursive Fibonacci

let rec fib n =
  if n = 0 then 0
  else if n = 1 then 1
  else fib (n - 1) + fib (n - 2)

has exponential running time: computing fib 46 this way is already unbearable. But Fibonacci can be computed in linear time by carrying the current and previous values as you go. Implement

fib_tailrec : int -> int

as a tail-recursive function (each recursive call is in tail position) so that fib_tailrec 46 = 1836311903 returns instantly. (Why stop at 46? The in-browser toplevel compiles to JavaScript, where OCaml ints are 32-bit; fib 47 already overflows them. On native 64-bit OCaml you could go much further.)

let fib_tailrec n =
  let rec aux i prev cur =
    if i = n then cur
    else aux (i + 1) cur (prev + cur)
  in
  if n = 0 then 0 else aux 1 0 1

Part 2: the higher-order toolkit

Part 1 was deliberately recursion-first. Part 2 revisits the same flavour of problem, but now you should reach for List.map, List.filter, List.fold_left / List.fold_right, function composition, and the pipeline operator |>. Several of these have a one-line answer once you pick the right combinator and accumulator; finding that shape is the exercise.

Problem 10: partition

Write a function

partition : ('a -> bool) -> 'a list -> 'a list * 'a list

that splits a list into two: the elements satisfying the predicate (in original order) and the elements failing it (in original order). For example, partition (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5; 6] = ([2; 4; 6], [1; 3; 5]).

The standard library has List.partition; write your own with a single List.fold_right. (The accumulator is a pair of lists.)

let partition p xs =
  List.fold_right
    (fun x (yes, no) -> if p x then (x :: yes, no) else (yes, x :: no))
    xs ([], [])

Problem 11: flat_map

Write a function

flat_map : ('a -> 'b list) -> 'a list -> 'b list

that applies f (which returns a list) to every element and concatenates the results. For example, flat_map (fun x -> [x; x * 10]) [1; 2; 3] = [1; 10; 2; 20; 3; 30].

flat_map is map followed by concat (the standard library calls it List.concat_map). It is the workhorse behind list comprehensions in other languages, and is the bind of the list monad you will meet in Module 8.

let flat_map f xs =
  List.fold_right (fun x acc -> f x @ acc) xs []

Problem 12: compose_all

Write a function

compose_all : ('a -> 'a) list -> 'a -> 'a

that composes a list of functions into one, applying them left-to-right. For example, compose_all [f; g; h] x should compute h (g (f x)): f first, then g, then h. An empty list composes to the identity function. For example,

compose_all [(fun x -> x + 1); (fun x -> x * 2); (fun x -> x - 3)] 10 = 19

(that is ((10 + 1) * 2) - 3).

This follows directly from the composition lecture: you are folding the composition operator over a list of functions, with the identity function as the seed.

let compose_all fs =
  List.fold_left (fun acc f -> fun x -> f (acc x)) (fun x -> x) fs

Problem 13: run_length_encode

Write a function

run_length_encode : 'a list -> ('a * int) list

that compresses each run of equal adjacent elements into a single (element, count) pair. For example,

run_length_encode [1; 1; 1; 2; 3; 3] = [(1, 3); (2, 1); (3, 2)]

This is the counting cousin of remove_stutter from Problem 6: instead of dropping the repeats, you tally them.

let run_length_encode xs =
  List.fold_right
    (fun x acc ->
      match acc with
      | (y, n) :: rest when y = x -> (y, n + 1) :: rest
      | _ -> (x, 1) :: acc)
    xs []

Problem 14: running_sum

Write a function

running_sum : int list -> int list

that returns the list of prefix sums: each output element is the sum of all input elements up to and including that position. For example, running_sum [1; 2; 3; 4] = [1; 3; 6; 10].

This is a scan (sometimes scanl): like a fold, but it keeps every intermediate accumulator instead of only the final one.

let running_sum xs =
  List.rev
    (snd
       (List.fold_left
          (fun (total, acc) x -> let t = total + x in (t, t :: acc))
          (0, []) xs))

Problem 15: dot_product

Write a function

dot_product : int list -> int list -> int

that treats the two lists as vectors of equal length and returns the sum of the element-wise products. For example, dot_product [1; 2; 3] [4; 5; 6] = 32 (that is 1*4 + 2*5 + 3*6).

Write it as a pipeline: combine the two lists element-wise with List.map2 (the standard library's two-list map; it raises Invalid_argument on a length mismatch, which is fine here since the inputs are promised to have equal length), then pipe the products into a fold that sums them.

let dot_product xs ys =
  List.map2 ( * ) xs ys
  |> List.fold_left ( + ) 0

Part 3: optimising a syntax tree

The last two problems leave lists behind and work on a small abstract syntax tree (AST) for arithmetic expressions: integer literals, variables, and the three binary operators. This is the same kind of tree you built in the variants tutorial and interpreted in the interpreter tutorial:

type expr =
  | Int of int
  | Var of string
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr

Those tutorials evaluated a tree to a number. Here you do something a compiler does before evaluating: rewrite the tree into a smaller, equivalent tree. Both problems are recursions with the same shape as the tree folds in Part 1's Problem 8, but the result is itself an expr, not a number, so the recursion rebuilds the tree as it goes.

Problem 16: constant_fold

Write a function

constant_fold : expr -> expr

that replaces any subexpression whose operands are both integer literals with the computed literal, working bottom-up. Variables (and any operator with a variable somewhere underneath) stay. For example, constant_fold (Mul (Add (Int 5, Int 3), Int 2)) = Int 16, while constant_fold (Add (Mul (Int 2, Int 3), Var "x")) = Add (Int 6, Var "x") (the 2 * 3 folds to 6, but the + x stays because x is not known).

The shape: recurse into both children first, then look at what they reduced to. If both are Int, compute the result; otherwise rebuild the node with the simplified children.

let rec constant_fold e =
  match e with
  | Int _ | Var _ -> e
  | Add (a, b) ->
      (match constant_fold a, constant_fold b with
       | Int x, Int y -> Int (x + y)
       | a', b' -> Add (a', b'))
  | Sub (a, b) ->
      (match constant_fold a, constant_fold b with
       | Int x, Int y -> Int (x - y)
       | a', b' -> Sub (a', b'))
  | Mul (a, b) ->
      (match constant_fold a, constant_fold b with
       | Int x, Int y -> Int (x * y)
       | a', b' -> Mul (a', b'))

Problem 17: simplify

Constant folding only fires when both operands are literals. Real optimisers also use algebraic identities that fire when just one operand is a particular literal. Write

simplify : expr -> expr

that does everything constant_fold does, and in addition applies:

• e + 0 = e and 0 + e = e
• e - 0 = e
• e * 1 = e and 1 * e = e
• e * 0 = 0 and 0 * e = 0

For example, simplify (Add (Mul (Var "x", Int 0), Mul (Int 1, Var "y"))) = Var "y": the x * 0 collapses to 0, the 1 * y collapses to y, and then 0 + y collapses to y.

let rec simplify e =
  match e with
  | Int _ | Var _ -> e
  | Add (a, b) ->
      (match simplify a, simplify b with
       | Int x, Int y -> Int (x + y)
       | Int 0, e | e, Int 0 -> e
       | a', b' -> Add (a', b'))
  | Sub (a, b) ->
      (match simplify a, simplify b with
       | Int x, Int y -> Int (x - y)
       | e, Int 0 -> e
       | a', b' -> Sub (a', b'))
  | Mul (a, b) ->
      (match simplify a, simplify b with
       | Int x, Int y -> Int (x * y)
       | Int 0, _ | _, Int 0 -> Int 0
       | Int 1, e | e, Int 1 -> e
       | a', b' -> Mul (a', b'))

What you should be able to do now

By the end of these seventeen problems you should be comfortable with:

• Pattern-matching on lists ([], x :: xs) and on options (None, Some _).
• Writing your own recursion when the standard library does not quite have the shape you need.
• Carrying an accumulator through a tail-recursive helper, and reversing at the end when order matters.
• Reaching for List.fold_left / List.fold_right when the answer is built from the whole list rather than each element independently.
• Recognising when a problem is asking for an explicit "previous element" or "running bucket list," and the shape of the helper function that follows.
• Choosing the right higher-order combinator (map, filter, fold, composition) instead of hand-writing the recursion, and chaining them into a |> pipeline that reads top-to-bottom.
• Using a pair-valued accumulator (partition, running_sum) and composing functions into new functions (compose_all).
• Recursing over a custom algebraic data type and rebuilding it, not just summarising it: a tree-to-tree rewrite like the constant folding and algebraic simplification an optimiser performs.

Module 7 introduces side effects and the OCaml module system: references and mutation, arrays, exceptions (the formal counterpart to the failwith shortcut we used in Problem 3), streams, memoisation, signatures, and functors. Higher-order functions remain in play throughout.

Sources

Most of Part 1 is drawn from Assignment 1 of the instructor's CS3100: Paradigms of Programming course at IIT Madras (Monsoon 2025), with prose, test harnesses, and reference solutions rewritten for this NPTEL course; Problems 4 and 7 are new here. Part 2 (Problems 10 to 15) and Part 3 (Problems 16 to 17) are also new, extending the higher-order toolkit and the arithmetic AST from the Module 4 to Module 6 lectures and tutorials.