[MLton-user] Questions on MLton

[Stephen Weeks]

> Ah, well. Let us suppose we have something like
> 
>     datatype 'a mlist = Mnil | Mpair of ('a * 'a mlist ref)
> 
> SML/NJ will arrange things so that the Mpair constructor does no allocation --
> an Mpair value is just represented as the pair, and an Mnil value is
> represented as a constant with a non-address low type tag. Will Mlton do this
> much?

Yes.  I think SML/NJ and MLton will represent these exactly the same,
except that MLton will specialize the mlist based on the element type.

Of course, you could always use MLton's allocation profiler to see how
many bytes are being allocated.  :-)

> My destructive-list sorting algo will take a list and sort it. While
> running, 
>   - it will require a stack of O(lg n) depth.
>   - it will run in O(n lg n) worst-case and O(n) best-case time.
>   - it will allocate nothing -- zero cons cells.
> The list becomes sorted simply by wandering around it and redirecting
> the links. These SET-CDR!'s are the only side effects performed.

Ah.  Then the ref cells shouldn't hurt as much since you're not
allocating them during the sort.