|
|
The `unique' (nub) function removes duplicate elements
from a list while preserving the order of
first occurrence.
It operates correctly on even infinite (lazy) lists.
Note that `r' is a list and `u' is a function
and that they have mutually recursive definitions -
r depends on u and v.v..
Bird called programs with self-referential data-structures
circular programs.
unique = lambda L. {remove duplicates from L (may be infinite)}
let rec
r = u L 0, { result }
u = lambda L. lambda n. { returns L-r }
if null L then nil
else if member hd L r n then u tl L n { duplicate }
else hd L :: (u tl L (n+1)), { new value }
member = lambda e. lambda L. lambda n. { is e in L ? }
if n = 0 then false { n is current length of r }
else if e = hd L then true
else member e tl L (n-1)
in r
{\fB Circular Program Unique \fP}
|
- Reference:
- L. Allison,
Circular programs and self referential structures.
Software Practice and Experience 19(2) pp99-109, Feb 1989.
|
λ ...
| :: | list cons |
| nil | the [ ] list |
| null | predicate |
| hd | head (1st) |
| tl | tail (rest) |
|
|
|