Five ways to write listofarray

For after Tick 3. listofarray is the inverse of arrayoflist: it lists a functional array's elements in subscript order. There are three reasonable ways to write it, and a variant of the third. They all take O(n log n) time, but they differ in the space they need. A fifth way, at the end, takes O(n).

The cell under each solution loads it rewritten to count, and runs it on arrays of 256 to 4096 elements, built outside the count. It counts three things, and fits how each grows as the array doubles:

Change a solution, run it, and run the cell under it again to see what changes.

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree let rec tcons v = function | Lf -> Br (v, Lf, Lf) | Br (w, t1, t2) -> Br (v, tcons w t2, t1) let arrayoflist l = List.fold_right tcons l Lf let analyse ~as_ id = let l = Focs_check.load_counting ~as_ id in if not l.ok then Focs_check.print_diagnostics l else Focs_check.print_profile (Focs_check.profile ~as_ ~input:"fun n -> arrayoflist (List.init n Fun.id)" ~call:(as_ ^ ".listofarray") [ 256; 512; 1024; 2048; 4096 ]) let check f = let l = List.init 20 Fun.id in if f (arrayoflist l) <> l then failwith "listofarray gives a wrong answer"

1. Merge the subtrees' lists

The root is subscript 1; the left subtree holds the even subscripts and the right the odd ones, so the two subtrees' lists interleave.

let rec merge l1 l2 = match l1, l2 with | x :: xs, y :: ys -> x :: y :: merge xs ys | [], ys -> ys | xs, [] -> xs let rec listofarray = function | Lf -> [] | Br (x, l, r) -> x :: merge (listofarray l) (listofarray r) let () = analyse ~as_:"Merging" "merging" ;; let () = check Merging.listofarray

Each level of the tree merges lists that between them hold all of that level's elements and those below it: every element is copied once for each level above it, log n times, so time and allocation are both O(n log n). The stack is O(n): merge's call is under ::, not a tail call, and it takes a frame for every two elements of the longest merge.

2. Take the first element off, again and again

untcons undoes tcons: it removes the element at subscript 1 and moves every other element one subscript down.

let rec untcons = function | Lf -> invalid_arg "untcons" | Br (_, Lf, _) -> Lf | Br (_, (Br (w, _, _) as t2), t1) -> Br (w, t1, untcons t2) let rec listofarray = function | Lf -> [] | Br (v, _, _) as t -> v :: listofarray (untcons t) let () = analyse ~as_:"Untcons" "untcons" ;; let () = check Untcons.listofarray

Each untcons builds a new path from the root down, log n new Br nodes, and the old tree becomes garbage: O(n log n) blocks for a result of n cells, about as many as merging. The stack is O(n), from v :: listofarray ....

3. Look up each subscript in turn

Look up subscripts 1, 2, 3, ... until one isn't there.

let rec lookup t k = match t with | Lf -> raise Not_found | Br (v, l, r) -> if k = 1 then v else if k mod 2 = 0 then lookup l (k / 2) else lookup r (k / 2) let listofarray t = let rec go k = match lookup t k with | v -> v :: go (k + 1) | exception Not_found -> [] in go 1 let () = analyse ~as_:"Lookup" "lookup" ;; let () = check Lookup.listofarray

Each lookup goes down log n levels, so the time is O(n log n) as before. But it builds nothing: the only blocks allocated are the result's n cells. The stack is still O(n), from v :: go (k + 1). lookup itself is tail recursive.

4. Look up each subscript, with an accumulator

let rec lookup t k = match t with | Lf -> raise Not_found | Br (v, l, r) -> if k = 1 then v else if k mod 2 = 0 then lookup l (k / 2) else lookup r (k / 2) let listofarray t = let rec go k acc = match lookup t k with | v -> go (k + 1) (v :: acc) | exception Not_found -> List.rev acc in go 1 [] let () = analyse ~as_:"Lookup_acc" "lookup-acc" ;; let () = check Lookup_acc.listofarray

The call go (k + 1) (v :: acc) is a tail call, so the stack stays the same size whatever the array: O(1). The price is List.rev at the end, which builds the list a second time: 2n blocks, still O(n).

5. Can you beat O(n log n)?

Yes: go level by level. Below the root, subscript s at depth d has s + 2d as its left child and s + 2d+1 as its right. So if one level holds subscripts 4 to 7, in order, their left children are 8 to 11 and their right children 12 to 15: the next level, in order, is all the left subtrees and then all the right ones. A subscript past the end is missing, and they are all at the end, so dropping the Lfs leaves no gaps.

let rec roots = function | [] -> [] | Lf :: ts -> roots ts | Br (v, _, _) :: ts -> v :: roots ts let rec lefts = function | [] -> [] | Lf :: ts -> lefts ts | Br (_, l, _) :: ts -> l :: lefts ts let rec rights = function | [] -> [] | Lf :: ts -> rights ts | Br (_, _, r) :: ts -> r :: rights ts let listofarray t = let rec go = function | [] -> [] | level -> roots level @ go (lefts level @ rights level) in go [ t ] let () = analyse ~as_:"Levels" "levels" ;; let () = check Levels.listofarray

Each node is looked at a fixed number of times: once by each of roots, lefts and rights, and once more by each @. So time and allocation are O(n). At these sizes the gain over O(n log n) is modest, as log n is at most 12; the ratios show it best, 2.00 where the others are about 2.2. The stack is O(n) again, from roots, lefts, rights and @ on the bottom level: try making them tail recursive.