[Haskell-cafe] Haskell performance (again)!

Udo Stenzel u.stenzel at web.de
Sun Oct 8 19:38:56 EDT 2006

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.

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

Hast du zum Leben kein Motiv --
steig mal vor, vielleicht geht's schief.
	-- aus einem Gipfelbuch
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061009/6b9deec6/attachment.bin

More information about the Haskell-Cafe mailing list