[Haskell-cafe] Equirecursive types?
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