Два ключевых момента:
(а) испытание на совпадение типа одинаковых отдельных компонентов
(б) проверка на совпадение значений при переходе к «основным» значениям элемента
Какой бы язык программирования вы не использовали, если мы посмотрим на часть списков, например, (a (bc) ...) и (abc ...), мы заметим после того, как увидим «a», что каждый имеет другой тип. Первый список следует за «a» со списком, а второй список следует за другим элементом, не относящимся к списку. Языки, скорее всего, потерпят неудачу (сигнализируют об ошибке какого-либо рода), или же позволят вам рассматривать каждый из этих различных типов одинаково, но обычно предоставляют способ запроса типа.
В схеме (и я точно не помню), первый список имеет значение car, равное a, а значение cdr - список ((b c) ...). Второй список имеет значение автомобиля a, но cdr возвращает список (b c ...). Эти два не могут быть одинаковыми, если язык не предлагает иного взгляда на «сходство».
Этот вид тестирования для типа объекта будет первым шагом к проверке того, совпадают ли списки.
Далее мы проверяем значения базовых элементов в соответствующих местах в уже проверенных идентичных структурах. Мы должны пройти структуры должным образом (то есть, в зависимости от деталей структуры).
Детали алгоритма обхода зависят от языка программирования. Некоторые языки помогают больше, чем другие, избегать ошибок и проверять одинаковость.
Мы можем использовать рекурсивные или итеративные подходы. С концептуальной и рекурсивной схемой это более естественно.
Пример псевдокода, в котором тип и значение обрабатываются с помощью составленного теста =?
function f (l1, l2):
(=? car(l1) car(l2))
and
(f cdr(l1) cdr(l2))
Мы отмечаем рекурсию. Это значит, что если вы получаете простой элемент, он проверяет на равенство и возвращает это значение. Если эта функция была вызвана напрямую, то это окончательный ответ, если он был вызван рекурсивно, то он отправляет этот ответ обратно по цепочке вызовов функций, заставляя некоторые вложенные (f cdr (l1) cdr (l2)) возвращать false или true и, в конечном итоге, вызов наивысшего уровня также возвращает false или потенциально все еще может вернуть true (обратите внимание на требование «и» и как оно работает. true приходит только в том случае, если каждая часть истинна, а false - если любая часть ложна). Точно так же, если функция получает список, то она проверяет автомобильную часть и "и" это значение t / f с тем, что она получает, когда она рекурсивно вызывает себя снова в остальной части списка. Следовательно, эта функция обрабатывает списки и не списки в любой сложной структуре подсписков, которые вы передаете. [помните, мы предполагали, что =? управлял как проверками типа, так и значениями, например, чтобы (=? b '(b)) было бы #f]
[Также см. http://cs.gettysburg.edu/~tneller/cs341/scheme-intro/exercises.html#Equivalence, что вы можете использовать для проверки эквивалентности.]