Re: Potential space leak in transpose

14 May 2020

      My suggestion was much less sophisticated even than that, and is basically
what David answered with fusion. Also according to his answer, the original
code of transpose lacks the laziness that unzip's actual implementation
would provide.

I think what that means is that his concern over allocating extra pairs is
about the ones created internally by unzip when it builds the lazy
heads-and-tails accessors.

On Thu, May 14, 2020, 03:27 Andreas Abel  wrote:
...
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