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

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

Результаты, получаемые каждой из функций свертки, приведены ниже. Сначала я показываю ответ, а затем ход его построения для наглядности:

(fold-right / 1 (list 1 2 3))

(/ 1 (/ 2 (/ 3 1)))

(fold-left / 1 (list 1 2 3))
1/6
(/ (/ (/ 1 1) 2) 3)

(fold-right list nil (list 1 2 3))
(1 (2 (3 ())))
(list 1 (list 2 (list 3 nil)))

(fold-left list nil (list 1 2 3))
(((() 1) 2) 3)
(list (list (list nil 1) 2) 3)
 

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

Правая свертка вычисляет для последовательности (a1 a2 … an) и начального элемента i такое выражение:

(a1 op (a2 op … (an op i) …)).

Левая свертка вычисляет для них же такое выражение:

(… ((i op a1) op a2 ) … op an).

Если мы можем выдвигать требования только к самой операции op, то для эквивалентности приведенных выражений (а значит и эквивалентности результатов правой и левой сверток) будет достаточно того, чтобы op была коммутативна и ассоциативна, то есть для любых a, b и c выполнялись тождества:

  1. a op b ≡ b op a
  2. a op (b op c) ≡ (a op b) op c

Подчеркиваю, что одного лишь свойства коммутативности операции op (такой ответ приводится в некоторых источниках) недостаточно! Свойства ассоциативности на практике часто бывает достаточно, но лишь при условии удачно выбранного начального элемента i. От него требуется быть так называемой единицей группы относительно op, то есть удовлетворять тождествам:

  1. i op a ≡ a
  2. a op i ≡ a

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

Приведенные в упражнении операции / и list, очевидно, не являются ни коммутативными, ни ассоциативными, потому правая и левая свертки для них дают совершенно разные результаты.

Comments

Comment from Sergey Khenkin
Date: January 31, 2008, 8:50 pm

Примером коммутативной, но не ассоциативной бинарной операции является модуль разности двух чисел. Легко показать, что левая и правая свертки с этой операцией не будут давать одинаковых результатов.
Это пример для опровержения достаточности одной только коммутативности op.

Comment from thror
Date: February 19, 2008, 10:35 am

Сергей, немного исправлю вас. Итак, как правильно замечено, ассоциативность операции необходима. Но вот с коммутативностью вы перебрали. От операции не требуется коммутативности и не требуется чтоб начальный элемент был единицей. И того и другого слишком много. Правильнее сказать так-начальный элемент должен коммутировать со всеми остальными (ну и ассоциативность естественно). Конечно если операция коммутативна это будет так. И если начальный элемент единица то это тоже выполнится. Но это все более сильные условия чем нам необходимо. –трор

Comment from Sergey Khenkin
Date: February 19, 2008, 10:58 am

Я писал о коммутативности только в контексте требований исключительно к операции op (а не к операции и начальному элементу). Так сформулировано условие упражнения.

“Если мы можем выдвигать требования только к самой операции op, то для эквивалентности приведенных выражений (а значит и эквивалентности результатов правой и левой сверток) будет достаточно того, чтобы op была коммутативна и ассоциативна…”

Что же касается единицы (о ней я писал для случая, когда можно выдвигать требования и к начальному элементу тоже), то тут полностью согласен. Перебрал. Достаточно, чтобы начальный элемент коммутировал с остальными, то есть i op a = a op i для всех a.

Write a comment