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 ] h x y = 2*x+3*y merge :: (Ord a) => [a] -> [a] -> [a] merge [] xs = xs merge ys [] = ys merge (x:xs) (y:ys) = case compare x y of LT -> x : merge xs (y:ys) GT -> y : merge (x:xs) ys EQ -> x : merge xs ys anybody has a better solution?. Thanks Jose
The author of Pugs (Perl6 implemented in Haskell) gives a nice solution to the problem of generating the Hamming numbers in the following interview: http://www.perl.com/pub/a/2005/09/08/autrijus-tang.html?page=last
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
On 18/01/2008, Bertram Felgenhauer
I have some ideas, but maybe you want to work on a correct solution first?
There is an implementation on the wikipedia article for Haskell: hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming where merge (x:xs) (y:ys) | x < y = x : xs `merge` (y:ys) | x > y = y : (x:xs) `merge` ys | otherwise = x : xs `merge` ys -- Dougal Stanton dougal@dougalstanton.net // http://www.dougalstanton.net
Calvin Smith
The author of Pugs (Perl6 implemented in Haskell) gives a nice solution to the problem of generating the Hamming numbers in the following interview: http://www.perl.com/pub/a/2005/09/08/autrijus-tang.html?page=last
Dougal Stanton
There is an implementation on the wikipedia article for Haskell:
Note that Dijkstra's two exercises are not the same as Hamming's original problem. I recommend the exercises! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig One thing that UNIX does not need is more features. It is successful in part because it has a small number of good ideas that work well together. Merely adding features does not make it easier for users to do things -- it just makes the manual thicker. -- Rob Pike, Brian W. Kernighan, 1983.
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
Jose Luis Reyes F. wrote:
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.
Oh, but it's pretty close working, actually. We only need two small modifications: 1) use the right fold. foldl on an infinite list *never* produces a result. 'merge' is associative, so we can just use foldr instead: hammingx = 1 : foldr1 merge [map (h x) hammingx | x <- hammingx ] 2) we still haven't exploited the property that h x 1 > x. This property ensures that of the two arguments that 'merge' is applied to by 'foldr', the first one starts with the smaller element. So we can write merge' (x:xs) ys = x : merge xs ys hammingx = 1 : foldr1 merge' [map (h x) hammingx | x <- hammingx] which actually works. I'd actually define 'hamming' as a higher order function: hamming :: Ord a => (a -> a -> a) -> a -> [a] hamming f a = result where result = a : foldr1 merge' [map (f x) result | x <- result] hammingx = hamming h 1 HTH, Bertram
I wrote:
merge' (x:xs) ys = x : merge xs ys
hammingx = 1 : foldr1 merge' [map (h x) hammingx | x <- hammingx]
Sorry. 'foldr1' is still slightly too strict. (Why doesn't the Haskell report define foldr1 in terms of foldr?) The code that works is marge' [] ys = ys merge' (x:xs) ys = x : merge xs ys hammingx = 1 : foldr merge' [] [map (h x) hammingx | x <- hammingx] I had tested that version, but I assumed the foldr1 version would be equivalent.
which actually works.
And I wrote that without testing. Shame on me. Bertram
participants (5)
-
Bertram Felgenhauer -
Calvin Smith -
Chung-chieh Shan -
Dougal Stanton -
Jose Luis Reyes F.