Ezra's Research: Recursive Types in Ocaml

Why can I not have a type like this in OCaml?

type t = string * (Left of t | Right of t)

Is there a type-theoretic reason for it?

Posted by Ezra elias kilty Cooper on October 10, 2005 6:23 PM | Permalink

You can do this in O'Caml using polymorphic variants, which allow you to define anonymous variant types:

type t = string * [`Left of t | `Right of t]

a value of this type can be defined as:

let rec x = ("tinker", `Left of ("tailor", `Right of x))

Type theoretically, the type is just μX. String * (X + X), where μX. denotes a recursive type.

I see; the problem was in the necessity of a name for the sum type. Jeremy Yallop pointed out privately that this works as well:

type s = string * r and r = Left of s | Right of s

Thanks, both.

Ezra's Research