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.




www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 19-Mar-2024 06:18:31 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.