>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.
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.
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
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@gmail.com>
12/12/2007 02:24 PM
To
Thomas Hartman/ext/dbcom@DBAmericas
cc
haskell-cafe@haskell.org
Subject
Re: [Haskell-cafe] eager/strict eval
katas
On Dec 12, 2007 2:31 PM, Thomas Hartman <thomas.hartman@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
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.