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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
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)
*/
(<) infix 4 :: !Int !Int -> Bool
(<) a b = code inline {
ltI
}
(-) infixl 6 :: !Int !Int -> Int
(-) a b = code inline {
subI
}
(*) infixl 7 :: !Int !Int -> Int
(*) a b = code inline {
mulI
}
(==) infix 4 :: !Int !Int -> Bool
(==) a b = code inline {
eqI
}
map :: (a -> b) [a] -> [b]
map f [] = []
map f [x:xs] = [f x:map f xs]
take :: Int [a] -> [a]
take 0 _ = []
take n [x:xs] = [x:take (n-1) xs]
//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.
|
