1
$\begingroup$

I am looking for an algorithm that I can use to compare nested and potentially recursive data structures, for example to implement the Scheme equal? function. equal? recursively compares two objects for equality and properly handles cycles. Specifically, the algorithm needs to return true iff the (possibly infinite) unfoldings of the graphs would be equal, e.g.

(letrec ((a (cons 1 (cons 2 a)))
         (b (cons 1 (cons 2 (cons 1 (cons 2 b))))
  (equal? a b))

is true because a and b are both cyclic lists that repeat the sequence (1 2) infinitely.

Destructive modification of traversed nodes is thread-unsafe, requires a spare bit in object headers, and requires a separate traversal to reset the bit. Using a hash table to store object addresses is not safe in the presence of a moving garbage collector unless the GC is blocked for the duration of the traversal (so the operation cannot be implemented except as a primitive).

$\endgroup$
2
  • 1
    $\begingroup$ Library request and the lines of code suggests it is not on-topic here. Are you looking for cycle detection in the graph? What kind of hashing? Sorry, the title, body and the tag are (probably) different subjects. To handle the cycles flagging already visited nodes does the job, could you clarify the question? $\endgroup$ – Evil Aug 22 '16 at 18:31
  • 2
    $\begingroup$ What approaches have you consdiered? What are the algorithmic challenges? What makes this difficult, from an algorithmic perspective? What is the specification for equal? -- when should two objects be considered equal? What does the title have to do with the body of the question? I'm not even sure how to parse "cycle-detecting hashing and comparison"; it would be good to elaborate on what you're referring to in the body of the question (I can make some guesses, but I shouldn't have to guess). Coding/implementation questions are off-topic here. Library requests are also off-topic. $\endgroup$ – D.W. Aug 22 '16 at 19:26
2
$\begingroup$

There is no pure way to detect cycles, where by pure I mean without caring about representation details such as object addresses. If you only allow examining data by comparing fields at base types, then there is no way to distinguish e.g. a cyclic list from a very long list. If you start examining

(1 2 3 4 5 6 7 8 9 10 11 …
(1 2 3 4 5 6 7 8 9 10 11 …

then maybe one of them is the list (1 2 3 4 5 6 7 8 9 10 11) and the other is (repeat (1 2 3 4 5 6 7 8 9 10 11) where (repeat cycle) builds a cyclic list that repeats its arguments — but you need to examine one more node to find the difference. Since the difference could be arbitrary far, there's no way to prove that two cyclic lists are equal.

The most practical solution is to compare object addresses to detect cycles. I expect that this is how most Scheme implementations do it. This requires some knowledge of how the garbage collector works, and specifically the ability to temporarily prevent it from relocating any object that is within the already-traversed part of the data structure. Locking GC moves might not hurt much, it depends on the GC technology: a mark-and-sweep GC doesn't need to move objects.

By the way, mark-and-sweep GC usually detect cycles by using a spare bit in the object. But that doesn't generalize well to arbitrary processing of arbitrary data structures.

If you're building your own data structure, as opposed to having to cope with arbitrary data structures like equal?, then a good approach is to not store cycles. Purely functional data structures typically don't have cycles in the first place since they can only create cycles with a statically-known structure which is not very useful. As with many problems in computing, this is solved by adding a level of indirection: instead of having the data structure contain a pointer chain that loops back to itself, have it contain references, i.e. the data structure is represented as some kind of map from identifiers from elements and nested data structures are stored using their identifier. When doing this, it's useful to perform hash consing, i.e., when applying a constructor, verify if the result is already referenced in the map and if so use the existing identifier rather than making a new one. This can save memory, and also processing time since traversal algorithms never need to handle the same data structure twice. In particular, with this trick, you can test equality of data structures by simply testing equality of identifiers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.