[Haskell-cafe] Re: Equirecursive types?

[John Hughes]

>From: Ross Paterson <ross at soi.city.ac.uk>
>
>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