# MLton and polymorphic recursion through datatypes?

**Matthew Fluet
**
Matthew Fluet <fluet@CS.Cornell.EDU>

*Tue, 17 Apr 2001 10:06:30 -0400 (EDT)*

>* > 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.