[Haskell-cafe] Re: sort and lazyness (?)
duncan.coutts at worc.ox.ac.uk
Fri Dec 19 10:26:19 EST 2008
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.
> > 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
It will not make any difference to the space used by Fraction unless you
also unpack them as I mentioned in my other post.
More information about the Haskell-Cafe