Re: [Caml-list] Type abstraction and (polymorphic) equality

[Andreas Rossberg <rossberg@ps.uni-sb.de>]

sejourne_kevin wrote:
> 
> A generic equality should be one that work with recursives.

Not so easy. In order to be a proper equivalence test for cyclic data 
structures it essentially had to test graph equivalence, which is the 
same as testing equivalence of DFAs. So it would be a completely 
different algorithm, with significant complexity in space and time.

> When the compiler generate code he have the complete type, no ?

No, not in the presence of polymorphism.

> so he
> can know if a type is recursives or not, so he can select the slow but
> recursives compliant version are the actual.

Recursion on the type level does not necessarily imply recursion on the 
value level. Just consider lists, they are rarely cyclic. On the other 
hand, there may be recursion even where it is not visible in types, e.g. 
when you have implicit forms of existential quantification, like for 
abstract types, (non-recursive) object types, function types (closures). 
So this is not a useful criterium.

In Alice ML, where we have recently added such a co-recursive 
equivalence operation, we opted for turning it into a separate 
operation, to avoid these issues.

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

Let's get rid of those possible thingies!  -- TB