These Standard ML declarations separate the three evaluation and mutation models: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.
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;For a pure predicate For a lazy list, return a delayed computation. Searching for the next retained element begins only when this computation is forced:A retained element has a delayed filtered tail, so the whole input is not forced at once. A long run of rejected elements must still be traversed to find the next match. If an infinite lazy list has no matching element beyond the current position, forcing the next result does not terminate; laziness does not promise productivity for every predicate.
p, the ordinary linked list version copies only the surviving spine:sml
fun filterO p ONil = ONil
| filterO p (OCons (x, xs)) =
if p x then OCons (x, filterO p xs)
else filterO p xs;sml
fun filterL p stream () =
case stream () of
LNil => LNil
| LCons (x, rest) =>
if p x then LCons (x, filterL p rest)
else filterL p rest ();The destructive mutable list version operates on the link reaching the current node:When a node survives, recurse on its tail link. When it fails, bypass it by copying its successor into the same link and inspect that link again, which correctly handles several consecutive rejected nodes. No new list nodes are allocated. In particular, changing the root ML reference type cell handles deletion of the head. These arguments assume finite acyclic input for the eager and destructive versions and a predicate that does not itself mutate the list. Aliases observe the mutations; a detached node is not promised to disappear from all external references.
sml
fun filterM p link =
case !link of
MNil => ()
| MCons (x, tail) =>
if p x then filterM p tail
else (link := !tail; filterM p link); Articles by others on the same topic
There are currently no matching articles.