Рекурсия и итерация.

[mibori]

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

foldl f v xs = foldr (λx g →(λa → g (f a x))) id xs v
Давайте рассмотрим подробнее определения функций foldl и foldr.

foldr f v [] = v
foldr f

Comments

[inv2004]

спасибо, всё так чётко расписано, что для себя я тоже закрою эту тему.

[mibori]

Кстати, _darkus_ перевел док, на русский.

А еще надо прокачать этот скилл.

[lomeo]

_darkus_ также перевел статью о катаморфизме[WIKI] на русский[WIKI].

[mibori]

О, спасибо. А слона то я и не приметил :)

[lomeo]

Оператор свёртки написать можно для любого алгебраического типа данных, а значит можно написать универсальный (generic).

[nealar]

В Epigram называется "eliminator" - штука, которая каноническим способом уничтожает тип данных. Для списка - fold, для дерева - какой-то деревянный fold, для натурального - матиндукция, для Bool - ifthenelse.

[lomeo]

интересно, спасибо! я вообще на эпиграм давно хочу поглядеть :-)