Examples first

Before writing a function, say what it should do, with examples. Each of yours is checked against correct versions of the function, which it must agree with, and against wrong ones, each made from a mistake people really make: a good set of examples tells every wrong version from the right ones. This is Examplar's idea, here for three exercises from the FoCS notes.

Write your examples as a list of things that should be true. Run the cell (or edit it) and the test under it says how many wrong versions they catch. One example is there to start you off; it catches some, not all.

evens: every other element

Notes, exercise 3.3. evens l is the even-numbered elements of l: the 2nd, 4th, 6th and so on, counting the head as the 1st.

let rec evens = function _ :: x :: xs -> x :: evens xs | _ -> [] let evens_wheats = [ {|let rec evens = function _ :: x :: xs -> x :: evens xs | _ -> []|}; {|let evens l = let rec go acc = function _ :: x :: xs -> go (x :: acc) xs | _ -> List.rev acc in go [] l|} ] let evens_chaffs = [ ("counts from 0, so gives the 1st, 3rd, 5th, ...", {|let rec evens = function x :: _ :: xs -> x :: evens xs | [x] -> [x] | [] -> []|}); ("reads even-numbered as even values", {|let evens xs = List.filter (fun x -> x mod 2 = 0) xs|}); ("forgets the one-element list", {|let rec evens = function [] -> [] | _ :: x :: xs -> x :: evens xs | [_] -> raise (Match_failure ("", 0, 0))|}); ("drops only the first element, then steps by one", {|let rec evens = function _ :: x :: xs -> x :: evens (x :: xs) | _ -> []|}); ("uses an accumulator and never reverses it", {|let evens l = let rec go acc = function _ :: x :: xs -> go (x :: acc) xs | _ -> acc in go [] l|}) ] let examples = [ evens [ 1; 2; 3; 4 ] = [ 2; 4 ] ] let r = Focs_check.examplar ~wheats:evens_wheats ~chaffs:evens_chaffs "evens-examples" let () = assert (r.invalid = 0 && r.caught = r.chaffs)

tails: every tail of a list

Notes, exercise 3.5. tails l is the list of all of l's tails, longest first. [] is a tail too: tails [1; 2] is [[1; 2]; [2]; []].

let rec tails = function [] -> [ [] ] | _ :: xs as l -> l :: tails xs let tails_wheats = [ {|let rec tails = function [] -> [ [] ] | _ :: xs as l -> l :: tails xs|}; {|let tails l = let rec go acc = function [] -> List.rev ([] :: acc) | _ :: xs as l -> go (l :: acc) xs in go [] l|} ] let tails_chaffs = [ ("leaves out the empty tail", {|let rec tails = function [] -> [] | _ :: xs as l -> l :: tails xs|}); ("stops at a one-element list, and fails on []", {|let rec tails = function [x] -> [ [x] ] | _ :: xs as l -> l :: tails xs | [] -> raise (Match_failure ("", 0, 0))|}); ("leaves out the whole list", {|let rec tails = function [] -> [ [] ] | _ :: xs -> xs :: tails xs|}); ("gives them shortest first", {|let tails l = let rec go acc = function [] -> [] :: acc | _ :: xs as l -> go (l :: acc) xs in go [] l|}); ("gives the prefixes instead", {|let rec tails = function [] -> [ [] ] | x :: xs -> [] :: List.map (fun p -> x :: p) (tails xs)|}) ] let examples = [ tails [] = [ [] ] ] let r = Focs_check.examplar ~wheats:tails_wheats ~chaffs:tails_chaffs "tails-examples" let () = assert (r.invalid = 0 && r.caught = r.chaffs)

split: non-negative and negative

Notes, exercise 4.2. split l is a pair: the non-negative numbers of l, and the negative ones, each in the order they came in l.

let rec split = function | [] -> ([], []) | x :: xs -> let ps, ns = split xs in if x >= 0 then (x :: ps, ns) else (ps, x :: ns) let split_wheats = [ {|let rec split = function | [] -> ([], []) | x :: xs -> let ps, ns = split xs in if x >= 0 then (x :: ps, ns) else (ps, x :: ns)|}; {|let split l = (List.filter (fun x -> x >= 0) l, List.filter (fun x -> x < 0) l)|} ] let split_chaffs = [ ("puts 0 with the negatives", {|let split l = (List.filter (fun x -> x > 0) l, List.filter (fun x -> x <= 0) l)|}); ("gives the negatives first", {|let split l = (List.filter (fun x -> x < 0) l, List.filter (fun x -> x >= 0) l)|}); ("loses the negatives", {|let split l = (List.filter (fun x -> x >= 0) l, [])|}); ("decides from the head, and puts the whole list on that side", {|let split = function [] -> ([], []) | x :: _ as l -> if x >= 0 then (l, []) else ([], l)|}); ("uses two accumulators and never reverses them", {|let split l = let rec go ps ns = function | [] -> (ps, ns) | x :: xs -> if x >= 0 then go (x :: ps) ns xs else go ps (x :: ns) xs in go [] [] l|}) ] let examples = [ split [ 1; -2 ] = ([ 1 ], [ -2 ]) ] let r = Focs_check.examplar ~wheats:split_wheats ~chaffs:split_chaffs "split-examples" let () = assert (r.invalid = 0 && r.caught = r.chaffs)