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

27 January, 2008 (13:16) | Решения упражнений

Рассмотрим первую попытку Хьюго реализовать square-list:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

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

Вторая попытка Хьюго весьма показательна как иллюстрация алгоритма “попытка – не пытка” (когда мы получаем результат, близкий к искомому, но не тот, который требуется, точно не знаем, в чем именно проблема, и просто пытаемся немного перегруппировать части программы для получения нужного результата).

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

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

Правильным же решением задачи будет использование процедуры append для соединения списка результатов с очередным полученным квадратом значения:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (append answer
                      (list (square (car things)))))))
  (iter items nil))

Поскольку append работает со списками, мы используем list, превращая число (square (car things)) в список из одного элемента.

Comments

Comment from Sergey Khenkin
Date: January 27, 2008, 1:36 pm

Очень хорошие иллюстрации соединения списков с помощью операции cons можно посмотреть у Эли Бендерски внизу страницы.

Comment from Irv
Date: January 29, 2016, 3:00 pm

не лучше ли просто перевернуть результирующий список (за O(n)/O(1)) вместо того, что бы на каждом шаге использовать append (O(n)/O(n2)?
(if (null? things) (reverse answer)

Write a comment