= Solution
Skip whole trees using their cached sizes, then descend through one tree:
``
index :: List a -> Int -> a
index (List ts) i
| i < 0 = error "index: negative index"
| otherwise = seek ts i
where
seek [] _ = error "index: out of bounds"
seek ((w,t):us) j
| j < w = at w t j
| otherwise = seek us (j-w)
at _ (Leaf x) 0 = x
at w (Node x l r) j
| j == 0 = x
| j <= h = at h l (j-1)
| otherwise = at h r (j-1-h)
where h = w `div` 2
at _ _ _ = error "index: invalid representation"
``
After skipping a size-$w$ tree, the desired index decreases by $w$. Inside a node, position zero is the root, positions $1,\ldots,h$ belong to the left child and the following $h$ positions to the right child. This proves correctness by <structural induction> on the search.
There are at most $\lceil\log_2(n+1)\rceil$ <forest> entries by the supplied bound, and each tree has logarithmic height. Consequently a valid query takes \b[$O(\log(n+1))$ time], with logarithmic worst cases. On a conventional <linked list>, `xs !! i` follows $i$ links and costs $\Theta(i+1)$, hence $\Theta(n)$ in the worst case. The first element remains a <constant time> query in either representation.
Back to article page
