# [Haskell-cafe] Hamming's Problem

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Mon Jan 21 10:17:52 EST 2008

```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
```

More information about the Haskell-Cafe mailing list