MLton and polymorphic recursion through datatypes?

[Matthew Fluet]

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

The problem, I think, is that datatypes with polymorphic recursion are of
limited use when you can't (easily) write functions with polymorphic
recursion.  For example, with the alternating list datatype

datatype ('a, 'b) altlist = nil | cons of 'a * ('b, 'a) altlist

you would like to write the map function with the type:

('a -> 'c) -> ('b -> 'd) -> ('a, 'b) altlist -> ('c, 'd) altlist

The simplest function one might like to write is the following:

fun altmap fa fb
  = fn nil => nil
     | cons (h, t) => cons (fa h, altmap fb fa t)

which does typecheck, but gives you an overly restricted type:

('a -> 'b) -> ('a -> 'b) -> ('a,'a) altlist -> ('b,'b) altlist

because the SML type system requires all occurrences of a recursively
defined function to be used monomorphically inside the body of the
definition.  

You can get around this by "unrolling" the recursion manually:

fun altmapA fa fb
  = fn nil => nil
     | cons (h, t) => cons (fa h, altmapB fb fa t)
and altmapB fb fa
  = fn nil => nil
     | cons (h, t) => cons (fb h, altmapA fa fb t)
val altmap = altmapA

But, IMHO, you're left somewhat annoyed by the fact that you needed to
write almost syntactically identical functions to satisfy the type system.