Predict the next step

Watching a computation teaches little; predicting it first teaches more. Each cell below records the states of a computation with Focs_check.Steps, and shows them with <x-stepper>: press ▶ and, for the first few steps and the last, choose what comes next before it is shown. The wrong choices are mistakes people make, and choosing one says what it gets wrong.

Lists are drawn as chains of cells, and a cell shared by two lists is drawn once, with two arrows to it: the sharing is the program's own, found by physical equality. From a script, step(), back() and reset() drive it, and mode = "lecture" stops it asking, as a slide would.

Reversing a list with an accumulator

(* This cell builds the steps shown below it. It doesn't animate rev by magic: it runs its own copy of rev and records a snapshot of the variables at each call, plus some wrong snapshots for the reader to choose among. Focs_check.Steps turns the snapshots into box-and-pointer diagrams; the <x-stepper> element draws and animates them. *) open Focs_check (* [1; 2; 3], for the labels above each diagram. *) let show l = "[" ^ String.concat "; " (List.map string_of_int l) ^ "]" (* The code the reader sees beside the diagram. Each snapshot says which of its lines runs next: line 3 (the [] case) once xs is empty, line 4 (the :: case) before that. *) let rev_code = {|let rec go xs acc = match xs with | [] -> acc | x :: rest -> go rest (x :: acc) let rev l = go l []|} let line xs = if xs = [] then 3 else 4 let rev_steps l = let t = Steps.create () in (* A snapshot of one call go xs acc: the original list l, and xs and acc. Steps.list records the actual list cells, so where xs is a tail of l the diagram draws one chain of cells with two arrows into it: the sharing is the program's own. acc is highlighted, since it's what changes. *) let st label xs acc = Steps.state ~label ~line:(line xs) ~highlight:[ Steps.list string_of_int acc ] [ ("l", Steps.list string_of_int l); ("xs", Steps.list string_of_int xs); ("acc", Steps.list string_of_int acc) ] in let go_label xs acc = Printf.sprintf "go %s %s" (show xs) (show acc) in (* The first snapshot: rev l has just called go l []. *) Steps.add t (st ("rev " ^ show l ^ " = " ^ go_label l []) l []); (* Our own go, the same as the code shown, recording each call it makes. *) let rec go xs acc = match xs with | [] -> acc | x :: rest -> let acc' = x :: acc in (* The wrong next states, each from a misconception, with what it gets wrong. These are the options the reader chooses among, next to the right one. *) let wrong = [ ( Printf.sprintf "x :: acc puts %d in front of the accumulator, not after it." x, acc @ [ x ] ); (* adds x at the end *) ("Nothing is lost: the head of the list moves onto the accumulator.", acc ); (* forgets x *) ("The accumulator is extended, not replaced: it keeps what it had.", [ x ] ) ] (* replaces acc by [x] *) (* At the first call, acc = [] makes some of these the same as the right answer, or as each other: keep only those that differ. *) |> List.filter (fun (_, a) -> a <> acc') |> List.sort_uniq (fun (_, a) (_, b) -> compare a b) |> List.map (fun (why, a) -> (why, st (go_label rest a) rest a)) in (* The right next state: the call go rest acc' that is about to happen, offered among the wrong ones. *) Steps.add t ~choices:wrong (st (go_label rest acc') rest acc'); go rest acc' in let r = go l [] in (* The last step: go [] acc returns acc. The wrong option is the list itself, for those who expect rev to give back its input. *) Steps.add t ~choices:[ ("go returns the accumulator, which holds the elements in the \ reverse of the order they were met.", Steps.state ~label:("= " ^ show l) [ ("result", Steps.list string_of_int l) ]) ] (Steps.state ~label:("= " ^ show r) [ ("result", Steps.list string_of_int r) ]); t (* Show the steps under this cell, with the code beside them. In predict mode (the default) the reader chooses the next state for the first two steps and the last; ~mode:"lecture" would just step. *) let () = Steps.show ~title:"rev [1; 2; 3; 4]" ~code:rev_code (rev_steps [ 1; 2; 3; 4 ])

Traversing a tree: preorder, inorder, postorder

Each step visits one node: it's marked, visiting points to it, and it joins the visited list, which is the traversal's output so far. When asked what comes next?, choose which node is visited next. Each option is labelled with the node it visits and the output that would give. The wrong options are the nodes the other two orders would visit at that point.

open Focs_check type 'a tree = Lf | Br of 'a * 'a tree * 'a tree let view = function Lf -> None | Br (v, l, r) -> Some (v, [ l; r ]) let rec preorder = function Lf -> [] | Br (v, l, r) -> (v :: preorder l) @ preorder r let rec inorder = function Lf -> [] | Br (v, l, r) -> inorder l @ (v :: inorder r) let rec postorder = function Lf -> [] | Br (v, l, r) -> postorder l @ postorder r @ [ v ] let rec find v = function | Lf -> None | Br (w, l, r) as t -> if v = w then Some t else (match find v l with Some t -> Some t | None -> find v r) let code_of = function | "preorder" -> "let rec preorder = function\n | Lf -> []\n | Br (v, l, r) -> (v :: preorder l) @ preorder r" | "inorder" -> "let rec inorder = function\n | Lf -> []\n | Br (v, l, r) -> inorder l @ (v :: inorder r)" | _ -> "let rec postorder = function\n | Lf -> []\n | Br (v, l, r) -> postorder l @ postorder r @ [ v ]" let orders = [ ("preorder", preorder, "That is preorder: a node comes before its subtrees."); ("inorder", inorder, "That is inorder: the left subtree comes before the node."); ("postorder", postorder, "That is postorder: both subtrees come before the node.") ] let traversal_steps name t = let _, order, _ = List.find (fun (n, _, _) -> n = name) orders in let s = Steps.create () in let tree = Steps.tree string_of_int view t in (* A snapshot just after visiting a node: the whole tree t, the subtree being visited, and the output so far. The label says which node was visited and what the output is now, so the options can be told apart. *) let show l = "[" ^ String.concat "; " (List.map string_of_int l) ^ "]" in let st v here visited = let here_v = Steps.tree string_of_int view here in Steps.state ~label:(Printf.sprintf "visits %d: output so far %s" v (show visited)) ~line:3 ~highlight:[ here_v ] [ ("t", tree); ("visiting", here_v); ("visited", Steps.list string_of_int visited) ] in Steps.add s (Steps.state ~label:(name ^ " t: nothing visited yet") [ ("t", tree); ("visited", Steps.list string_of_int []) ]); let seq = order t in List.iteri (fun i v -> let before = List.filteri (fun j _ -> j < i) seq in let here x = Option.get (find x t) in let wrong = List.filter_map (fun (n, o, why) -> match List.nth_opt (o t) i with | Some w when n <> name && w <> v && not (List.mem w before) -> Some (w, why) | _ -> None) orders |> List.sort_uniq (fun (a, _) (b, _) -> compare a b) |> List.map (fun (w, why) -> (why, st w (here w) (before @ [ w ]))) in Steps.add s ~choices:wrong (st v (here v) (before @ [ v ]))) seq; s let t = Br (4, Br (2, Br (1, Lf, Lf), Br (3, Lf, Lf)), Br (6, Br (5, Lf, Lf), Lf)) let () = List.iter (fun (name, _, _) -> Steps.show ~title:name ~code:(code_of name) ~ask:6 (traversal_steps name t)) orders