Dijkstra attributes to Hamming the problem of building the infinite ascending sequence of all positive numbers greater than 1 containing no prime factors other than 2, 3 and 5, i.e. numbers of the form 2^i x 3^j x 5^k (i,j,k >= 0). The ideas to compute them are the following:
- Given a hamming number h, then 2h, 3h, 5h are hamming numbers.
- 1 is a hamming number at it is used to start the computation.
- To maintain them sorted, it is only needed to compare the numbers coming from the multiplication for 2, 3, 5 not used yet. Other products will result greater than some of then, so they are not candidates to be the first in the sorted list.
It can be coded by simply following the description of the solution of the problem. We need lazy evaluation to compute the solution.
fun merge: list A * list A -> list A. merge [] l2 = l2. merge l1 [ ] = l1. merge x::l1 y::l2 = if x < y then x::(merge l1 y::l2) else if x > y then y::(merge x::l1 l2) else x::(merge l1 l2). fun merge3: list A * list A * list A -> list A. merge3 l1 l2 l3 = merge l1 (merge l2 l3). fun hamming: list int. hamming = 1::(merge3 (map hamming (2 *)) (map hamming (3 *)) (map hamming (5 *)). fun first: list A * int -> list A. first 0 l = [ ] . first succ (n) x::l = x::(first n l). fun nhamming: int -> list int. nhamming n = first n hamming.
See also the Prolog solution.
Go to index