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
{ Circular Program Unique }