Potential space leak in transpose

[David Feuer]

Right. I still think it might be the right thing to do, though. I'm not a
big fan of general-purpose library functions that have any unnecessary
memory leak hazard. The biggest counterargument is that real code is
unlikely to run into that problem.

On Thu, May 14, 2020, 3:35 PM Ryan Reich <ryan.reich at gmail.com> wrote:

> 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/c3330b5c/attachment.html>