= Solution
The first tree's root is the first element. Deleting that root either discards a singleton or exposes two equal-sized child trees:
``
head :: List a -> a
head (List ((_,Leaf x):_)) = x
head (List ((_,Node x _ _):_)) = x
head (List []) = error "head: empty list"
tail :: List a -> List a
tail (List ((_,Leaf _):ts)) = List ts
tail (List ((w,Node _ l r):ts)) =
let h = w `div` 2 in List ((h,l):(h,r):ts)
tail (List []) = error "tail: empty list"
``
For a node of size $w=2h+1$, both children have size $h$. Their order agrees with the old <preorder traversal>, and they become the sole permitted initial duplicate. The rest of the <forest> was no smaller than the old root tree. Thus both operations preserve the representation invariant and take \b[worst-case $O(1)$ time] on a nonempty <skew-binary random-access list>.
Back to article page
