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
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe