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 #ad:

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

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