Statistical Analysis with Fold, Map, and Filter
Cambridge Computer Science Tripos Part IA -- 2024 -- Paper 1, Question 1
The chief examiner of a Tripos course would like to do some statistical analysis of the results of an exam. There are 150 students who have taken an exam consisting of 10 questions, of which each student has answered 6. If a student has not attempted a question, this is indicated by a zero in the list.
type marks = int list
(* Some sample data to work with *)
let results : marks list = [
[ 30; 25; 20; 0; 0; 18; 30; 0; 0; 8 ];
[ 27; 0; 18; 9; 0; 30; 28; 0; 0; 17 ];
[ 10; 18; 0; 7; 0; 29; 25; 0; 1; 0 ];
[ 0; 22; 15; 0; 28; 0; 0; 19; 30; 12 ];
[ 15; 0; 0; 20; 25; 0; 18; 30; 0; 10 ];
[ 0; 30; 28; 0; 0; 15; 22; 0; 18; 0 ];
[ 20; 0; 0; 12; 30; 25; 0; 0; 15; 28 ];
[ 0; 15; 22; 0; 18; 0; 30; 28; 0; 10 ];
]The mean and standard deviation of a marks value can be calculated as:
- Mean: the sum of values divided by the count
- Standard deviation: the square root of the average squared deviation from the mean (using n-1 in the denominator)
Part (a): Core higher-order functions
Define fold, map, and filter:
let rec fold (f : 'a -> 'b -> 'a) (acc : 'a) (l : 'b list) : 'a =
failwith "TODO"let () =
let sum = fold ( + ) 0 [1; 2; 3; 4; 5] in
Printf.printf "fold (+) 0 [1..5] = %d (expected 15)\n" sum;
let product = fold ( * ) 1 [1; 2; 3; 4; 5] in
Printf.printf "fold (*) 1 [1..5] = %d (expected 120)\n" product;
let reversed = fold (fun acc x -> x :: acc) [] [1; 2; 3] in
Printf.printf "reverse [1;2;3] = [%s] (expected [3;2;1])\n"
(String.concat "; " (List.map string_of_int reversed))let rec map (f : 'a -> 'b) (l : 'a list) : 'b list =
failwith "TODO"let () =
let doubled = map (fun x -> x * 2) [1; 2; 3] in
Printf.printf "map (*2) [1;2;3] = [%s] (expected [2;4;6])\n"
(String.concat "; " (List.map string_of_int doubled));
let lengths = map String.length ["hello"; "world"; "!"] in
Printf.printf "map length [\"hello\";\"world\";\"!\"] = [%s] (expected [5;5;1])\n"
(String.concat "; " (List.map string_of_int lengths))let rec filter (p : 'a -> bool) (l : 'a list) : 'a list =
failwith "TODO"let () =
let evens = filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5; 6] in
Printf.printf "filter even [1..6] = [%s] (expected [2;4;6])\n"
(String.concat "; " (List.map string_of_int evens));
let non_zero = filter (fun x -> x <> 0) [0; 3; 0; 5; 0] in
Printf.printf "filter non_zero = [%s] (expected [3;5])\n"
(String.concat "; " (List.map string_of_int non_zero))Part (b): Mean and standard deviation
The examiner evaluates performance by taking a marks value, filtering out the zeros, and then calculating the mean and standard deviation. Write a function that does this and returns an appropriate type. Remember that the result is not defined for some marks values (e.g. all zeros).
(* These are available for your use *)
let float_of_int = float_of_int
let sqrt = sqrttype stats = { mean : float; std : float }
let compute_stats (m : marks) : stats option = failwith "TODO"let () =
(* Test with the first row: [30; 25; 20; 0; 0; 18; 30; 0; 0; 8] *)
(* Non-zero values: [30; 25; 20; 18; 30; 8], mean = 131/6 ~ 21.83 *)
match compute_stats [30; 25; 20; 0; 0; 18; 30; 0; 0; 8] with
| Some s ->
Printf.printf "mean = %.2f (expected ~21.83)\n" s.mean;
Printf.printf "std = %.2f (expected ~8.33)\n" s.std
| None ->
print_endline "Got None (unexpected)";
match compute_stats [0; 0; 0; 0] with
| Some _ -> print_endline "Got Some for all-zeros (unexpected)"
| None -> print_endline "All zeros => None (correct)"Part (c): Per-question statistics
The examiner wants to assess the exam itself by looking at the mean and standard deviation for each question. First define an auxiliary function nth that returns the nth item of a list (0-indexed), then write functions to calculate per-question statistics.
let rec nth (n : int) (l : 'a list) : 'a option = failwith "TODO"
(* qmean q results: mean mark for question q across all students
(only counting students who attempted it, i.e. non-zero marks) *)
let qmean (q : int) (rs : marks list) : float = failwith "TODO"
(* qstd q results: standard deviation for question q *)
let qstd (q : int) (rs : marks list) : float = failwith "TODO"let () =
Printf.printf "Per-question statistics for sample data:\n\n";
Printf.printf " Q# Mean Std\n";
Printf.printf " -- ---- ---\n";
for q = 0 to 9 do
Printf.printf " %2d %5.1f %5.1f\n" q (qmean q results) (qstd q results)
doneExplore further
Now that you have the building blocks, try some explorations:
(* Which question had the highest average mark? *)
let best_question =
let means = List.init 10 (fun q -> (q, qmean q results)) in
let best = List.fold_left
(fun (bq, bm) (q, m) -> if m > bm then (q, m) else (bq, bm))
(-1, 0.0) means
in
Printf.printf "Best question: Q%d (mean %.1f)\n" (fst best) (snd best)(* Per-student statistics *)
let () =
List.iteri (fun i row ->
match compute_stats row with
| Some s -> Printf.printf "Student %d: mean=%.1f std=%.1f\n" i s.mean s.std
| None -> Printf.printf "Student %d: no answers\n" i
) results