Functional Programming is more Expressive than Logic Programming


Problem: The Hamming Numbers

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:

Functional Solution

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