Potential space leak in transpose

[Ryan Reich]

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 <andreas.abel at ifi.lmu.de> 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 <david.feuer at gmail.com
> > <mailto:david.feuer at 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 <david.feuer at gmail.com
> >     <mailto:david.feuer at gmail.com>> wrote:
> >
> >         The cost of allocating the extra pairs.
> >
> >         On Tue, May 12, 2020, 5:11 AM Andreas Abel
> >         <andreas.abel at ifi.lmu.de <mailto:andreas.abel at 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 at haskell.org <mailto:Libraries at haskell.org>
> >              >
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >              >
> >
> >     _______________________________________________
> >     Libraries mailing list
> >     Libraries at haskell.org <mailto:Libraries at haskell.org>
> >     http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
> >
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20200514/524e3299/attachment.html>