Рекурсия

[lomeo]

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

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

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

Comments

[swizard]

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

[lomeo]

1. "Избегайте" /= "Никогда не используйте".
2. Этот пост возник из-за этой дискуссии. Т.е. "как заменить" уже есть.

Не стоит заменять. Если нужно, скажем, делать разбор двух структур по условию, то я пишу рекурсивный код. Пример: merge двух сортированных списков.

[swizard]

Понятно, спасибо.

[thesz]

А что это такое?

В качестве возможного примера могу предложить Omega monad: http://hackage.haskell.org/package/control-monad-omega

Комбинатор рекурсивной обработки потенциально бесконечных списков с гарантированным перечислением всех элементов.

[swizard]

Ну, я могу навскидку привести вот такую задачу: есть схема проекта в виде дерева зависимостей, вот в таком виде:

(:components ((:file "f0")
(:module M1
:components ((:module M2
:components ((:file "f1")
(:file "f2" :depends-on ("f1"))))
(:module M3
:components ((:file "f3" :depends-on ("f4" "f5"))
(:file "f4")
(:file "f5")))
(:file "f6" :depends-on (M3 M2))))
(:file "f7" :depends-on (M1 "f0"))))

Где, грубо говоря, file -- это исходник, а module -- директория. Нужно написать функцию, которая применит функцию компиляции к каждому исходному файлу, причём в правильном порядке, с учётом что от чего зависит

[thesz]

Scrap your boilerplate.

http://www.haskell.org/haskellwiki/Scrap_your_boilerplate

(есть ещё более навороченные и/или удобные варианты, более поздние)

Например, одной строкой можно получить все файлы. Другой - все зависимости. Отображение (map compile) на файлы даст компиляцию и тп.

Наверное, это ближе всего к нужному тебе.

[swizard]

Погоди, я не очень понял: вот у меня в одной руке есть все файлы из дерева, а во второй все зависимости. А как мне теперь в правильном порядке обойти файлы через (map compile)? А как сломаться, если в зависимостях есть цикл?

[swizard]

Если тебе не сложно, напиши, пожалуйста, пример. Схему проекта можно отобразить в аналогичную на типах хаскеля, я пойму.

[thesz]

Топологическая сортировка, типа того.

Сортируем пары вида (файл, зависимость) вот таким сравнением:
compareTopo (fa,depsa) (fb,depsb)
| fa `elem` depsb && fb `elem` depsa = error "cycle!"
| fa `elem` depsb = LT
| otherwise = EQ

sortDeps = sortBy compareTopo filesDeps

Первыми должны оказаться файлы без зависимостей.

Не однострочник, но близко.

[swizard]

Вроде понял, спасибо, это должно сработать.

Единственное, не могу сообразить, как scrap your boilerplate позволит мне одной строкой собрать из дерева все зависимости всех файлов, но верю на слово, что такое возможно.

[thesz]

Вот кусочек:
{-# LANGUAGE DeriveDataTypeable

[voidex]

testC = Component [f0, f7] [m1]

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

[thesz]

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

[voidex]

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

[swizard]

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

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

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

[thesz]

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

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

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

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