[Haskell-cafe] eager/strict eval katas

[Felipe Lessa]

On Dec 12, 2007 2:31 PM, Thomas Hartman <thomas.hartman at db.com> wrote:
> exercise 2) find the first integer such that average of [1..n] is > [10^6]
>   (solution involves building an accum list of (average,listLength) tuples.
> again you can't do a naive fold due to stack overflow, but in this case even
> strict foldl' from data.list isn't "strict enough", I had to define my own
> custom fold to be strict on the tuples.)

What is wrong with

Prelude> snd . head $ dropWhile ((< 10^6) . fst) [((n+1) / 2, n) | n <- [1..]]
1999999.0

Note that 1 + ··· + n = n * (n+1) / 2, so the average of [1..n] is
(n+1) / 2. The naive

Prelude Data.List> let avg xs = foldl' (+) 0 xs / (fromIntegral $ length xs)
Prelude Data.List> snd . head $ dropWhile ((< 10^6) . fst) [(avg
[1..n], n) | n <- [1..]]

works for me as well, only terribly slower (of course). Note that I
used foldl' for sum assuming the exercise 1 was already done =). How
did you solve this problem with a fold? I see you can use unfoldr:

Prelude Data.List> last $ unfoldr (\(x,s,k) -> if s >= k then Nothing
else Just (x, (x+1,s+x,k+10^6)))  (2,1,10^6)

I'm thinking about a way of folding [1..], but this can't be a left
fold (or else it would never stop), nor can it be a right fold (or
else we wouldn't get the sums already done). What am I missing?

Cheers,

-- 
Felipe.