[Haskell-cafe] Re: Equirecursive types?
rjmh at cs.chalmers.se
Mon Mar 27 06:51:14 EST 2006
>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.
More information about the Haskell-Cafe