(Схема) Проверьте список пунктов, все ли удовлетворены логическим соотношением - PullRequest
Новая
       73

(Схема) Проверьте список пунктов, все ли удовлетворены логическим соотношением

0 голосов
/ 20 октября 2018

В настоящее время я изучаю Схему и сталкиваюсь с вопросом, описание которого, например, такое: Определите и реализуйте функцию, которая принимает что-то вроде логического оператора check и список xs, затем проверьте, оценивается ли это (check a b) как истинноедля всех двух ближайших элементов a b в списке xs.

Ниже приведен пример, например: 

(check < '(15 16 17 18)) 
#t

(check > '(5)) 
#t

(check > '()) 
#t

(check (lambda (a b) (eq? b (+ a 1))) '(11 12 13))
#t

(check eq? '(4 4 5))
#f

На мой взгляд, этот вопрос похож на проверкуСписок сортируется в порядке возрастания или нет, но реализация может иметь некоторые различия.Я намереваюсь определить рекурсивную функцию, связанную с foldl, и выполнить некоторые условные проверки, но мой вопрос заключается в том, как определить, какой логический оператор и как они выполняют свою работу в моем коде, чтобы любой мог помочь с этим?Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 21 октября 2018

Есть два тривиальных случая, когда функция может возвращать true, а именно пустые списки и списки с одним элементом.Вы проверяете пустые списки с помощью null?.Сначала необходимо проверить, является ли список пустым, а если нет, то является ли его подсписок пустым (в этом случае обязательно есть только один элемент).Если какой-либо из этих списков пуст, предикат тривиально возвращает true.

В противном случае в общем случае предикат может вернуть true, только если check работает для пары элементов (эта пара существует, поскольку мыисключены списки размером 0 и 1), и , если подсписок также удовлетворяет предикату. 

(define (every-pair-check? check xs)
  (or (null? xs)
      (null? (cdr xs))
      (and (check (car xs) (cadr xs))
           (every-pair-check? check (cdr xs)))))
0 голосов
/ 20 октября 2018 
(define (check-every? check-operator lst)
  (cond ((or (null? lst) (= (length lst) 1)) #t)
        ((check-operator (car lst) (cadr lst)) (check-every? check-operator (cdr lst)))
        (else #f)))

Это останавливается, как только начинается первый #f тест, поэтому он эффективен.

Я хотел сохранить некоторые проверки следующим образом: 

;; cave! Erroneous code!!
(define (check-every? check-operator lst)
  (cond ((and (null? (cdr lst)) (<= (length lst) 1)) #t)
        ((check-operator (car lst) (cadr lst)) (check-every? check-operator (cdr lst)))
        (else #f)))

Эта стратегия будет работать вобычный lisp, потому что (cdr '()) в общем lisp возвращает '().Но в Racket / Scheme это возвращает ошибку.Как запутанно!Спасибо, напомни мне, @coredump!

Я подумал:

(null? (cdr lst)) - это хак для (or (null? lst) (= (length lst) 1)), однако, если один элемент lst равен '(), томы были бы в беде.Но с обычным списком номеров это работает.В противном случае следует использовать более длинный тест.Теперь я исправил (and (null? (cdr lst)) (<= (length lst) 1)), который - из-за короткого замыкания and - проверяет только на (null? (cdr lst)), но, если это правда, дополнительно проверяет, равна ли длина lst 1 или нулю.Только тогда он возвращает #t для этого случая.Таким образом, эта форма улавливает случай, когда lst может содержать '() в качестве элемента где-то еще, чем в последней позиции, по-прежнему сводя к минимуму количество тестов за цикл.

Но хорошо, так как этов Racket невозможно, первая версия самая короткая ...

...