FoCS: exercises that check more than answers

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 xs let () = 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 xs let () = 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 _ -> true let 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