[Haskell-cafe] Equirecursive types?

Ross Paterson ross at soi.city.ac.uk
Sun Mar 26 18:08:13 EST 2006

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))

More information about the Haskell-Cafe mailing list