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

[Duncan Coutts]

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 
> 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