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)