Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 4 / a / Solution

A function returning an optional value supplies the representation:For a finite represented list, require a length $m\ge 0$ such that every index $0\le 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.