Little Schemer evens-only * & co

Ответ 1

Я нашел этот раздел запутанным и в первом чтении, и только начал его получать после того, как я прочитал в другом месте о продолжениях и стиле продолжения прохождения (вот что это такое).

Рискуя объяснить что-то, что вы уже получили, один из способов взглянуть на него, который помог мне, - подумать о "коллекторе" или "продолжении" как о замене нормального способа возврата функции. В нормальном стиле программирования вы вызываете функцию, получаете значение и делаете что-то с ним в вызывающем. Например, стандартная рекурсивная функция length включает выражение (+ 1 (length (cdr list))) для непустого случая. Это означает, что после того, как (length (cdr list)) вернет значение, произойдет вычисление, ожидающее, что произойдет с любым значением, которое оно производит, которое мы могли бы назвать (+ 1 [returned value]). В обычном программировании интерпретатор отслеживает эти ожидающие вычисления, которые имеют тенденцию "складываться", как вы можете видеть в первых парах глав книги. Например, при вычислении длины списка рекурсивно мы имеем гнездо "ожидающих вычислений" как много уровней в глубину, так как список длинный.

В стиле продолжения передачи вместо вызова функции и использования возвращаемого результата в вызывающей функции мы сообщаем функции, что делать, когда она производит свое значение, предоставляя ей "продолжение" для вызова. (Это похоже на то, что вы делаете с обратными вызовами в асинхронном Javascript-программировании, например: вместо записи result = someFunction(); вы пишете someFunction(function (result) { ... }), и весь код, который использует result, входит в функцию обратного вызова).

Здесь length в стиле продолжения прохождения, просто для сравнения. Я вызвал параметр продолжения return, который должен предлагать, как он функционирует здесь, но помните, что это просто обычная переменная Scheme, как и любая другая. (Часто параметр продолжения называется k в этом стиле).

(define (length/k lis return)
  (cond ((null? lis) (return 0))
        (else
         (length/k (cdr lis)
                   (lambda (cdr-len)
                     (return (+ cdr-len 1)))))))

Есть полезный совет для чтения этого типа кода в статья о продолжениях соавтором Little Schemer Дэном Фридманом. (См. Раздел II-5, начиная со страницы 8). Перефразируя, вот что говорится выше в разделе else:

Представьте, что у вас есть результат вызова length/k на (cdr lis), и назовите его cdr-len, затем добавьте один и передайте результат этого добавления к вашему продолжению (return).

Обратите внимание, что это почти то же, что должен интерпретировать интерпретатор при оценке (+ 1 (length (cdr lis))) в нормальной версии функции (за исключением того, что он не должен давать имя промежуточному результату (length (cdr lis)). продолжения или обратные вызовы, которые мы установили поток управления (и имена промежуточных значений) явным, вместо того, чтобы интерпретатор отслеживал его.

Пусть этот метод применяется к каждому предложению в evens-only*&co. Это немного усложняется тем, что эта функция генерирует три значения, а не один: вложенный список с нечетными номерами удален; произведение четных чисел; и сумма нечетных чисел. Здесь первое предложение, где (car l) известно как четное число:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col (cons (car l) newl)
                       (opx (car l) product)
                       sum)))

Представьте, что у вас есть результаты удаления нечетных чисел, умножая evens и добавляя нечетные числа из списка cdr списка, и назовите их newl, product и sum соответственно. consглава списка на newl (так как это четное число, оно должно идти в результате); умножить product на заголовок списка (поскольку мы вычисляем произведение эвенов); оставить sum самостоятельно; и передать эти три значения для вашего ожидания col.

Здесь случай, когда голова списка является нечетным числом:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col newl product (op+ (car l) sum))))

Как и раньше, но передавайте те же значения newl и product в продолжение (т.е. "возвратите" их) вместе с суммой sum и главой списка, поскольку мы суммируем нечетные числа.

И вот последний, где (car l) - вложенный список, и который немного усложняется двойной рекурсией:

(evens-only*&co (car l)
                (lambda (newl product sum)
                  (evens-only*&co (cdr l)
                                  (lambda (dnewl dproduct dsum)
                                    (col (cons newl dnewl)
                                         (opx product dproduct)
                                         (op+ sum dsum))))))

Представьте, что у вас есть результаты удаления, суммирования и добавления числа в (car l) и назовите эти newl, product и sum; тогда представьте, что у вас есть результаты от того, чтобы сделать то же самое до (cdr l), и назовите их dnewl, dproduct и dsum. К вашему ожиданию продолжите, дайте значения, полученные cons ing newl и dnewl(поскольку мы составляем список списков); умножение product и dproduct; и добавление sum и dsum.

Обратите внимание: каждый раз, когда мы делаем рекурсивный вызов, мы строим новое продолжение для рекурсивного вызова, которое "закрывает" текущие значения аргумента l и продолжения возврата - col, в других слова, вы можете думать о цепочке продолжений, которую мы создаем во время рекурсии, моделируя "стек вызовов" более условно написанной функции!

Надеюсь, что это часть ответа на ваш вопрос. Если я немного переусердствовал, это было только потому, что я думал, что после самой рекурсии продолжения являются второй по-настоящему опрятной, расширяющей сознание идеей в The Little Schemer и вообще в программировании.

Ответ 2

answer от Jon O. - это действительно большое углубленное объяснение базовых концепций. Хотя для меня (и, надеюсь, для некоторых других людей) понимание таких понятий намного проще, если у них есть визуальное представление.

Итак, я подготовил две блок-схемы (похожие на как только я сделал для multirember&co, распутывая то, что происходит во время вызова evens-only*&co

когда l:

'((9 1 2 8) 3 10 ((9 9) 7 6) 2) 

и col:

(define the-last-friend
    (lambda (newl product sum)
        (cons sum (cons product newl))
    )
)

Одна блок-схема, отражающая , как переменные относятся к различным этапам рекурсии: Вторая блок-схема, показывающая действительные значения , передаваемые:

Моя надежда заключается в том, что этот ответ станет достойным дополнением к объяснению Джона выше.

Ответ 3

Я читал "Как программировать программы" (felleisen et.al.). Я просматриваю раздел, где они определяют определения local. Я написал код, который реализует вышеупомянутые evens-only & co, используя локальное определение. Вот что я написал:

(define (evens-only&co l)
  (local ((define (processing-func sum prod evlst lst)
            (cond ((null? lst) (cons sum (cons prod evlst)))
                  ((atom? (car lst))
                   (cond ((even? (car lst)) (processing-func sum (* prod (car lst)) (append evlst (list (car lst))) (cdr lst)))
                         (else
                          (processing-func (+ sum (car lst)) prod evlst (cdr lst)))))
                  (else
                   (local ((define inner-lst (processing-func sum prod  '() (car lst))))
                   (processing-func (car inner-lst) (cadr inner-lst) (append evlst (list (cddr inner-lst))) (cdr lst)))))))
    (processing-func 0 1 '() l)))

Для тестирования, когда я ввожу (только evens-only & co '((9 1 2 8) 3 10 ((9 9) 7 6) 2)), он возвращает' (38 1920 (2 8) 10 (( ) 6) 2) как ожидалось в маленьком интригане. Но мой код не срабатывает при одном условии: когда нет четных чисел, произведение эвенов по-прежнему отображается как 1. Например (evens-only & co '((9 1) 3 ((9 9) 7) )) возвращает '(38 1() (())). Думаю, мне понадобится дополнительная функция, чтобы исправить это. @melwasul: Если вы не знакомы с локальным определением, извините за сообщение здесь. Я предлагаю вам также прочитать HTDP. Это отличная книга для новичков. Но ребята, которые являются экспертами по схеме, могут поместить свои комментарии и на мой код. Является ли мое понимание локального определения правильным?

Ответ 4

В эквациональном псевдокоде (a примечание KRC, написание f x y для вызова (f x y), где оно однозначно), это

evens-only*&co l col 
   = col [] 1 0                                     , IF null? l
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col (cons (car l) newl)
                            (opx (car l) product)
                            sum )                   , IF atom? (car l) && even? (car l)
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col  newl  product  (op+ (car l) sum) )      , IF atom? (car l)
   = evens-only*&co (car l) 
                    ( anewl aproduct asum =>
                         evens-only*&co (cdr l)
                                        ( dnewl dproduct dsum =>
                                             col (cons anewl    dnewl)
                                                 (opx  aproduct dproduct)
                                                 (op+  asum     dsum) ) )   , OTHERWISE

Это CPS, который собирает все эвенки из входного вложенного списка (то есть дерева), сохраняя при этом древовидную структуру, а также находит продукт всех эвенов; как для неэвенов, он суммирует их:

• если l - пустой список, три основных значения (идентификатора) передаются как аргументы col;

• если (car l) является четным числом, результаты обработки (cdr l) равны newl, product и sum, а затем они передаются как аргументы col, а первые два увеличены путем consing & Frasl; умножение на (car l) (четное число);

• если (car l) - это атом, который не является четным числом, результаты обработки (cdr l) равны newl, product и sum, а затем они передаются как аргументы col с третьим, дополненным суммированием с помощью (car l) (атома нечетного числа);

• если (car l) - это список, результаты обработки (car l) равны anewl, aproduct и asum, а затем результаты обработки (cdr l) равны dnewl, dproduct и dsum, а затем три комбинированных результата передаются как аргументы col.

[], 1 и 0 базового случая являются элементами тождества моноидов списков, номера под умножение и числа при добавлении соответственно. Это означает только специальные значения, которые не меняют результат, когда они объединены в него.

В качестве иллюстрации, для '((5) 2 3 4) (что близко к примеру в вопросе), оно создает расчет

evens-only*&co [[5], 2, 3, 4] col
=
col  (cons []                   ; original structure w only the evens kept in,
           (cons 2              ;   for the car and the cdr parts
              (cons 4 [])))
     (opx 1                     ; multiply the products of evens in the car and 
          (opx 2 (opx 4 1)))    ;   in the cdr parts
     (op+ (op+ 5 0)             ; sum, for the non-evens
          (op+ 3 0))     

Подобно моему другому ответу (к вопросу о сестре), вот еще один способ написать это, с псевдокодом, совместимым с patter (с защитой):

evens-only*&co  =  g   where
  g [a, ...xs...] col 
         | pair? a    = g a  ( la pa sa =>
                         g xs ( ld pd sd =>
                                        col [la, ...ld...] (* pa pd) (+ sa sd) ) )
         | even? a    = g xs ( l p s => col [ a, ...l... ] (* a  p )       s     )
         | otherwise  = g xs ( l p s => col         l            p   (+ a  s )   )
  g []            col =                 col []              1         0

Экономика (и разнообразие) этой нотации действительно делает ее намного понятнее, проще просто увидеть, а не потеряться в слове салат длинных имен для функций и переменных, так как парны перегружены как синтаксические разделители для данных списка, (например, в выражениях cond), привязки имен (в выражениях lambda) и указатели функций, которые выглядят точно так же. Такая же однородность обозначений S-выражений, которые облегчают манипулирование машиной (т.е. lisp read и макросы), является тем, что вредно для его читаемости.