MLton and polymorphic recursion through datatypes?
Mon, 16 Apr 2001 17:18:12 -0700 (PDT)
> I don't have a recent version of MLton running, but wanted to check
> with you or one of the other MLton creators as to whether polymorphic
> recursion through datatypes is supported. In particular does the
> following program compile, run, and produce 3?
Yes. To be absolutely precise, I tried the following program and it prints 3.
datatype ('a, 'b) altlist = nil | cons of 'a * ('b, 'a) altlist
val x = cons (1, (cons (true, cons (2, nil))))
fun f (cons (n, (cons (_, (cons (m, _)))))) = n + m
val _ = print (concat [Int.toString (f (x)), "\n"])
> That program will not compile in CIL, nor in RML since in both cases
> the implementors decided not to support polymorphic recursion through
> datatypes. The program compiles and produces 3 when typed in at the
> SML/NJ prompt. I couldn't get my (very old) copy of MLton to compile
> the program, but wondered if a more recent version would.
Must have been a bug in the old MLton. The new one works, and the monomorphizer
(was supposed to) handled that from its first design.
> This sort of recurring through a datatype with the order of type
> parameters changed is a nuisance to implement in a monomorphizing
> language: one can design such a datatype with n-1 constructors, each
> changing the order of 2 out of n type parameters, resulting in n!
> mutually recursive datatypes after monomorphization for a particular
> set of disjoint type parameters.
MLton's monomorphiser expands the polymorphic datatypes completely lazily, only
creating a new monomorphic datatype when a constructor is used in the program at
a given type. I don't think this can lead to this problem you mention (but I've
thought about it < 1 minute).
> I haven't seen any program which makes use of this feature of SML.