Adding swap to Data.Tuple

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Wed Jun 17 14:47:19 EDT 2009


roconnor at theorem.ca wrote:
> On Tue, 16 Jun 2009, Neil Mitchell wrote:
>
>> What is the need for swap' ? Things like foldl' solve space leaks,
>> what does swap' solve? I fully agree on the addition of swap.
>
> I'm not sure what swap' solves.  I just think it has a pretty symmetry to 
> it.  I presume one of these pro-strict-swap people can come up with an 
> example of where swap' solves a problem.

Sure.

    f (x, y) z = let !t = x+z in (t, y)
    
    bar1 xs = foldl' ((swap' .) . f) (0, 0) xs
    bar2 xs = foldl' ((swap  .) . f) (0, 0) xs

Prelude Swap> bar1 [0..1000000]
(250000000000,250000500000)
Prelude Swap> bar2 [0..1000000]
(*** Exception: stack overflow

Actually, "swap" works fairly well most of the time, because in addition
to its laziness, ghc's garbage collector does short-cut evaluation of
record selectors. So if the code just builds up a chain of swaps, GC
will compress that chain very nicely.

But I still prefer the strict version.

Bertram

P.S. I'd problably write your example as

    foo x []       = (x, 0)
    foo x [y]      = (0, x + y)
    foo x (y:z:xs) = let !t = x + y + z in foo t xs

or, if I wanted to do something fancy,

    foo x xs = r where
        (c, d, r) = go x xs (c, d)
        go x []     r = (x, 0, r)
        go x (y:ys) r = let !z = x + y; !r' = swap' r in go z ys r'

Compiled, both versions end up about 2 times faster than

    foo x []     = (x, 0)
    foo x (y:xs) = let !z = x + y in swap (foo z xs)

on foo 0 [0..1000000].


More information about the Libraries mailing list