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

30 January, 2008 (20:41) | Решения упражнений

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

Чтобы оперделить map через accumulate, начнем накопление с пустого списка и будем на этапе аккумулирования соединять с помощью cons результат применения отображающей процедуры с остальными результатами:

(define (map p sequence) 
    (accumulate (lambda (x y) (cons (p x) y)) nil sequence))

Для реализации append мы просто начнем со второго списка и на каждом шаге будем добавлять первый элемент остатка первого списка к результату накопления для остатка первого списка без этого элемента. Сложно выразить словами, выглядит это так:

(define (append seq1 seq2) 
    (accumulate cons seq2 seq1))

Для подсчета числа элементов последовательности начнем с нуля и будем просто на каждом шаге прибавлять 1 к накопленному до этого шага результату:

(define (length sequence) 
    (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

Таким образом из accumulate можно построить многие другие процедуры.

Comments

Comment from Максим
Date: November 29, 2014, 11:58 pm

Хитрая задача с длиной последовательности.
Долго мучился с подпроцедурой-счётчиком (что вообще, как оказалось, не имеет смысла, поскольку каждый очередной рекурсивный вызов accumulate “сбрасывает” его, так как мы не можем повлиять на формальные параметры accumulate, вызывается он каждый раз начиная с 0).

А куда деваются в случае с длиной последовательности все накопленные (car sequence)?
Ведь в исходном коде у нас:

...
(op (car sequence)
(accumulate ... (cdr sequence)))

Comment from oleg
Date: December 7, 2014, 10:16 am

Максим – игнорируются. Т. к. в исходном коде (op (car sequence) (accumulate … (cdr sequence))) это функция, определенная нами так: (lambda (x y) (+ 1 y)), где x – (car sequence), y – (accumulate … (cdr sequence)). Все очень просто.

Comment from Sergk
Date: February 24, 2015, 12:05 pm

начнем накопление с пустого списка

,

начнем с нуля

, не совсем понимаю почему назвали эту переменную начальной (initial), вроде это элемент “захлапывания”

Write a comment