oCamlCase
Exercise E3 · Hard

Iteration and Search

Implement the two fundamental iteration patterns from scratch, then use partial application to build a family of specialized utilities on top of them. This exercise ties together currying, higher-order functions, and tail recursion.

The challenge
Build iter and first, then derive everything else
Hard

Start by implementing the two core iteration functions. Then use them as building blocks to solve concrete problems. The goal is to get comfortable using partial application to specialize a general function into a specific one.

  • 01Implement iter f n start: applies f exactly n times to start. Must be tail recursive.
  • 02Use iter to define double_n_times: doubles a number exactly n times. Use partial application.
  • 03Use iter to define add_step and count_by_3: add a fixed amount n times.
  • 04Implement first pred start: returns the smallest integer at or above start for which pred holds.
  • 05Use first to define first_divisible_by n start.
  • 06Use first to define first_perfect_square start. A number x is a perfect square if floor(sqrt(x))^2 = x.
  • 07Use first to define natural_sqrt n: compute floor(sqrt(n)) without using any floating-point square root.

Starter code

search.ml 
(* Definite iteration *)
let rec iter (f : int -> int) (n : int) (start : int) =
  (* TODO *)
  start

let double_n_times n =
  (* TODO: partial application of iter *)
  iter (fun x -> x) n

let add_step step =
  (* TODO: partial application of iter *)
  iter (fun x -> x) step

let count_by_3 =
  (* TODO: partial application of add_step *)
  add_step 0

(* Indefinite iteration *)
let rec first (pred : int -> bool) (start : int) =
  (* TODO *)
  start

let first_divisible_by n start =
  (* TODO *)
  0

let first_perfect_square start =
  (* TODO: use int_of_float (sqrt (float_of_int x)) *)
  0

let natural_sqrt n =
  (* TODO: use first to find the first k where k*k > n *)
  0

Hints

For iter, the base case is when n < 1: return start as is. For the recursive case, call iter again with n - 1 and f start as the new starting value. This keeps the recursion in tail position.

For double_n_times, notice that iter (fun x -> x * 2) is a function of type int -> int -> int. Supplying just iter (fun x -> x * 2) gives you a function that still expects n and start. That is exactly double_n_times.

For natural_sqrt, use first to find the first k where k * k > n, starting from 1. Then subtract 1 from the result.

Key insight

Every derived function is just iter or first with one or more arguments already fixed. Recognize this pattern and the implementations become one-liners.

Watch out

first_perfect_square uses OCaml's built-in sqrt to check whether a number is a perfect square, but natural_sqrt must not. The whole point of natural_sqrt is to compute the integer square root using only integer arithmetic through first.

+ Show solution try it yourself first
search_solution.ml 
(* Definite iteration *)
let rec iter (f : int -> int) (n : int) (start : int) =
  if n < 1 then start
  else iter f (n - 1) (f start)

let double_n_times = iter (fun x -> x * 2)
(* double_n_times : int -> int -> int *)

let add_step step = iter (fun x -> x + step)
let count_by_3 = add_step 3

(* Indefinite iteration *)
let rec first (pred : int -> bool) (start : int) =
  if pred start then start
  else first pred (start + 1)

let first_divisible_by n =
  first (fun x -> x mod n = 0)

let first_perfect_square start =
  let is_square x =
    let s = int_of_float (sqrt (float_of_int x)) in
    s * s = x
  in
  first is_square start

let natural_sqrt n =
  (first (fun k -> k * k > n) 1) - 1

let () =
  Printf.printf "1 doubled 4 times: %d\n"
    (double_n_times 4 1);
  Printf.printf "count_by_3, 5 steps from 0: %d\n"
    (count_by_3 5 0);
  Printf.printf "First multiple of 7 from 50: %d\n"
    (first_divisible_by 7 50);
  Printf.printf "First perfect square from 20: %d\n"
    (first_perfect_square 20);
  Printf.printf "floor(sqrt(50)): %d\n"
    (natural_sqrt 50)

Walkthrough

iter. The function simply decrements n and applies f to start on each recursive call. Both updated values are passed forward as arguments, so there is nothing pending after the recursive call. This makes it tail recursive.

double_n_times. Supplying iter (fun x -> x * 2) produces a function waiting for n and start. That is exactly the type of double_n_times. No wrapper function is needed.

add_step and count_by_3. add_step takes step and returns a partially applied iter. Then count_by_3 partially applies add_step with 3, giving a function of type int -> int -> int. Two levels of partial application, both one-liners.

natural_sqrt. The key insight is that the first k where k * k > n overshoots by exactly one step. Subtracting 1 gives the floor of the square root. No floating-point arithmetic involved.

Going further

Once everything works, try these extensions:

  • Generalize iter to work with any type, not just int. What does the signature look like?
  • Write iterate_until f pred start that applies f repeatedly until pred holds, similar to first but with a custom step function.
  • Use iter to implement the Fibonacci sequence: fib n via a pair accumulator (a, b) where each step becomes (b, a + b).
extension.ml 
(* Fibonacci using iter with a pair accumulator *)
let fib n =
  let step (a, b) = (b, a + b) in
  let rec loop acc k =
    if k < 1 then fst acc
    else loop (step acc) (k - 1)
  in
  loop (0, 1) n

fib 10  (* 55 *)
← Playlist Back to Home