Рекурсия

[lomeo]

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

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

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

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

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

Comments

[some41.livejournal.com]

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

[thesz.livejournal.com]

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

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

Поправите?

[some41.livejournal.com]

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

[thesz.livejournal.com]

Спасибо!

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

[some41.livejournal.com]

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