CODEWITHSUNDEEP
typesfunctional-programmingprogramming-languagessmlml
Tim
Tim

Reputation: 99408

In SML, are product types and function types type constructors?

In Ullman's SML book:

We can build new types from old types T1 and T2, as follows.

  1. T1 * T2 is a "product" type, whose values are pairs. The first component of the pair is of type T1 and the second is of type T2.

  2. T1 -> T2 is a "function" type, whose values are functions with domain type T1 and range type T2.

  3. We may create new types by following a type such as T1 by certain identifiers that act as type constructors.

(a) The list type constructor. That is, for every type T1, there is another type T1 list, whose values are lists all of whose elements are of type T1.

(b) The option type constructor. For every type T1 there is a type T1 option whose values are NONE and SOME x where x is any value of type T1.

(c) Additional type constructors ref, array, and vector.

I was wondering if * in product types and -> in function types are considered type constructors?

If no, why?

Upvotes: 1

Views: 312

Answers (1)

ruakh
ruakh

Reputation: 183270

They're not, but this is mostly just for syntactic reasons:

  • * and -> are keywords rather than identifiers (setting aside the unrelated use of * as an identifier in e.g. 3 * 4 = 12).
  • We write int * real and int -> real rather than (int, real) * and (int, real) ->.
  • A type constructor has a fixed number of parameters (for example, list always takes one parameter — we can't write (int, real) list — and int always takes none), but int * real * char * string is a 4-tuple. (In other words: * is "overloaded" for any n-tuple type with n ≥ 2. So it's like infinitely many type constructors, rather than just one.)

But I don't think there's any reason that it must be this way. One could imagine a parallel-universe version of Standard ML that:

  • did not define * and -> as reserved words, but just as identifiers in the initial basis (analogously to ref or int).
  • allowed type constructors to be made infix (analogously to how 3 + 4 means op+ (3, 4)), and declared * and -> as such.
  • didn't support the * notation for products of three or more types, but rather, interpreted int * real * char * string as ((int * real) * char) * string. (In our universe, 'a * 'b * … * 'n is just syntactic sugar for { 1: 'a, 2: 'b, …, 14: 'n }; perhaps in the parallel universe that's not considered very useful for products of three or more types?)

In fact, even in our own universe, we can write:

type ('a, 'b) pair = 'a * 'b
type ('a, 'b, 'c) triple = 'a * 'b * 'c
type ('a, 'b) function = 'a -> 'b

which creates type constructors pair, triple, and function such that (int, real) pair is synonymous with int * real, (int, real, char) triple is synonymous with int * real * char, and (int, real) function is synonymous with int -> real. (Not that anyone wants that.)

Upvotes: 1

Related Questions