[Haskell-cafe] Hamming's Problem

[Bertram Felgenhauer]

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