lomeo: (лямбда)
Dmitry Antonyuk ([personal profile] lomeo) wrote2012-11-30 05:48 pm

Рекурсия

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

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

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

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

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

[identity profile] inv2004.livejournal.com 2012-11-30 01:53 pm (UTC)(link)
Могу только поддержать.

[identity profile] nealar.livejournal.com 2012-11-30 01:56 pm (UTC)(link)
Когда сложность кода - уровня хелловорда, рекурсия понятна. А когда его становится побольше, уже надо спасаться комбинаторами.

[identity profile] lomeo.livejournal.com 2012-11-30 02:27 pm (UTC)(link)
Я стараюсь использовать её для реализации комбинаторов. Ну, т.е. вот есть модуль с объявленным типом, сначала, конечно typeclass morphism, потом более конкретные функции для этого типа. И вот всё это можно и через рекурсию. А наружу уходят чистые комбинаторы.

[identity profile] thedeemon.livejournal.com 2012-11-30 03:45 pm (UTC)(link)
>сначала, конечно typeclass morphism

Вот об этом было бы интересно подробнее послушать.

[identity profile] lomeo.livejournal.com 2012-11-30 03:58 pm (UTC)(link)
Да собственно тут (http://conal.net/papers/type-class-morphisms/) всё сказано.

Зачем нам алгебраические структуры в самом деле? Чтобы их использовать! :-)

Ну, и в нагрузку ещё немножко про дизайн (http://lukepalmer.wordpress.com/2008/07/18/semantic-design/) от Люка Палмера (правда, это оффтопик).

[identity profile] thedeemon.livejournal.com 2012-11-30 04:07 pm (UTC)(link)
Первое я видел, но хотелось бы примеров из личной практики.

[identity profile] miserakl.livejournal.com 2012-11-30 04:48 pm (UTC)(link)
> Ну и ссылочка, куда без неё!

Кажется, ссылка потерялась, и ЖЖ вместо неё подставил адрес текущей страницы.

[identity profile] lomeo.livejournal.com 2012-11-30 05:18 pm (UTC)(link)
Да ничего особенного. Абстракции как приём программирования :-)

Пишем же мы монады для ограничения контекста, для задания собственного подъязычка, мало ли для чего. При этом мы отслеживаем семантику, проверяем выполняются ли законы.

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

ZipList, например. Структура та же, что и у списка, а семантика другая. Она отражена в реализации instance Applicative. Однако он неполноценный — это просто представление (view) списка. Если мы захотим работать с ним, как и с нормальным типом, добавить свёртку, например, то нам придётся это реализовывать. Так вот я стараюсь сразу делать это в Foldable, к примеру.

Ну и со всеми типами так. Пишешь монаду для работы с БД, например, или с пользовательскими сессиями, не забудь реализовать Functor, Applicative, если надо MonadPlus. Код получается более generic.

Напишешь какую-то функцию, смотришь, а это <|> из Alternative. Ну и чего сразу этот класс не реализовать и получить бесплатно другие функции с проверенными свойствами. Если твой код удовлетворяет законам класса, разумеется.

Как-то так. Несложное правило, позволяющее не писать кучу кода и рассуждать одинаково в кажущихся различными ситуациях.

[identity profile] lomeo.livejournal.com 2012-11-30 05:20 pm (UTC)(link)
:-) Явная рекурсия - зло.

[identity profile] thedeemon.livejournal.com 2012-11-30 05:42 pm (UTC)(link)
спасибо!

[identity profile] miserakl.livejournal.com 2012-11-30 06:45 pm (UTC)(link)
А, так это специально. Небось до вечера пятницы тоже нарочно откладывали? :)

[identity profile] nealar.livejournal.com 2012-11-30 07:06 pm (UTC)(link)
Отложенные вычисления :)

[identity profile] lomeo.livejournal.com 2012-11-30 07:14 pm (UTC)(link)
Нет, так вышло ;-)

И можно на ты.

[identity profile] nivanych.livejournal.com 2012-11-30 08:03 pm (UTC)(link)
Можно ещё такой довод.
Структурная рекурсия, это один простой паттерн, легко укладывающийся в довольно простой Тьюринг-худой язык.
А значит, имеем простой и предсказуемый reasoning.
Что вполне подтверждается на практике.
Общая рекурсия заставляет думать в рамках уже Тьюринг-полноты, что в общем случае, неразрешимо даже теоретически, а не то, чтобы уложилось человеку в голову.
Конечно же, при реальном программировании, возникает ряд "паттернов" (навроде отслеживания разборки значения индуктивного типа), иначе бы было очень сложно сделать что-то.
Ну вот, структурная рекурсия, это один из таких паттернов — простой, чОтко формализованный и весьма общий.

[identity profile] swizard.livejournal.com 2012-11-30 08:39 pm (UTC)(link)
А можно вот такой теоретический вопрос: как предлагается заменять, например, двойную (или более широкую) рекурсию комбинаторами?

[identity profile] lomeo.livejournal.com 2012-11-30 08:55 pm (UTC)(link)
Один раз реализовать свёртку полезно для типа ;-) Хотя сейчас уже deriving Foldable есть.

[identity profile] lomeo.livejournal.com 2012-11-30 09:05 pm (UTC)(link)
1. "Избегайте" /= "Никогда не используйте".
2. Этот пост возник из-за этой дискуссии (http://levgem.livejournal.com/420910.html?thread=5124654#t5124654). Т.е. "как заменить" уже есть.

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

[identity profile] thesz.livejournal.com 2012-11-30 09:31 pm (UTC)(link)
А что это такое?

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

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

[identity profile] swizard.livejournal.com 2012-11-30 09:53 pm (UTC)(link)
Ну, я могу навскидку привести вот такую задачу: есть схема проекта в виде дерева зависимостей, вот в таком виде:



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

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

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

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

[identity profile] swizard.livejournal.com 2012-11-30 09:54 pm (UTC)(link)
Понятно, спасибо.

[identity profile] thesz.livejournal.com 2012-11-30 10:09 pm (UTC)(link)
Scrap your boilerplate.

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

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

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

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

[identity profile] swizard.livejournal.com 2012-11-30 10:27 pm (UTC)(link)
Погоди, я не очень понял: вот у меня в одной руке есть все файлы из дерева, а во второй все зависимости. А как мне теперь в правильном порядке обойти файлы через (map compile)? А как сломаться, если в зависимостях есть цикл?

[identity profile] swizard.livejournal.com 2012-11-30 10:28 pm (UTC)(link)
Если тебе не сложно, напиши, пожалуйста, пример. Схему проекта можно отобразить в аналогичную на типах хаскеля, я пойму.

[identity profile] thesz.livejournal.com 2012-11-30 10:42 pm (UTC)(link)
Топологическая сортировка, типа того.

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

sortDeps = sortBy compareTopo filesDeps

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

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

[identity profile] swizard.livejournal.com 2012-11-30 10:59 pm (UTC)(link)
Вроде понял, спасибо, это должно сработать.

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

Page 1 of 3