An example of substituability test that is recursive

[John Rose]

On Jan 31, 2019, at 10:41 AM, forax at univ-mlv.fr wrote:
> 
> yes, i creates a DAG that will be too long to traverse :(
> you basically, DDOS yourself if you do a ==.

The complexity is exponential in depth, and
can be more than linear in heap allocation,
because of the risk of repeat traversals.

A worklist algorithm could make use of the
secret implementation identity of heap nodes
to push the complexity back down to heap
allocation size.  A portable algorithm could
not.  This is one more bit of evidence it should
be a system intrinsic rather than a vanilla library
function.