## Lambda Calculus Remove Duplicates.

 home1 home2  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  Book

FP
Lambda
Introduction
Examples

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.
 let 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} in unique (1::2::1::3::2::4::nil)
 Coding Ockham's Razor, L. Allison, Springer A Practical Introduction to Denotational Semantics, L. Allison, CUP

 Linux  Ubuntu free op. sys. OpenOffice free office suite The GIMP ~ free photoshop Firefox web browser

λ ...
 :: list cons nil the [ ] list null predicate hd head (1st) tl tail (rest)

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 02-Feb-2023 05:58:06 AEDT.