Рекурсия

[lomeo]

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

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

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

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

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

Comments

[voidex.livejournal.com]

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

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

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

Update

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

[nivanych.livejournal.com]

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

[swizard.livejournal.com]

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

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

[some41.livejournal.com]

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