[Haskell-cafe] Haskell performance (again)!

[Yang]

On 10/8/06, Udo Stenzel u.stenzel-at-web.de |haskell-cafe|
<...> wrote:
> Yang wrote:
> > type Poly = [(Int,Int)]
> >
> > addPoly1 :: Poly -> Poly -> Poly
> > addPoly1 p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t)
> >    | p1d == p2d = (p1c + p2c, p1d) : addPoly1 p1t p2t
> >    | p1d < p2d = p1h : addPoly1 p1t p2
> >    | p1d > p2d = p2h : addPoly1 p1 p2t
> > addPoly1 p1 [] = p1
> > addPoly1 [] p2 = p2
> > addPoly1 [] [] = []
> >
> > But this doesn't use tail recursion/accumulation
>
> Indeed it doesn't.  Now remind me, why is that supposed to be a Bad
> Thing?  The above code exhibits a maximum of lazyness and runs with no
> useless space overhead.  Apart from the expression (p1c + p2c), which
> you probably want to evaluate eagerly, it is close to perfect.
>
> > so I rewrote it: [...]
> >
> > But laziness will cause this to occupy Theta(n)-space of cons-ing
> > thunks.
>
> No, it doesn't.  Insisting on accumulator recursion does.  Actually,
> using reverse does.  Think about it, a strict reverse cannot use less
> than O(n) space, either.

Well, in general, the problem you run into is this, where we use
linear space for the thunks:

foldl (+) 0 [1,2,3]
= foldl (+) (0 + 1) [2,3]
= foldl (+) ((0 + 1) + 2) [3]
= foldl (+) (((0 + 1) + 2) + 3) []
= ((0 + 1) + 2) + 3
= (1 + 2) + 3
= 3 + 3
= 6

whereas with strictness, you use constant space:

foldl' f z [] = z
foldl' f z (x:xs) = let u = f z x in u `seq` foldl' f u xs
foldl' (+) 0 [1,2,3]
= let u = 0 + 1 in u `seq` foldl' (+) u [2,3]
= foldl' (+) 1 [2,3]
= let u = 1 + 2 in u `seq` foldl' (+) u [3]
= foldl' (+) 3 [3]
= let u = 3 + 3 in u `seq` foldl' (+) u []
= foldl' (+) 6 []
= 6

>
> > I was
> > hoping for more in-depth insights on how to take advantage of laziness
> > to write cleaner AND more efficient code.
>
> Try to explain why your first iteration was bad.  You'll achieve
> enlightenment at the point where your explanation fails.
>
>
> Udo.
> --
> Hast du zum Leben kein Motiv --
> steig mal vor, vielleicht geht's schief.
>         -- aus einem Gipfelbuch
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
>
> iD8DBQFFKYwQc1ZCC9bsOpURAs4KAKCymnLiE5LfkCa01H0AJ2FddwJ6oQCfY6DY
> sYRPT1fGr0mUozUcs+qGC8s=
> =BRLQ
> -----END PGP SIGNATURE-----
>
>
>