Продолжения понимания справки в Схеме
Я работал вместе с Маленьким Интриганом для изучения Схемы и использовал PLT-схему своей среды.
Маленький Интриган помог мне чрезвычайно с рекурсией (это просто для меня теперь), но я застреваю на части книги, которая представляет "коллекторы" и вызывает функцию в целом продолжение.
Вот пример кода, который они использовали. Я понимаю рекурсивные элементы, но я застреваю, в особенности на функциях лямбды - мой ум не может следовать за путем и как аргументы в пользу той функции лямбды установлены (так как их единственный вызов должен назвать их снова в рекурсии, нет никакого конкретного использования в теле функции).
Если кто-то мог бы более или менее дать мне передохнуть вниз пути вычисления через рекурсию функции в коллекторы лямбды, которые могут помочь мне.
;; Build a nested list of even numbers by removing the odd ones from its
;; argument and simultaneously multiply the even numbers and sum the odd
;; numbers that occur in its argument.
(define (even-only-collector l col)
(cond
((null? l)
(col (quote ()) 1 0))
((atom? (car l))
(cond
((even? (car l))
(even-only-collector (cdr l)
(lambda (newl p s)
(col (cons (car l) newl)
(* (car l) p) s))))
(else
(even-only-collector (cdr l)
(lambda (newl p s)
(col newl
p (+ (car l) s)))))))
(else
(even-only-collector (car l)
(lambda (al ap as)
(even-only-collector (cdr l)
(lambda (dl dp ds)
(col (cons al dl)
(* ap dp)
(+ as ds)))))))))
;; The collector function
(define (collector newl product sum)
(cons sum
(cons product newl)))
Заранее спасибо!!
2 ответа
Попробуйте что-нибудь попроще, чтобы увидеть, как это работает. Например, вот версия функции list-sum, которая получает аргумент продолжения (который часто называют k):
(define (list-sum l k)
(if (null? l)
???
(list-sum (cdr l) ???)))
Основной паттерн есть, а недостающие части - это то место, где происходят интересные вещи. Аргумент продолжения - это функция, которая ожидает получить результат -- так что если список равен нулю, то понятно, что мы должны послать его 0, так как это сумма:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) ???)))
Теперь, когда список не равен нулю, мы вызываем функцию рекурсивно с хвостом списка (другими словами, это итерация), но вопрос в том, что должно быть продолжением. Делать это:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) k)))
явно неправильно -- это означает, что k в конечном итоге получит сумму (cdr l) вместо всей l. Вместо этого используйте там новую функцию, которая тоже просуммирует первый элемент l вместе со значением, которое он получит:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) (lambda (sum) (+ (car l) sum)))))
Это приближается, но все равно неправильно. Но стоит подумать о том, как все работает - мы вызываем list-sum с продолжением, которое само по себе получит общую сумму, и добавляем к ней первый элемент, который мы видим сейчас. Недостающая часть видна в том, что мы игнорируем k. Что нам нужно, так это составить с этой функцией k -- так мы выполним ту же самую операцию с суммой, а затем отправим результат на k:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) (compose k (lambda (s) (+ s (car l)))))))
, который, в конце концов, работает. (Кстати, помните, что каждая из этих функций лямбда имеет свою собственную "копию" l). Вы можете попробовать это с:
(list-sum '(1 2 3 4) (lambda (x) x))
И, наконец, заметьте, что это то же самое, что и:
(define (list-sum l k)
(if (null? l)
(k 0)
(list-sum (cdr l) (lambda (s) (k (+ s (car l)))))))
если вы сделаете композицию явной.
(Вы также можете использовать этот код на промежуточном+лямбда-студентском языке, и нажать на шаговую кнопку, чтобы посмотреть, как будет происходить оценка - это займет некоторое время, но вы увидите, как вложены функции продолжения, каждая из которых имеет свой вид списка)
.Вот один способ помочь вам "получить более конкретную идею". Представьте, если бы коллектор был определен таким образом:
(define (collector l p s)
(display l)
(newline)
(display p)
(newline)
(display s)
(newline))
В базовом случае, если Вы передаете в пустом списке, то он вызовет Вашу функцию с аргументами '(), 1, и 0. Теперь работайте с одноэлементным списком, и посмотрите, чем он вызовет Вашу функцию. Продолжайте работать с длинными и длинными списками, пока не поймете, что происходит.
Удачи!
.