= Solution
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.
Back to article page
