= Solution
For a pure 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;
``
For a <lazy list>, return a delayed computation. Searching for the next retained element begins only when this computation is forced:
``
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 ();
``
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.
The destructive <mutable list> version operates on the link reaching the current node:
``
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);
``
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. \b[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.
Back to article page
