Рекурсия

[lomeo]

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

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

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

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

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

Comments

[thesz.livejournal.com]

Вот кусочек:

{-# 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.livejournal.com]

testC = Component [f0, f7] [m1]

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

[thesz.livejournal.com]

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

[voidex.livejournal.com]

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

[swizard.livejournal.com]

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

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

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

[thesz.livejournal.com]

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

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

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

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

[rigidus.livejournal.com]

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