[Haskell-cafe] Hamming's Problem
Bertram Felgenhauer
bertram.felgenhauer at googlemail.com
Fri Jan 18 07:35:44 EST 2008
Jose Luis Reyes F. wrote:
> Hi,
>
> In exercise 2 of http://www.walenz.org/Dijkstra/page0145.html we need to
> write a function that holds
>
> (1) The value 1 is in the sequence
> (2) If x and y are in the sequence, so is f(x,y), where f has the
> properties
> a. f(x,y) > x
> b. (y1 > y2) => (f(x,y1)>f(x,y2))
>
> This is a solution for this problem, but an inefficient one
>
> hammingff :: [Integer]
> hammingff = 1 : merge [ h x y | x <- hammingff, y <- hammingff ]
> [ h x y | y <- hammingff, x <- hammingff ]
That's not sufficient. In fact, because hammingff is an infinite sequence,
this is equivalent to
hammingff = 1 : merge [ h (head hammingff) y | y <- hammingff ]
[ h x (head hammingff) | x <- hammingff ]
> h x y = 2*x+3*y
[snip merge function]
Indeed, the first few terms of hammingff are [1,5,13,17,29], and the
value h 5 5 = 25 is missing.
> anybody has a better solution?.
I have some ideas, but maybe you want to work on a correct solution
first?
Btw, with your choice of h, the result list will contain all natural
numbers that are not divisible by 3 and are = 1 (mod 4). Evaluating the
first n elements of that list will require O(n^2) evaluations of h.
Bertram
More information about the Haskell-Cafe
mailing list