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)