MLton and polymorphic recursion through datatypes?

Allyn Dimock
Mon, 16 Apr 2001 20:04:02 -0400 (EDT)


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?

let 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
  f (x)

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. 

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.

I haven't seen any program which makes use of this feature of SML.

-- Allyn