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);Represent a binary search tree by:Assume the provided For equality-type values, call
sml
datatype ('k, 'v) dict = Empty
| Branch of ('k, 'v) dict * 'k * 'v * ('k, 'v) dict;lookup d key returns NONE or SOME value, and update d (key, value) returns the updated binary search tree. Traverse the first dictionary, retaining only a key with the same value in the second:sml
fun intersection equal d1 d2 =
let
fun visit Empty result = result
| visit (Branch (left, key, value, right)) result =
let
val r1 = visit left result
val r2 =
case lookup d2 key of
NONE => r1
| SOME other =>
if equal (value, other)
then update r1 (key, value)
else r1
in
visit right r2
end
in
visit d1 Empty
end;intersection (op =) d1 d2. An explicit value comparison parameter also handles values for which Standard ML does not define built-in equality. This distinguishes absent keys from defined values without reserving a sentinel value.Every inserted entry belongs to both input dictionaries with the same value, so the result agrees with each. Conversely, each common equal-valued entry is visited in
d1, found in d2, and inserted. Any dictionary agreeing with both can contain only those entries. Thus the result is exactly the largest common dictionary, not merely an intersection of key sets. If d1 has entries, lookup height is , and maximum result-tree height during insertion is , the time complexity is for constant-cost comparisons. Logarithmic heights require a balancing assumption; an ordinary unbalanced binary search tree can have linear height. Articles by others on the same topic
There are currently no matching articles.