The sequence begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... . Note that 7, 11, 13, 14 arei j k 2 × 3 × 5, i,j,k>=0

The Hamming program (below) defines a list which begins with the first Hamming number `1':

If you take a Hamming number and multiply it by 2, 3 or 5 you get another Hamming number. A moment's thought reveals that all Hamming numbers, except 1, can be obtained in this way. The program therefore continues byhamm = 1 :: ...

The merge and multiply functions are quite conventional. The program below never terminates but continues to print Hamming numbers until it runs out of space or is killed. If somemerge (mult 2 hamm) (merge .... )

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) in let rec hamm = 1 :: (merge (mul 2 hamm) (merge (mul 3 hamm) (mul 5 hamm))) in hamm {\fB Hamming Numbers. \fP}

The merge and multiplication functions can be thought of as processes communicating by streams (lists) of values. The initial value `1' has to be injected to start the calculation. Many operating systems and other useful programs have similar structures where graphs of processes communicate through streams.

[Previous Page] [Next Page] [Index] © L. Allison, Dept. of Computer Science, Monash University