равны? предикат для списков


Упражнения 2.54

Два списка, как говорят быть равны? если они содержат равные элементы расположены в том же порядке.

Например,

(equal? '(this is a list) '(this is a list))

- это правда, но

(equal? '(this is a list) '(this (is a) list))

является ложным. Чтобы быть более точным, мы можем определить равными? рекурсивно с точки зрения основной экв? равенство символов говорят, что А и Б будут равны? если они оба символы и символы экв?, или если они оба такие списки что (автомобиль) - это равные? в (автомобиль Б)и (цхд а) является равным? для (цхд б). Используя эта идея, реализовать равные? как процедуры.

Я написал следующее:

(define (equal? a b)
  (or (and (and (symbol? a) (symbol? b)) (eq? a b))
      (and (null? a) (null? b))
      (and (and (and (not (null? a)) 
                     (list? a))
                (and (not (null? b))
                     (list? b)))
           (and (equal? (car a) (car b))
                (equal? (cdr a) (cdr b))))))

Это может быть улучшено?



1183
3
задан 20 апреля 2011 в 03:04 Источник Поделиться
Комментарии
1 ответ

Поскольку и операция является ассоциативной, можно написать:

(and (and (symbol? a) (symbol? b)) (eq? a b))

как:

(and (symbol? a) (symbol? b) (eq? a b))

Аналогично:

(and (and (and (not (null? a)) 
(list? a))
(and (not (null? b))
(list? b)))
(and (equal? (car a) (car b))
(equal? (cdr a) (cdr b))))

эквивалентно:

(and (not (null? a))
(not (null? b))
(list? a)
(list? b)
(equal? (car a) (car b))
(equal? (cdr a) (cdr b)))

Можно было бы расширить определение равных? для работы с обоими списками и пар просто меняя тест списке? для пары?. Это также устраняет необходимость испытаний для некурящих ничтожность в том же и статья.

Используя приведенные выше рекомендации, можно написать короче определение таким образом:

(define (equal? a b)
(or (and (symbol? a) (symbol? b) (eq? a b))
(and (null? a) (null? b))
(and (pair? a)
(pair? b)
(equal? (car a) (car b))
(equal? (cdr a) (cdr b)))))

Концептуально, можно думать о нуль-символ, и пары видах. Для проверки на равенство двух объектов, один должен проверить, что их типы одинаковы, а затем Проверка на равенство в этом типе.

Таким образом, для проверки на равенство, если мы видим, что объекты являются символами, тест для эквалайзера?; если мы видим, что объекты имеют значение NULL, то никаких дальнейших испытаний необходимо, чтобы они равны; если мы видим, что объекты являются пары, Тест на равенство Car и CDR.

Это понимание позволяет расширить определение равных? к другим типам (хэш-таблицы, векторы и т. д.) если решите это сделать в будущем.

3
ответ дан 20 апреля 2011 в 12:04 Источник Поделиться