Recycled Bin

для красивых комбинаторных решений часто приходится напрячься и переосмыслить задачу в более общих терминах, чтобы то, что мы хотим было частным случаем какой-то общей операции, может над чуть более общей структурой данных.
но для того, чтобы избежать явной рекурсии это не обязательно. например, в данном случае берем рекурсивный алгоритм из википедии (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