## Lambda Calculus Remove Duplicates.

 LA home Computing FP  λ-calc.   Intro   Syntax   Examples    Ints    Bools    Lists(1)    arithmetic    Y (lazy)    Y (strict)    Lists(2)    Trees    Primes(1)    Fibonacci(1)    Unique    Hamming#s    Composites    Fibonacci(2)    Thue seqs.    Edit-dist.    Unique

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 }

```

Reference:
[All89] L. Allison, Circular programs and self referential structures. Software Practice and Experience, 19(2), pp.99-109, Feb 1989.

[All93] L. Allison, Applications of Recursively Defined Data Structures, Australian Computer Journal, 25(1), pp.14-20, arxiv:2206.12795, 1993.