Как рекурсивно перебирать списки с CDR работают с Cons в Схеме? - PullRequest
0 голосов
/ 23 сентября 2019

В частности, у меня есть следующая функция

(define (even-odd-filter x . intlist)   
  (if (equal? '() intlist)
      '()
      (if (equal? (modulo x 2) (modulo (car intlist) 2))
          (cons (car intlist) (even-odd-filter x (cdr intlist)))
          (even-odd-filter x (cdr intlist)))))

Может кто-нибудь объяснить, почему это сломается на второй итерации?Насколько я знаю, (список автомобилей) предназначен для ссылки на первый элемент списка, однако во втором рекурсивном вызове

(modulo (car int list) 2)

вызывает ошибку, как считает интерпретаторчто (car intlist) ссылается на весь список, а не на первый элемент указанного списка.

Я совершенно заблудился в этом, и любая помощь будет принята с благодарностью.

Ответы [ 2 ]

1 голос
/ 23 сентября 2019

Причина в том, что если вы позвоните (even-odd-filter 5 1 2 3), это сделает (cons 1 (even-odd-filter 5 '(2 3))), а intlist будет ((2 3)) во второй итерации.

Чтобы избежать этого, лучше использовать помощника, так что только внешний вызов имеет аргументы rest:

(define (even-odd-filter x . intlist)
  (let helper ((intlist intlist))   
    (cond
      ((null? intlist) '())
      ((equal? (modulo x 2) (modulo (car intlist) 2))
       (cons (car intlist) (helper (cdr intlist))))
      (else
       (helper (cdr intlist))))))

Еще одна приятная вещь с этим заключается в том, что x, это не меняетсяитерация не передается, а используется как свободная переменная.Это облегчает чтение кода.Поскольку вы вложили if, я превратил его в cond, что соответствует типичному сценарию if-then-else.

Если вы действительно хотите использовать аргументы rest в рекурсии, вам нужно использовать apply в каждом рекурсивном вызове.Это не очень эффективно, так как, скорее всего, будет создавать новый список на каждой итерации:

(define (even-odd-filter x . intlist)   
  (if (equal? '() intlist)
      '()
      (if (equal? (modulo x 2) (modulo (car intlist) 2))
          (cons (car intlist) (apply even-odd-filter x (cdr intlist)))
          (apply even-odd-filter x (cdr intlist)))))
0 голосов
/ 23 сентября 2019

Причина в том, что если вы определяете функцию с синтаксисом:

(define (function arg1 . rest-of-args-as-list) body)

, вы должны вызывать ее всегда с определенным количеством аргументов, но не со списком.Например, предполагая, что вам нужно работать с последовательностью целых чисел, вы можете вызвать ее следующим образом:

(function 1 2 3 4 5)

и внутри тела функции arg1 будет связано с 1 и rest-of-args-as-list будет привязан к списку (2 3 4 5).

Так что в вашем случае, если вы вызовете функцию: (even-odd-filter 1 2 3 4 5), x будет привязан к 1, intlis t к (2 3 4 5) и во второй итерации функция будет вызываться как: (even-odd-filter 1 (3 4 5)) (поскольку x равно 1, а cdr из (2 3 4 5) равно (3 4 5)).И вызов его таким образом вызовет ошибку (в DrRacket):

modulo: contract violation
  expected: integer?
  given: '(3 4 5)
  argument position: 1st
  other arguments...:
> 

Как вы могли бы решить эту проблему?

Возможно определить функцию с одним аргументом, которыйсписок.Вот переписывание вашей функции следующим образом:

(define (even-odd-filter intlist)   
  (cond ((equal? '() intlist) '())
        ((equal? '() (cdr intlist)) intlist)
        ((equal? (modulo (car intlist) 2) (modulo (cadr intlist) 2))
         (cons (cadr intlist) (even-odd-filter (cons (car intlist) (cddr intlist)))))
        (else (even-odd-filter (cons (car intlist) (cddr intlist))))))
...