listofarrayFor 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:
:: built;::, each
Br, each tuple or record. This is all that is ever
allocated, not what is alive at once: a block no longer used is
garbage, and is collected;Change a solution, run it, and run the cell under it again to see what changes.
The root is subscript 1; the left subtree holds the even subscripts and the right the odd ones, so the two subtrees' lists interleave.
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.
untcons undoes tcons: it removes the
element at subscript 1 and moves every other element one subscript
down.
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 ....
Look up subscripts 1, 2, 3, ... until one isn't there.
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.
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).
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.
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.