Bertram Thanks for your help, I tried to solve the problem this weekend but I have some dudes. My reasoning is: The sequence is [1,a1,a2,a3,..] where a1 = h 1 1, a2 = h 1 a1, and so on So, I want to construct the list of lists [[1,a1,a2,a3], [h 1 1, h 1 a1, h 1 a2,..], [h a1 1, h a1 a1, h a1 a2,...] ... [h an 1, h an a2,h an a3,...] ... ] The function is hammingx = 1 : foldl1 merge [ map (h x) hammingx | x <- hammingx] However this is not a solution because the list is a infinite list of infinite lists. Please some advices to resolve this problem. Thanks Jose Luis -----Mensaje original----- De: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] En nombre de Bertram Felgenhauer Enviado el: viernes, 18 de enero de 2008 8:36 Para: haskell-cafe@haskell.org Asunto: Re: [Haskell-cafe] Hamming's Problem 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe __________ Informacisn de NOD32, revisisn 2805 (20080118) __________ Este mensaje ha sido analizado con NOD32 antivirus system http://www.nod32.com