[Haskell-cafe] Hamming's Problem
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
> [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
More information about the Haskell-Cafe