Рекурсия

[lomeo]

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

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

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

Comments

[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)
Код сурово императивный, что видно по foldr, но хотя бы нет явной структурной рекурсии.
Как известно, вместо рекурсии можно использовать цикл с очередью (http://hpaste.org/78602):

topsort cm = res
where roots = M.elems $ cm `diff` allDepends cm
visit n (qs,rs,seen) = if name n `S.member` seen then (qs,rs,seen)
else (qs ++ deps n, n:rs, S.insert (name n) seen)
deps File{ dependsOn=ds } = find ds
deps Module{ components=cs } = cs
find = map (\name -> fromJust $ M.lookup name cm)
next (qs,rs,seen) = foldr visit ([],rs,seen) qs
(_,res,_) = until (\(qs,_,_) -> null qs) next (roots,[],S.empty)
Код по-прежнему императивный, но явной рекурсии больше нет. Она спрятана в until и foldr.

Если все немного обобщить (разрешить зависимости и на уровне модулей, чтобы структура была более симметричная) и причесать, то можно избавиться от рекурсии и во flatten, перенеся ее в общий комбинатор foldTree: http://hpaste.org/78603