Potential space leak in transpose

[David Feuer]

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