[Haskell-cafe] Honest constant-space mergesort

[Li-yao Xia]

On 1/12/19 6:25 AM, Ryan Reich wrote:
> I considered using something like 
> STRef to represent the links (so, departing from the plain [a] type) but 
> even then, if you overwrite the contents of one of those, the garbage 
> collector still needs to know.  This is better than allocating more 
> space, but it is not necessary because the algorithm never actually 
> makes any of the nodes unreachable.


I thought this did not apply to a copying GC, does it?

What is actually in an STRef? If it's small enough then unpacking the 
tail reference like this may be a good idea:

     data List s a = Nil | Cons a {-# UNPACK #-} !(STRef s (List s a))

Li-yao