RE: [Haskell-cafe] Hamming's Problem

[Jose Luis Reyes F .]

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: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] 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


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Hamming's Problem

[Jose Luis Reyes F .]

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

 

 

 

 

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe