Each exercise below runs in the browser, and its test cell checks it
there too: whether the answers are right, and also whether the function
is tail recursive, how its work grows, and whether it
sidesteps the exercise with a library function. Edit an exercise (and press ▶ or Ctrl-Enter) and its
test runs again: unfold “Tests” under it
to see what the checks found. The checks load a copy of your code, rewritten as each
check needs; the code you see runs as written.
1. Make it tail recursive
Notes, exercise 3.1: code an iterative version of the sum of a
list. This version is correct but not iterative: the addition waits for
the recursive call to return. The test asks the compiler which recursive
calls are tail calls.
let rec go acc = function
| [] -> acc
| x :: xs -> go (acc + x) xs
let isum xs = go 0 xslet () =
let t = Focs_check.tailcheck "isum-ex" in
Focs_check.print_tail t;
if not (Focs_check.is_tail_recursive t) then failwith "isum is not iterative yet"
let () = ignore (Focs_check.load ~as_:"I" "isum-ex")
;;
let () =
if not (I.isum [] = 0 && I.isum [1; 2; 3; 4] = 10 && I.isum [3; -5; 2] = 0)
then failwith "isum gives a wrong answer";
print_endline "isum is right, and iterative"
Try: an accumulator, let rec go acc = function [] -> acc | x :: xs -> go (acc + x) xs
and let isum xs = go 0 xs. Then put the recursive call
inside a try … with and see it flagged again.
2. Fix the complexity
Lecture 3: this rev is correct, but each @
copies the list built so far. The test runs a counting copy of your code
on lists of growing length and fits how the work grows.
let rec rev_app xs acc = match xs with [] -> acc | x :: xs -> rev_app xs (x :: acc)
let rev xs = rev_app xs []let () = ignore (Focs_check.load_counting ~as_:"R" "rev-ex")
;;
let () =
if R.rev [1; 2; 3] <> [3; 2; 1] then failwith "rev gives a wrong answer";
let g =
Focs_check.growth
(Focs_check.measure ~as_:"R" ~input:"fun n -> List.init n Fun.id" ~call:"R.rev"
[ 64; 128; 256; 512; 1024 ])
in
Focs_check.print_growth g;
if g.model <> "O(n)" then failwith ("rev should be O(n), not " ^ g.model)
Try: an accumulator, as in the lecture's rev_app.
The table's ratios fall from about 4 to about 2 as the input doubles.
List.rev would pass too: library functions are counted,
not free.
3. No library functions
Decision D8: in exercise 3.1 the point is the accumulator pattern, so
library functions are not allowed. This answer is correct, and tail
recursive, but it uses List.fold_left. The check reads the
typed code, so renaming the module does not get round it.
let rec go acc = function [] -> acc | x :: xs -> go (acc + x) xs
let isum xs = go 0 xslet () =
let broken = Focs_check.check_uses [ Focs_check.Forbid_library [] ] "fold-ex" in
List.iter (fun (line, msg) -> Printf.printf "line %d: %s\n" line msg) broken;
if broken <> [] then failwith "library functions are not allowed here";
let t = Focs_check.tailcheck "fold-ex" in
Focs_check.print_tail t;
if not (Focs_check.is_tail_recursive t) then failwith "isum is not iterative";
print_endline "no library functions, and iterative"
Try: module L = List let isum xs = L.fold_left ( + ) 0 xs,
or Stdlib.List.fold_left, or open List. All
are caught. +, @ and failwith
stay allowed.
4. Find an input that breaks it
Notes, exercise 4.3: two versions of zip differ. Rather
than describe the difference, give an input on which they disagree.
(Both are hidden; one is the notes' version, the other leaves out the
wildcard case.)
let rec zip1 xs ys =
match xs, ys with
| (x :: xs, y :: ys) -> (x, y) :: zip1 xs ys
| _ -> []
let rec zip2 xs ys =
match xs, ys with
| (x :: xs, y :: ys) -> (x, y) :: zip2 xs ys
| ([], []) -> []
| _ -> raise (Match_failure ("zip2", 0, 0))
let disagree (xs, ys) =
match zip2 xs ys with
| r -> r <> zip1 xs ys
| exception Match_failure _ -> truelet breaking : int list * int list = ([1; 2], [3])let () =
Printf.printf "zip1 gives %d pairs; zip2 %s\n"
(List.length (zip1 (fst breaking) (snd breaking)))
(match zip2 (fst breaking) (snd breaking) with
| r -> Printf.sprintf "gives %d pairs" (List.length r)
| exception Match_failure _ -> "fails with Match_failure")
let () =
if not (disagree breaking) then failwith "they agree on this input: try another"
else print_endline "found it: they disagree"
More demos
Examples first: write examples for
evens, tails and split (notes
exercises 3.3, 3.5 and 4.2); they are checked against hidden correct
versions and against wrong ones (Caught N of M).
Predict the next step: rev
with an accumulator, and the three traversals, choosing each next
state before it is shown.