[Haskell-cafe] eager/strict eval katas

[Thomas Hartman]

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 <westondan at imageworks.com>:
> 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" <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.
> >>
> >>
> >> ------------------------------------------------------------------------
> >>
> >> _______________________________________________
> >> Haskell-Cafe mailing list
> >> Haskell-Cafe at haskell.org
> >> http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>