= Solution
A <function> returning an <optional value> supplies the representation:
``
newtype List a = List (Int -> Maybe a)
``
For a finite represented <list>, require a length $m\geq0$ such that every index $0\leq i<m$ returns `Just` its element and every other index returns `Nothing`. Thus there are no holes: absence at a nonnegative index implies absence at every later index. The type alone does not enforce this <invariant>, or <algorithm termination> of a query. An infinite represented <sequence> may instead have a present value at every nonnegative index; operations requiring its length will not terminate.
The implementations below return `Nothing` at negative indices. Finite lengths, requested counts and intermediate indices are assumed to fit `Int`; explicit guards on index shifts also prevent arithmetic wraparound from exposing an invalid element.
Back to article page
