From: Ross Paterson
On Sun, Mar 26, 2006 at 01:22:17PM -0500, Jim Apple wrote:
According to Pierce's book, O'Caml has an optional equirecursive type extension that turns off the occurs check. Is there any particular reason Haskell doesn't have that available?
It's certainly feasible, though turning off the occurs check doesn't do it: you need to use the unification algorithm for regular trees (see e.g. section 6.7 of the revised Dragon Book). You also need to decide what to do about
type T = T
I think the arguments against it are: * many common errors will lead to perfectly legal types. * it adds convenience, but not expressive power. * it only works for regular types, where the arguments of uses of the type constructor on the rhs are the same as (or a permutation of) the arguments on the lhs, so this is out:
type T a = Either a (T (a,a))
Indeed, error messages in common cases would be worsened significantly, because as Ross says, common errors (such as forgetting a parameter in a recursive call) would lead to legal definitions that cause a type error when applied. Partly for this reason, OCaml permits recursion only in object types, if I remember rightly, where it's most useful. In other cases the occurs check is still used. John