(moved to haskell-café) I ran Hal's code on my computer, and with test2 I get a stack overflow (so I had to use +RTS option for it to finish). test1 does not overflow stack (of standard size, I mean without +RTS). Which implies that test2 uses more stack space than test1. why would it use more stack if not because of laziness? konst
-----Original Message----- From: Hal Daume III [mailto:hdaume@ISI.EDU] Sent: Friday, February 08, 2002 4:35 PM To: Jorge Adriano Cc: Konst Sushenko; haskell@haskell.org Subject: Re: efficiency question
I agree that it's the overhead of (,), but I don't see why there would be any overhead for doing this.
-- Hal Daume III
"Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
On Sat, 9 Feb 2002, Jorge Adriano wrote:
On Friday 08 February 2002 23:52, Hal Daume III wrote:
I've tried using a strict fold:
foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs
but that has no effect (or minimal effect).
That wouldn't work even if if laziness is the problem because that would only cause the elements of the list to be evaluated to head normal form, the elements of the pair would not be evaluated so you'd have a 'suspension of (minus and plus) operations'.
(\x (a,b) -> (x+a,x-b))
instead of try
(\x (a,b) -> (((,) $! x-a)$! x-b) )
I just noticed that you were the one who sent me the DeepSeq module. This is the kind of place where I want to use it. Instead of $!, try $!!.
And Konst Sushenko wrote:
My guess is that it is due to the laziness of the addition/subtraction in (,)
Seems to me like lazyness is not the right guess because both functions Hall first posted were lazy. So I think it's just the overhead of applying (,) besides (+) and (-) in each step. Do I make sense or am I missing something?
J.A.
(moved to haskell-café) Good idea :-)
I ran Hal's code on my computer, and with test2 I get a stack overflow (so I had to use +RTS option for it to finish). test1 does not overflow stack (of standard size, I mean without +RTS). Which implies that test2 uses more stack space than test1. why would it use more stack if not because of laziness?
I see what you mean. Both are equally lazy but in the first case,
test1 l = let s1 = foldr (+) 1 l s2 = foldr (-) 1 l in (s1, s2)
creates a suspension of sums of ints when calculating s1, then a suspension of diferences of ints to calculate s2. The second one,
test2 l = let s = foldr (\x (a,b) -> (x+a,x-b)) (1,1) l in s
Creates a suspension of (x0...(xn-1%(xn%(1,1)))...), where (%) is that 'sumdiffs' lambda expression. You are telling me this suspension is worst than the first ones... can somebody explain why? I'm not really beeing able to find a valid argument... If you make it strict on the (,), like:
test3 l = let s = foldr (\x (a,b) -> ((,)$!x+a)$!x-b) (1,1) l in s
Things will get worst. Well, that's what I expected, the elements of the list will b reduced to head normal form, and instead of a suspension of (%), you'll have a suspension of sums in the fst element of the pair *and* a suspension of differences in the second element of the pair. OK, now lets forget about lazyness. I tried:
test1' l = let s1 = sfoldl (+) 1 l s2 = sfoldl (-) 1 l in (s1, s2)
test2' l = let s = sfoldl (\(a,b) x -> (x+a,x-b)) (1,1) l in s
Where sfold reduces both Ints and (Ints, Ints) to *normal form* The first one was still faster then the second one. So, I'd say you are right about lazyness also playing a role in the lack of efficience of Halls second function, but 1. you can't solve that problem by making the lambda function strict on (,) 2. strictness does not explains everything in that example, because if you use foldls and make them strict, no suspensions, the first version is still better. Don't take my word for it though. I'd *really* appreciate some comments from some haskell gurus on this problem and on my comments :-) J.A. J.A.
On Saturday 09 February 2002 11:38, Jorge Adriano wrote:
If you make it strict on the (,), like:
test3 l = let s = foldr (\x (a,b) -> ((,)$!x+a)$!x-b) (1,1) l in s
Things will get worst. Well, that's what I expected, the elements of the list will b reduced to head normal form, and instead of a suspension of (%), you'll have a suspension of sums in the fst element of the pair *and* a suspension of differences in the second element of the pair.
Eh... no need to comment on this one... this was kind of dumb. Forget it... :-) J.A.
participants (2)
-
Jorge Adriano -
Konst Sushenko