Term equality is structural. Constants match when their values match, holes when their names match, and symbols when their names and corresponding left and right children match. section 10.1
This equality makes two binary terms interchangeable only when their complete shapes and contents agree. It supports unification, where substitutions replace bound holes so that otherwise different terms become equal. section 10.1
Comparing binary terms
ImStack(X,ImStack(X,EmptyStack)) and ImStack(2,Y) are unequal: their corresponding children differ, even though both have the same outer symbol name. section 10.1
Structural equality has practical implementation consequences:
- Record classes can generate value equality automatically, including recursive comparisons of nested terms. section 1.2.1 section 10.1
- Recursive equality can be expensive for long structures and may overflow the call stack, motivating nonrecursive custom implementations. section 1.2.1
