Рекурсия

[lomeo]

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

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

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

Comments

[swizard]

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

[rigidus]

Черт побери, мне не очевидно.
Реквестирую решение на лиспе, т.к. haskell пока не понимаю

[some41]

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

[thesz]

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

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

Поправите?

[some41]

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

[thesz]

Спасибо!

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

[some41]

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

[thesz]

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

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

[voidex]

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

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

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

Update

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

[nivanych]

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

[swizard]

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

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

[some41]

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

[lomeo]

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

http://hpaste.org/78589

[nponeccop]

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

[nponeccop]

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

http://hpaste.org/78604

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

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

[lomeo]

Красиво.