Рекурсия

[lomeo]

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

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

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

Юный хаскеллист, избегай явной рекурсии!

Ну и ссылочка, куда без неё!

Comments

[thesz.livejournal.com]

Вот кусочек:

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Data
import Data.Generics (listify)
import Data.List (nub, sortBy)
import Data.Maybe

data File = File String [Either File Module]
        deriving (Data, Typeable, Eq, Ord, Show)
data Module = Module String Component
        deriving (Data, Typeable, Eq, Ord, Show)
data Component = Component [File] [Module]
        deriving (Data, Typeable, Eq, Ord, Show)

f0 = File "f0" []
f1 = File "f1" []
f2 = File "f2" [Left f1]
f3 = File "f3" [Left f4, Left f5]
f4 = File "f4" []
f5 = File "f5" []
f6 = File "f6" [Right m3, Right m2]
f7 = File "f7" [Right m1, Left f0]
m1 = Module "m1" $ Component [f6] [m2, m3]
m2 = Module "m2" $ Component [f1, f2] []
m3 = Module "m3" $ Component [f3, f4, f5] []

testC = Component [f0, f7] [m1, m2, m3]

files :: [File]
files = nub $ listify (const True) testC

filesDeps :: [(String,[String])]
filesDeps = map (\(File n deps) -> (n, nub $ map fn $ listify (const True) deps)) files
        where
                fn (File n _) = n

compareDeps :: (String, [String]) -> (String, [String]) -> Ordering
compareDeps (fa, da) (fb, db)
        | fa `elem` db && fb `elem` da = error "cycle"
        | fa `elem` db = LT
        | otherwise = GT

sortedDeps = sortBy compareDeps filesDeps

Вот как-то так.

Выхлоп:

*Main> mapM_ print sortedDeps
("f1",[])
("f2",["f1"])
("f5",[])
("f4",[])
("f3",["f4","f5"])
("f6",["f3","f4","f5","f1","f2"])
("f0",[])
("f7",["f6","f3","f4","f5","f1","f2","f0"])

Похоже на правду.

[thesz.livejournal.com]

Что-то мне вспомнилось, что у Луговского, что ли, была либа на Лиспе а-ля SYB. Для работы с языками и их трансляцией.

Он на ней деньги собирался зарабатывать. ;)

[voidex.livejournal.com]

Ну придумать-то можно, вопрос в том, будет ли это понятнее, чем рекурсия в данном случае.
Идея такая:
1. Строим список пар (имя объекта, непосредственные зависимости). Для файла это зависимости, для модуля - имена компонентов.
2. Строим дерево зависимостей, т.е. разворачиваем непосредственные зависимости.
3. Сортируем очевидным образом (зависящий идёт позже, если независимы - по имени)
4. Вуаля

Код без учёта циклических зависимостей: http://hpaste.org/78574

Для учёта идея проста, мы храним "родителей" и смотрим, чтобы текущий от них не зависел: http://hpaste.org/78575

Update

Я был не прав в пункте 3, сортировать не нужно. Вот конечный результат: http://hpaste.org/78585

[voidex.livejournal.com]

testC = Component [f0, f7] [m1]

А на циклы проверяли? Что-то меня смущает проверка на циклы. По идее зависимости должны раскрываться, но они тут раскрываться будут бесконечно в случае цикла. Банально f0 = File "f0" [f0].

[some41.livejournal.com]

compareTopo не является ordering. например, для (a, []), (b, []), (c, [a]) получаем a == b, b == c, a < c. аналогично если возвращать GT (как ниже), то будет a > b, b > a.

[nivanych.livejournal.com]

> Зачем нам алгебраические структуры в самом деле?

Так, или с пользой? (c)

[nivanych.livejournal.com]

> полезно для типа

Ему от этого становится лучше, да! ;-)

[nivanych.livejournal.com]

Добавлю мыслей.
Индуктивные типы — это деревья. Графы делают из них и напрямую, без соответствующего вычислятельного контекста, индуктивными типами они не являются.
Тем не менее, для графов можно сделать соответствующие комбинаторы.
Первыми ну просто напрашиваются всякие преобразования в процессе обхода графа в ширину-глубину.
Ещё строят построение (ленивого) дерева обхода и что-то-там с ним дальше делают.

[thesz.livejournal.com]

С ошибками даже интересней.

У вас появляется шанс поправить и понять, что не так. ;)

Поправите?

[thesz.livejournal.com]

И что, действительно раскрываются бесконечно? Каков вывод ghci в вашем примере?

[swizard.livejournal.com]

Благодарю, теперь совсем ясно.

В принципе, всё очевидно: двойная рекурсия спрятана в двух вложенных через map listify, которые, в свою очередь (если я ничего не путаю), просто выполняют flatten дерева.

Тогда, если можно, встречный теоретический вопрос: а как правильно в хаскеле оценить производительность алгоритма, учитывая ленивость языка и автоматическую мемоизацию? Например, в императивном языке в таком решении достаточно паскудная сложность, и двойная рекурсия будет несравнимо оптимальней.

[lomeo.livejournal.com]

Тип содрал у voidex, решение простое: использовать графы и uniplate для выдёргивания всего (аналог listify у thesz). Циклы не проверял.

http://hpaste.org/78589 (http://hpaste.org/78589)

[swizard.livejournal.com]

Круто, спасибо.

Последнее решение я, правда, уже не особо понимаю, но это чисто из-за слабого знания содержимого стандартной библиотеки хаскеля.

[voidex.livejournal.com]

Ваш код я не проверял

[thesz.livejournal.com]

Сложность оценивается, как у императивного алгоритма с ленивыми вычислениями и мемоизацией. ;)

Я, на самом деле, не большой спец по SYB. Я пользуюсь им довольно редко, только когда уж совсем нудно становится. Кстати, есть более быстрая и удобная версия SYB, называется uniplate: http://community.haskell.org/~ndm/uniplate/

Мой пример слишком простой - берём всё файлы из структуры и просеиваем через nub, убирая повторы. То есть, мы можем напороться на циклы, это раз, и мы сделаем слишком много действий, это два.

Сам listify сделан через обобщённую свёртку - gfold. В этой свёртке накапливается список - все подэлементы некоторого значения тестируются на принадлежность к File, добавляются в список и по ним делается listify, результат которого снова добавляется к результату. Чуть изменив listify, передавая ему на вход уже обнаруженные элементы, мы можем избавиться от циклов и не делать лишней работы по повторному проходу уже известных элементов.

[miserakl.livejournal.com]

Энергичней было бы вставить html-фрейм с этим самым постом, видимо.

[lomeo.livejournal.com]

:-) Я бы на такое никогда не решился.

[nponeccop.livejournal.com]

Теперь осталось только на data types a la carte переделать, завтра попробую, если не опередят. А топсорт - это читерство.

[some41.livejournal.com]

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

[some41.livejournal.com]

у решений с сортировкой совсем не такая сложность, как должна быть у topological sort.

[some41.livejournal.com]

voidex уже написал правильную функцию сравнения, но делать topological sort через сортировку как-то дико. вместо O(V+E) получается O(logV*V*V). я написал алгоритм из википедии внизу.

[nponeccop.livejournal.com]

Вот держите обещанную переделку на а ля карт:

http://hpaste.org/78604

Data.Functor.Fixedpoint находится в unification-fd, импорт можно заменить на ровно две строчки:

newtype Fix f = Fix { unFix :: f (Fix f) }
cata phi = phi . fmap self . unFix

[thesz.livejournal.com]

Спасибо!

Я, откровенно говоря, не помнил алгоритма топологической сортировки.

[some41.livejournal.com]

да там особенно нечего помнить -- он очевиден, никакой хитрости в нем нет. и если честно, то у меня тоже неправильная сложность из-за lookups в Map и Set. но, думаю, все равно лучше, чем с поисками в полностью развернутом графе.

[lomeo.livejournal.com]

Красиво.