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:
Prelude> head ([1,3] ++ head ((scanl undefined undefined) undefined))
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
http://thomashartman-learning.googlecode.com/svn/trunk/haskell/lazy-n-strict/average.hs
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
in Haskell 98 though).
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" <[EMAIL PROTECTED]>*
12/12/2007 02:24 PM
To
Thomas Hartman/ext/[EMAIL PROTECTED]
cc
haskell-cafe@haskell.org
Subject
Re: [Haskell-cafe] eager/strict eval katas
On Dec 12, 2007 2:31 PM, Thomas Hartman <[EMAIL PROTECTED]> 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.
------------------------------------------------------------------------
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
