[Haskell-cafe] eager/strict eval katas

[Thomas Hartman]

>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 

http://thomashartman-learning.googlecode.com/svn/trunk/haskell/lazy-n-strict/average.hs

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
haskell-cafe at haskell.org
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071212/893fbe0e/attachment.htm