UMBC ebiquity
SIGART Newsletter No. 60
Different Fringe for Different Folk
November 1, 1976
As Greussay has pointed out, the SAMEFRINGE problem has been notoriously overused as a justification for coroutines. However, the "ordinary LISP" solution he offers is unnecessarily inefficient in both time and space. Briefly, the SAMEFRINGE problem is to write a function that will return true if the atoms in two LISP trees are the same and appear in the same order when the trees are traversed in left-to-right preorder (i.e., if you PRINT them and delete all parentheses and spaces, the two resulting character strings would be identical). The problem is finding an efficient solution that will not do any unnecessary work when the two trees differ in their first positions.