# efficiency question

Sat, 9 Feb 2002 11:38:13 +0000

```> (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.

```