Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 2 / h

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, \dots, 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

⌈ lo g_{2} (n + 1)⌉

forest entries by the supplied bound, and each tree has logarithmic height. Consequently a valid query takes $O (lo g (n + 1))$ time, with logarithmic worst cases. On a conventional linked list, xs !! i follows