Take the 2-minute tour ×
  1. Can someone explain the difference between them?

  2. Also, when trying out:

datatype exp = Const of real | Pair of exp * exp;

val my_exp_2 = Pair(Const(1.2),Pair(Const(9.0),Const(2.0)));

The interpreter gives:

val my_exp_2 = Pair (Const 1.2,Pair (Const #,Const #)) : exp

Why does the # symbol appear there?


share|improve this question
Read the # as ... -- there are more nested expressions there, but the printer abbreviates them for readability. If this is SML/NJ, you can set e.g. Control.Print.printDepth := 10 to adjust it. –  Andreas Rossberg Jun 15 '12 at 16:36

1 Answer 1

up vote 5 down vote accepted

A recursive datatype is a datatype, which uses itself in its definition.

An example of this could be:

datatype intlist = IntNil
                 | IntCons of int * intlist

Notice how intlist is used in the definition of the IntCons value constructor.

val ls = IntCons(5, IntCons(6, IntNil));

Notice how IncCons contains another list value in this example.

A polymorphic datatype is a datatype, where one or more of the value constructors can contain a polymorphic value.

For instance, you could look at:

datatype 'a pair = Pair of 'a * 'a

Here, 'a is a type variable, and as such the constructor can be used on values of any type. Example:

val pairInt = Pair(1, 5);
val pairStr = Pair("Hello", "Goodbye");
val pairChr = Pair(#"x", #"y");

These two things are often combined into polymorphic recursive datatypes, as is done for normal lists:

datatype 'a mylist = MyNil
                   | MyCons of 'a * 'a mylist;

This is both polymorphic and recursive, as can be seen in these examples:

val listInt = MyCons(5, MyCons(6, MyNil));
val listStr = MyCons("abc", MyCons("def", MyNil));
val listChr = MyCons(#"a", MyCons(#"b", MyNil));
share|improve this answer

Your Answer


