great advice. I played with this a bit, desugared to haskell 98, and got -- okay for 1..10^6, not ok (stack overflows) if either the fold or g is left lazy. -- Thanks, Dan Weston. avg6 = uncurry (/) . foldl' g (0,0) where g (!sum,!count) next = ( (sum+next),(count+1))
-- same thing, in haskell98 (works without LANGUAGE BangPatterns) -- thanks #haskell.oerjan avg7 = uncurry (/) . foldl' g (0,0) where g (sum,count) next = sum `seq` count `seq` ( (sum+next),(count+1)) t = avg7 testlist testlist = [1..10^6] 2007/12/12, Dan Weston <[EMAIL PROTECTED]>: > Dan Weston wrote: > > 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 > > The first claim is of course false, nore would the example show it anyway. > > scanl is not strict in its third argument (I forgot about the initial > value as the second argument): > > Prelude Data.List> let z = [1,4,undefined,8,9] in scanl (\x y -> 5) 8 z > [8,5,5,5,5,5] > > It is the data dependence in the first argument of scanl that would make > the above strict: > > Prelude Data.List> let z = [1,4,undefined,8,9] in scanl (+) 8 z > [8,9,13,*** Exception: Prelude.undefined > > > Also note that it is better not to introduce the / operator in your > test, as it fails with large numbers. Multiply both sides by the > denominator before the comparison and leave everything as Num a instead > of Floating a. You can do the division at the end. > > > 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 > >> [email protected] > >> 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 > >> [email protected] > >> http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
