1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
module hamming
/*
The Hamming Function.
The result of this program is a list of the first NrElements numbers
having only 2, 3 and 5 as prime factors. Result:
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,...].
Run the program with the Show Constructors option on (Application options)
*/
import StdEnv
/* Ham (the Hamming function) returns an infinite list of numbers
having two, three and five as only prime factors by recursively
mapping the functions ((*) 2), ((*) 3) and ((*) 5) over the list of
Hamming numbers found sofar and merging these lists into one.
The definition of y specifies a cyclic graph to be used yielding a
polynomial complexity in stead of an exponential one.
The argument lists of merge never end with a Nil
and they are not Nil initially, so
the definition of merge can be specified for 'infinite' lazy lists
leaving out special cases for empty lists.
*/
Ham::[Int]
Ham = y
where
y = [1:merge (merge (map ((*) 2) y) (map ((*) 3) y)) (map ((*) 5) y)]
merge f=:[a:b] g=:[c:d]
| a<c = [a: merge b g]
| a==c = merge f d
| otherwise = [c: merge f d]
Start::[Int]
Start = take NrElements Ham
NrElements :== 300 // The number of Hamming numbers to be calculated.
|
