Potential space leak in transpose

[David Feuer]

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
>> >
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20200512/bd5e4e84/attachment.html>