Рекурсия и итерация.
Похоже, что спор в моей голове о том, может ли любой рекурсивный алгоритм быть преобразован в итеративный (циклический), у меня разрешился. Кажется точку ставит следующие отношение, которое я нашел здесь:
foldl f v xs = foldr (λx g →(λa → g (f a x))) id xs v
Давайте рассмотрим подробнее определения функций foldl и foldr.
foldr f v [] = v
foldr f v (x: xs) = f x (foldr f v xs)
foldl f v [] = v
foldl f v (x: xs) = foldl f (f v x) xs(или, для наглядности посмотрим на картинки правой и левой свертки)
Если, чтобы реализовать foldr в императивной семантике стек просто необходим, для хранения промежуточных результатов
foldr f v [1, 2, 3, 4, 5] = f 1 (f 2 (f 3 (f 4 (f 5 v)))),
то для foldl этого не нужно
foldl f v [1, 2, 3, 4, 5] = f (f (f (f (f v 1) 2) 3) 4) 5
foldl аккумулирует выходной результат во втором аргументе, и ее можно реализовать при помощи цикла.
Что же нам дает найденное равенство? А то, что foldr всегда можно преобразовать в foldl. Однако обратное преобразование выполняется не всегда. Именно поэтому циклический алгоритм всегда можно преобразовать в рекурсивный, но рекурсивный не всегда. Рекурсивный алгоритм равен циклическому только тогда, когда это равенство выполняется и в ту и в другую сторону...
Это значит, что не все рекурсивные алгоритмы могут быть оптимизированы в циклические, без явной эмуляции структуры так или иначе выполняющей функцию стека.
Хочется верить, что разработка алгоритмов, атоматически преобразующих правую свертку в левую, или доказывающих невозможность этого, является делом времени, хотя конечно катаморфизмы[WIKI] foldl и foldr существуют не только для структур данных типа список. А универсальных операторов свертки, я пока еще не находил. Вероятнее всего, если такие алгоритмы и будут, они будут строго привязаны к типу данных.
foldl f v xs = foldr (λx g →(λa → g (f a x))) id xs v
Давайте рассмотрим подробнее определения функций foldl и foldr.
foldr f v [] = v
foldr f v (x: xs) = f x (foldr f v xs)
foldl f v [] = v
foldl f v (x: xs) = foldl f (f v x) xs(или, для наглядности посмотрим на картинки правой и левой свертки)
Если, чтобы реализовать foldr в императивной семантике стек просто необходим, для хранения промежуточных результатов
foldr f v [1, 2, 3, 4, 5] = f 1 (f 2 (f 3 (f 4 (f 5 v)))),
то для foldl этого не нужно
foldl f v [1, 2, 3, 4, 5] = f (f (f (f (f v 1) 2) 3) 4) 5
foldl аккумулирует выходной результат во втором аргументе, и ее можно реализовать при помощи цикла.
Что же нам дает найденное равенство? А то, что foldr всегда можно преобразовать в foldl. Однако обратное преобразование выполняется не всегда. Именно поэтому циклический алгоритм всегда можно преобразовать в рекурсивный, но рекурсивный не всегда. Рекурсивный алгоритм равен циклическому только тогда, когда это равенство выполняется и в ту и в другую сторону...
Это значит, что не все рекурсивные алгоритмы могут быть оптимизированы в циклические, без явной эмуляции структуры так или иначе выполняющей функцию стека.
Хочется верить, что разработка алгоритмов, атоматически преобразующих правую свертку в левую, или доказывающих невозможность этого, является делом времени, хотя конечно катаморфизмы[WIKI] foldl и foldr существуют не только для структур данных типа список. А универсальных операторов свертки, я пока еще не находил. Вероятнее всего, если такие алгоритмы и будут, они будут строго привязаны к типу данных.