Рекурсия

[lomeo]

Я это как-то писал, но напишу ещё раз, бо тема поднялась.

Недостатки явной рекурсии по сравнению с комбинаторами (ага, zip3):

• Рекурсия непонятна (согласен, это субъективное).
• Обычно используется с декомпозицией, нарушая инкапусляцию.
• Всегда используется для работы с элементами, вместо работы с коллекцией ( wholemeal programming).
• Цепочка вызовов

Comments

[swizard]

А можно вот такой теоретический вопрос: как предлагается заменять, например, двойную (или более широкую) рекурсию комбинаторами?

[some41]

для красивых комбинаторных решений часто приходится напрячься и переосмыслить задачу в более общих терминах, чтобы то, что мы хотим было частным случаем какой-то общей операции, может над чуть более общей структурой данных.
но для того, чтобы избежать явной рекурсии это не обязательно. например, в данном случае берем рекурсивный алгоритм из википедии (http://en.wikipedia.org/wiki/Topological_sort, второй) и пишем его в лоб: http://hpaste.org/78601
основная функция получилась так:

topsort cm = fst $ foldr visit ([],S.empty) roots
where roots = M.elems $ cm `diff` allDepends cm
visit n (rs,seen) = if name n `S.member` seen then (rs,seen)
else (rs' ++ [n],seen')
where (rs',seen') = foldr visit (rs,S.insert (name n) seen) (deps n)
deps File{ dependsOn=ds } = find ds
deps Module{ components=cs } = cs
find = map (\name -> fromJust $ M.lookup name cm)Код