Deep-equal between sequences

[Michael Kay]

> 
> some $i in $firstSeq satisfies $secondSeq[deep-equal(.,$i)]
> 

Certainly this meets the requirement, and certainly a half-decent
implementation will exit when it finds the first "true" value. But in the
worst case, without a very clever bit of optimization, it will result in N*M
deep-equal comparisons.

I saw another requirement like this recently - essentially grouping where
grouping keys were compared using deep equality. It suggests to me a need
for a function

deep-comparison-key(node(), collation) -> xs:atomicValue

where the result of the function is undefined except to the extent that
deep-comparison-key(N, C) eq deep-comparison-key(M, C) if and only if
deep-equal(N, M, C). (One possible implementation would be to serialize into
canonical XML and then replace all strings with a collation key).

The downside is that the semantics of deep-equal are themselves so fragile -
the function so often doesn't perform exactly the comparison you would like.

Another solution you could try to implement at application level would be to
define a hash function such that deep-equal(A, B) => hash(A) eq hash(B), and
then confine the deep-equal() comparisons to nodes where the hash values are
equal. A good start might be hash($N) == string($N). Not very effective
where most of the information is held in attributes, but OK in most other
cases.

Michael Kay