Рекурсия

[lomeo]

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

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

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

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

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

Comments

[swizard.livejournal.com]

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



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

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

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

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

[thesz.livejournal.com]

Scrap your boilerplate.

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

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

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

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

[swizard.livejournal.com]

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

[swizard.livejournal.com]

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

[thesz.livejournal.com]

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

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

sortDeps = sortBy compareTopo filesDeps

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

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

[swizard.livejournal.com]

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

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

[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 в вашем примере?

[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 пока не понимаю

[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]

Что-то мне вспомнилось, что у Луговского, что ли, была либа на Лиспе а-ля SYB. Для работы с языками и их трансляцией.

Он на ней деньги собирался зарабатывать. ;)

[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.

[lomeo.livejournal.com]

Тип содрал у voidex, решение простое: использовать графы и uniplate для выдёргивания всего (аналог listify у thesz). Циклы не проверял.

http://hpaste.org/78589 (http://hpaste.org/78589)

[nponeccop.livejournal.com]

Теперь осталось только на data types a la carte переделать, завтра попробую, если не опередят. А топсорт - это читерство.

[nponeccop.livejournal.com]

Вот держите обещанную переделку на а ля карт:

http://hpaste.org/78604

Data.Functor.Fixedpoint находится в unification-fd, импорт можно заменить на ровно две строчки:

newtype Fix f = Fix { unFix :: f (Fix f) }
cata phi = phi . fmap self . unFix

[lomeo.livejournal.com]

Красиво.

[some41.livejournal.com]

для красивых комбинаторных решений часто приходится напрячься и переосмыслить задачу в более общих терминах, чтобы то, что мы хотим было частным случаем какой-то общей операции, может над чуть более общей структурой данных.
но для того, чтобы избежать явной рекурсии это не обязательно. например, в данном случае берем рекурсивный алгоритм из википедии (http://en.wikipedia.org/wiki/Topological_sort, второй) и пишем его в лоб: http://hpaste.org/78601
основная функция получилась так:

topsort cm = fst $ foldr visit ([],S.empty) roots
    where roots = M.elems $ cm `diff` allDepends cm
	  visit n (rs,seen) = if name n `S.member` seen then (rs,seen)
	                      else (rs' ++ [n],seen')
			          where (rs',seen') = foldr visit (rs,S.insert (name n) seen) (deps n)
	  deps File{ dependsOn=ds }    = find ds
	  deps Module{ components=cs } = cs
	  find = map (\name -> fromJust $ M.lookup name cm)

Код сурово императивный, что видно по foldr, но хотя бы нет явной структурной рекурсии.
Как известно, вместо рекурсии можно использовать цикл с очередью (http://hpaste.org/78602):

topsort cm = res
    where roots = M.elems $ cm `diff` allDepends cm
	  visit n (qs,rs,seen) = if name n `S.member` seen then (qs,rs,seen)
	                         else (qs ++ deps n, n:rs, S.insert (name n) seen)
	  deps File{ dependsOn=ds }    = find ds
	  deps Module{ components=cs } = cs
	  find = map (\name -> fromJust $ M.lookup name cm)
	  next (qs,rs,seen) = foldr visit ([],rs,seen) qs
	  (_,res,_) = until (\(qs,_,_) -> null qs) next (roots,[],S.empty)

Код по-прежнему императивный, но явной рекурсии больше нет. Она спрятана в until и foldr.

Если все немного обобщить (разрешить зависимости и на уровне модулей, чтобы структура была более симметричная) и причесать, то можно избавиться от рекурсии и во flatten, перенеся ее в общий комбинатор foldTree: http://hpaste.org/78603