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