Lambda Calculus Hamming Numbers

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.
   Hamming
Calculate the Hamming numbers by the well-known recursive method (also see the [PFL] version).

let rec
 merge = lambda a. lambda b.
   if hd a < hd b then (hd a)::(merge tl a b)
   else if hd b < hd a then (hd b)::(merge a tl b)
   else (hd a)::(merge tl a tl b),

 mul = lambda n. lambda l. (n* hd l)::(mul n tl l),

 first = lambda n. lambda l.
   if n <= 0 then nil else hd l :: first (n-1) tl l

in let rec
 hamm = 1 :: (merge (mul 2 hamm)
             (merge (mul 3 hamm)
                    (mul 5 hamm)))

in first 10 hamm

{\fB Hamming Numbers. \fP}

Note that 'hamm' is an infinite, self-referential list.



www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Thursday, 19-Apr-2018 05:53:32 EDT.

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