Potential space leak in transpose

[Ryan Reich]

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