Potential space leak in transpose

[David Feuer]

unzip should fuse with its argument, so inlining presumably won't do
anything there. The pairs that unzip itself creates are actually what
prevent the leak. GHC creates "selector thunks" to deconstruct them, which
the garbage collector can reduce. The garbage collector will never reduce
the deconstruction of list conses.

On Wed, May 13, 2020, 4:27 PM Ryan Reich <ryan.reich at gmail.com> wrote:

> Why not just inline the definition of unzip and hand-optimize away the
> pairs?
>
> On Tue, May 12, 2020, 10:24 David Feuer <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> wrote:
>>
>>> The cost of allocating the extra pairs.
>>>
>>> On Tue, May 12, 2020, 5:11 AM Andreas Abel <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
>>>> > 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/20200513/9b2d0356/attachment.html>