[Haskell-cafe] Haskell performance (again)!

[Udo Stenzel]

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.


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