Решение упражнения 2.20 из SICP

26 January, 2008 (19:29) | Решения упражнений

Довольно интересное упражнение с учетом того, что пока мы не рассматривали вопросы обобщенного отображения и фильтрации списков (очевидно, нас подводят к этим важным понятиям).

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

(define (same-parity first-value . other-values)
  (define (accept-parity? value)
    (equal? (even? first-value) (even? value)))
  (define (filter-parity values)
    (cond ((null? values) null)
          ((accept-parity? (car values)) (cons (car values)
                                               (filter-parity (cdr values))))
          (else (filter-parity (cdr values)))))
  (cons first-value (filter-parity other-values)))

Проверку того, совпадает ли четность первого значения и некоторого другого значения можно записать несколько короче, воспользовавшись тем, что сумма чисел одинаковой четности четна, а сумма чисел разной четности нечетна:

(define (accept-parity? value)
  (even? (+ first-value value)))

Будет ли этот способ записи более эффективным, сказать сложно.

Comments

Comment from thror
Date: February 8, 2008, 2:19 pm

Здесь на самом деле появляется очень интересная абстракция, фильтрация списка, которую можно выразить более общей идееей вот так (в рекурсивном, и итеративном виде):

(define (filter-list filter items)
  (cond ((null? items) '())
        ((filter (car items)) (cons (car items) (filter-list filter (cdr items))))
        (else (filter-list filter (cdr items)))))

Обратите внимание на этот вид рекурсии, о котором вы вообще не упоминаете, так называемая continuation-passing recursion, представляющая собой очень важный момент для изучения течения процессов. Подробнее о том, что это, и как работает, и почему полезно, можно почитать здесь MIT AI Memo 353–LAMBDA: The Ultimate Imperative.

(define (filter-list filter items c)
  (cond ((null? items) (c '()))
        ((filter (car items)) (filter-list filter
                                           (cdr items)
                                           (lambda (a) (c (cons (car items) a)))))
        (else (filter-list filter
                           (cdr items)
                           (lambda (a) (c a))))))

[ Вообще, вот определение факториала в том же стиле, оно более понятно:

(define (factorial n c)
  (if (= n 0)
      (c 1)
      (factorial (- n 1) (lambda (a) (c (* n a))))))

Вообще можно дополнить уражнения подобными определениями, просто для полноты. Странно что авторы даже не упоминают о таком виде рекурсии.]

(define (filter-list filter items)
  (define (iter l r)
    (cond ((null? r) l)
          ((filter (car r)) (iter (append l (list (car r))) (cdr r)))
          (else (iter l (cdr r)))))
  (iter '() items))

(define (same-parity n . w)
  (cons n (filter-list (lambda (x) (even? (+ n x))) w)))


--thror

Comment from Sergey Khenkin
Date: February 8, 2008, 3:19 pm

Совершенно верно.
В разделе 2.2.3, который идет в книге после упражнения 2.20, вводится обобщенная процедура фильтрации filter, аналогичная приведенной вами filter-list с двумя аргументами. Имея эту процедуру в арсенале, действительно можно записать same-parity как 

(define (same-parity first-value . other-values)
  (cons first-value
        (filter (lambda (value) (even? (+ first-value value)))
                other-values)))

Очень хорошее замечание.
Я старался не забегать вперед и не пользоваться еще не рассмотренными концепциями при решении упражнений.

Что касается continuation-passing recursion, то из приведенных примеров можно понять, как такая рекурсия работает, но неясен практический выигрыш от ее использовния.

Comment from thror
Date: February 8, 2008, 7:17 pm

На самом деле подобный вид рекурсии подводит нас вплотную к одной из важнейших концепций функционального программирования–Continuation Passing Style (CPS).

Число работ по данной теме очень велико, и найти их не трудно. Вот к примеру из классических Lambda-papers: MIT AITR 474–Rabbit: A Compiler for Scheme.

–thror

Comment from Sergey Khenkin
Date: February 9, 2008, 12:43 am

В английской Википедии есть неплохая вводная информация по Continuation Passing Style. Все же это слишком фундаментальная вещь для того, чтобы рассматривать ее серьезно на этом этапе. Как я понимаю, практически она используется при построении компиляторов. Подозреваю, что с continuations мы еще встретимся в четвертой главе книги.

Comment from thror
Date: February 11, 2008, 4:29 pm

Все же, если кто-нибудь окажется заинтересован в изучении этого интересного явления–CPS, то начать можно с классических статей отсюда http://library.readscheme.org/page6.html

–thror

Comment from JessicaFletcher
Date: March 7, 2009, 3:35 pm

еще простое решение -
(define (some-parity i . list)
(cons i (
(cond (= (cdr list) nill) nill)
(= (average i 2) (average (car list) 2)
(cons (car list) (some-parity (cdr list)))
(some-parity (cdr list))))))

Write a comment