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

[John Skaller <skaller@users.sourceforge.net>]

[-- Attachment #1: Type: text/plain, Size: 1225 bytes --]

On Thu, 2005-06-30 at 11:51 +0200, Andreas Rossberg wrote:
> 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.

I do not see that. The current algorithm is recursive descent
is it not? That can also be used with a trivial modification
to test graph equivalence, by simply keeping a list of visited
nodes and not revisiting them. 

The problem of course is that the cost per node
is O(N) where N is the recursion depth.

Profiling indicates my code spends up to 60% of all time
doing comparisons.

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

That seems reasonable, since the client will usually
know if the data structure contains cycles or not.

-- 
John Skaller <skaller at users dot sourceforge dot net>
Download Felix: http://felix.sf.net

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]