[Haskell-cafe] Re: sort and lazyness (?)

[Luke Palmer]

On Fri, Dec 19, 2008 at 8:26 AM, Duncan Coutts
<duncan.coutts at worc.ox.ac.uk>wrote:

> On Fri, 2008-12-19 at 15:58 +0100, Daniel Kraft wrote:
>
> > How does reverse work in constant space?  At the moment I can't imagine
> > it doing so; that's why I tried it, but of course you could be right.
>
> It allocates a new list cell for every cell it finds in the input list.
> If the input list can be garbage collected then reverse takes constant
> space because each time it inspects a list cell from the input list that
> cell can be garbage collected. If the input list is being retained for
> some other reason then reverse will take linear space.


I don't think that's true.  It must inspect the whole input list to give the
first element of the output list, but it cannot garbage collect the input
list because it needs to yield every element of it.

When I tested:

ghci>  length $ reverse [1..10^7]

It certainly did not run in constant space.

I think that if the first half of the output list is unused, then the second
half of the input list will be collected (I'm having trouble visualizing the
dynamics of this case though).  But for the very first cons of the output,
the whole input list (spine) needs to be in memory.

Luke


>
>
> > > You might get some mileage by suggesting to GHC that your Fraction type
> > > is strict e.g.
> > >
> > >> data Fraction = Fraction !Int !Int
> > >
> > > which might persuade it to unbox the Ints, giving some space savings.
> >
> > I already tried so, but this doesn't change anything to the performance.
> >   I will however try now to use the provided rational type, maybe this
> > helps.
>
> It will not make any difference to the space used by Fraction unless you
> also unpack them as I mentioned in my other post.
>
> Duncan
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081219/cfa80f62/attachment.htm