Рекурсия

[lomeo]

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

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

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

Comments

[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 -- директория. Нужно написать функцию, которая применит функцию компиляции к каждому исходному файлу, причём в правильном порядке, с учётом что от чего зависит.

Для данного примера порядок может быть таким: f1, f2, f4, f5, f3, f6, f0, f7.

В идеале ещё бы обнаружить циклические зависимости.

Как это сделать двойной рекурсией -- очевидно, а вот комбинаторного решения я придумать не могу.

[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 #-}

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"])Похоже на правду.

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

[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). я написал алгоритм из википедии внизу.