Potential space leak in transpose

[Ryan Reich]

Hopefully I'm not fooling myself...how about this?

---
transpose :: [[a]] -> [[a]]
transpose [] = []
transpose (r1 : rrest) = zipWith' (:) (:[]) id r1 (transpose rrest)

zipWith' :: (a -> b -> c) -> (a -> c) -> (b -> c) -> ([a] -> [b] -> [c])
zipWith' _ _ fb [] bs = fb <$> bs
zipWith' _ fa _ as [] = fa <$> as
zipWith' f fa fb (a : as) (b : bs) = f a b : zipWith' f fa fb as bs

main = do
  mapM_ (print . transpose)
    [
      [[1,2,3]],
      [[1,2,3],[4,5,6]],
      [[1,2,3],[4,5,6],[7,8,9]],
      [[10,11],[20],[],[30,31,32]]
    ]
---

I see the output:
---
[[1],[2],[3]]
[[1,4],[2,5],[3,6]]
[[1,4,7],[2,5,8],[3,6,9]]
[[10,20,30],[11,31],[32]]
---

which is correct (the last example is the one from the haddocks).

I was concerned that the definition of zipWith' (which is akin to the Map
function unionWith) is not compatible with the build/fold fusion rule, but
the implementation of zipWith itself is basically the same.

Ryan

On Thu, May 14, 2020 at 1:17 PM David Feuer <david.feuer at gmail.com> wrote:

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