 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/ia/paper-5/6/a/i/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 6 / a / i / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

These Standard ML declarations separate the three evaluation and mutation models:

sml
datatype 'a olist = ONil | OCons of 'a * 'a olist;

datatype 'a lnode = LNil | LCons of 'a * (unit -> 'a lnode);
type 'a llist = unit -> 'a lnode;

datatype 'a mnode = MNil | MCons of 'a * 'a mnode ref;
type 'a mlist = 'a mnode ref;

The ordinary linked list is immutable and its spine is built eagerly. A lazy list is a delayed function producing the next constructor, with another delayed function for its tail; it can describe an infinite stream without constructing it in advance. A mutable list uses an ML reference type cell for both the root link and every tail link. Updating those cells can remove nodes, including the original head. This lazy list representation delays evaluation but does not automatically implement memoization; repeated forcing can repeat work or effects.

 Read the full article

 New to topics? Read the docs here!