Dan Weston westondan at imageworks.com
Wed Dec 12 15:46:07 EST 2007

```Thomas Hartman wrote:
>
>
>  >Note that 1 + ··· + n = n * (n+1) / 2, so the average of [1..n] is
> (n+1) / 2
>
> fair enough.
>
> But I believe  if I restate the problem  so that you need to find the
> average of an arbitrary list, your clever trick doesn't work and we need
> eager eval or we blow the stack.

Not true:

Prelude Data.List> let f a = (\(a,b,c)->c) . head . dropWhile (\(s,n,_)
-> s <=n*a) . scanl (\(s,n,_) x ->(s+x,n+1,x)) (0,0,0) in f (10^5) [1,3..]
200001

> Also... on second thought, I actually solved a slightly different
> problem than what I originally said:  the problem of detecting when the
> moving average of an increasing list is greater than 10^6; but my
> solution doesn't give the index of the list element that bumped the list
> over the average. However I suspect my code could be tweaked to do that
> (still playing around with it):
>
> Also I actually used a strict scan not a strict fold and... ach, oh well.

scanl above is not strict in its second argument. The data dependencies
cause the strictness. Cf:

1

> As you see I wrote a customized version of foldl' that is strict on the
> tuple for this to work. I don't think this is necessarily faster than
> what you did  (haven't quite grokked your use of unfold), but it does
> have the nice property of doing everything in one one fold step (or one
> scan step I guess, but isn't a scan
>

You have

Prelude Control.Arrow Data.List>
let avg5 = uncurry (/) . foldl' (\(s,n) x -> (s + x,n + 1)) (0,0)
in avg5 [1..10000000]
*** Exception: stack overflow
-- This fails in 100 sec

Try this. It is not foldl' that needs to be strict, but the function folded:

Prelude Data.List> let avg5 = uncurry (/) . foldl' (\(!s,!n) x -> (s +
x,n + 1)) (0,0) in avg5 [1..10000000]

You will need -fbang-patterns for this (there are other ways to do this

>
>
> t.
>
> t1 = average_greater_than (10^7) [1..]
>
> average_greater_than max xs = find (>max) \$ averages xs
>
> averages = map fst . myscanl' lAccumAvg (0,0)
> average = fst . myfoldl' lAccumAvg (0,0)
> lAccumAvg (!avg,!n) r = ( (avg*n/n1) + (r/n1),(n1))
>  where n1 = n+1
>
> myfoldl' f (!l,!r) [] = (l,r)
> myfoldl' f (!l,!r) (x:xs) = ( myfoldl' f q xs )
>  where q = (l,r) `f` x
>
> myscanl f z []  = z : []
> myscanl f z (x:xs) =  z : myscanl f (f z x) xs
>
> myscanl' f (!l,!r) []  = (l,r) : []
> myscanl' f (!l,!r) (x:xs) =  (l,r) : myscanl' f q xs
>  where q = (l,r) `f` x
>
>
>
>
> *"Felipe Lessa" <felipe.lessa at gmail.com>*
>
> 12/12/2007 02:24 PM
>
>
> To
> 	Thomas Hartman/ext/dbcom at DBAmericas
> cc
> Subject
> 	Re: [Haskell-cafe] eager/strict eval katas
>
>
>
>
>
>
>
>
> 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.
>
>
> ---
>
> This e-mail may contain confidential and/or privileged information. If you
> are not the intended recipient (or have received this e-mail in error)
> please notify the sender immediately and destroy this e-mail. Any
> unauthorized copying, disclosure or distribution of the material in this
> e-mail is strictly forbidden.
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________