Re: Potential space leak in transpose

14 May 2020


      On 2020-05-13 22:27, Ryan Reich wrote:
...
Why not just inline the definition of unzip and hand-optimize away the 
pairs?
Isn't this what the original code of transpose is doing?
...
On Tue, May 12, 2020, 10:24 David Feuer mailto:david.feuer@gmail.com> wrote:
Also, the more eager list allocation can increase residency, but I
    don't think it can cause a leak.
On Tue, May 12, 2020, 9:48 AM David Feuer mailto:david.feuer@gmail.com> wrote:
The cost of allocating the extra pairs.
On Tue, May 12, 2020, 5:11 AM Andreas Abel
        mailto:andreas.abel@ifi.lmu.de> wrote:
 > I don't know how much that'll cost in practice.
What costs are you worried about?
On 2020-05-12 00:08, David Feuer wrote:
             > In Data.List, we define
             >
             > transpose :: [[a]] -> [[a]]
             > transpose [] = []
             > transpose ([] : xss) = transpose xss
             > transpose ((x : xs) : xss) = (x : [h | (h : _) <- xss]) :
            transpose (xs
             > : [t | (_ : t) <- xss])
             >
             > The potential difficulty is that we essentially mapMaybe
            over the xss
             > list twice in the third case. So we hang on to the heads
            where we need
             > the tails and the tails where we need the heads. We could
            fix that with
             > something like this:
             >
             > transpose ((x : xs) : xss) = (x : fronts) : transpose (xs
            : rears)
             >    where
             >      (fronts, rears) = unzip [(h,t) | (h : t) <- xss]
             >
             > I don't know how much that'll cost in practice.
             >
             > _______________________________________________
             > Libraries mailing list
             > Libraries@haskell.org mailto:Libraries@haskell.org
             > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
             >
_______________________________________________
    Libraries mailing list
    Libraries@haskell.org mailto:Libraries@haskell.org
    http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries