How tcons works

For after Tick 3. A functional array is a tree. The element at subscript 1 is at the root; the left subtree holds the even subscripts and the right subtree the odd ones from 3: subscript 2k is at subscript k of the left subtree, and 2k+1 at subscript k of the right. So below the root, 2 is on the left and 3 on the right, and below 2 come 4 and 6.

let rec tcons v = function
  | Lf -> Br (v, Lf, Lf)
  | Br (w, t1, t2) -> Br (v, tcons w t2, t1)

Below, t holds 1 to 15, each at its own subscript, so you can read a node's subscript off it. Each call of tcons on a Br is shown in two steps: first t1 and t2 swap places, then v goes in at the root, and the old root w is carried down into what is now the left subtree, by the call tcons w t2. The element being carried is drawn on its own, under the tree.

(* This cell builds the steps shown below it. To change the example, change t or v at the bottom. The elements must all be different: each is drawn as one node, which moves from state to state. *) open Focs_check type 'a tree = Lf | Br of 'a * 'a tree * 'a tree let code = {|let rec tcons v = function | Lf -> Br (v, Lf, Lf) | Br (w, t1, t2) -> Br (v, tcons w t2, t1)|} (* A tree in the making: Slot is the empty tree that tcons has reached, drawn as a node, so that the element carried can be seen to go in. *) type part = PLf | Slot | PBr of int * part * part let rec part = function Lf -> PLf | Br (v, l, r) -> PBr (v, part l, part r) (* Steps.tree gives a node the same id in every state if it is the same block, so draw each element as one block, whatever tree it is in. *) let blocks = Hashtbl.create 16 let block v = match Hashtbl.find_opt blocks v with | Some b -> b | None -> let b = ref v in Hashtbl.add blocks v b; b let leaf = ref 0 and slot = ref 0 let draw p = let kids = ref [] in let rec go = function | PLf -> leaf | Slot -> kids := (slot, ("Lf", [])) :: !kids; slot | PBr (v, l, r) -> let b = block v in let l = go l and r = go r in kids := (b, (string_of_int v, [ l; r ])) :: !kids; b in let root = go p in Steps.tree Fun.id (fun b -> if b == leaf then None else List.assq_opt b !kids) root (* The subtree tcons has reached, with Lf as the slot. *) let here = function Lf -> Slot | t -> part t (* The states of tcons v t. fill puts a subtree where tcons has got to in the tree: at first, that's the whole tree. *) let tcons_steps v t = let s = Steps.create () in let st ?note ~line ~label tree v focus = Steps.state ~line ~label ?note ~highlight:[ draw focus ] [ ("tree", draw tree); ("v", draw (PBr (v, PLf, PLf))) ] in Steps.add s (st ~line:(if t = Lf then 2 else 3) ~label:(Printf.sprintf "tcons %d t" v) ~note:"Each element of t is at its own subscript." (here t) v (here t)); let rec go fill v t = match t with | Lf -> let one = PBr (v, PLf, PLf) in Steps.add s (Steps.state ~line:2 ~highlight:[ draw one ] ~label:(Printf.sprintf "tcons %d Lf = Br (%d, Lf, Lf)" v v) ~note:"Done: the new element is at subscript 1, and each element is \ now one subscript along from where it was." [ ("tree", draw (fill one)) ]) | Br (w, t1, t2) -> let swapped = PBr (w, part t2, part t1) in Steps.add s (st ~line:3 ~label:(Printf.sprintf "tcons %d (Br (%d, t1, t2)): swap t1 and t2" v w) ~note:"The old left subtree t1 will be the right subtree of the result, \ unchanged." (fill swapped) v swapped); let fill' x = fill (PBr (v, x, part t1)) in Steps.add s (st ~line:3 ~label:(Printf.sprintf "= Br (%d, tcons %d t2, t1)" v w) ~note:(Printf.sprintf "%d takes %d's place, and %d is carried down into t2, now \ on the left." v w w) (fill' (here t2)) w (here t2)); go fill' w t2 in go Fun.id v t; s (* The array 1, 2, ..., n, each element at its own subscript. At depth d (the root is at 0) subscripts go up by 2^d from one node to the next, so below subscript s, at depth d, come s + 2^d on the left and s + 2^(d+1) on the right. *) let numbered n = let rec go s step = if s > n then Lf else Br (s, go (s + step) (2 * step), go (s + 2 * step) (2 * step)) in go 1 1 let t = numbered 15 let () = Steps.show ~title:"tcons 0 t" ~code ~mode:"lecture" (tcons_steps 0 t)