![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
lomeoЯ это как-то писал, но напишу ещё раз, бо тема поднялась.
Недостатки явной рекурсии по сравнению с комбинаторами (ага, zip3):
Юный хаскеллист, избегай явной рекурсии!
Ну и ссылочка, куда без неё!
Недостатки явной рекурсии по сравнению с комбинаторами (ага, zip3):
- Рекурсия непонятна (согласен, это субъективное).
- Обычно используется с декомпозицией, нарушая инкапусляцию.
- Всегда используется для работы с элементами, вместо работы с коллекцией (wholemeal programming).
- Цепочка вызовов проще для оптимизации.
- Сложнее нежно мною любимый equational reasoning.
Юный хаскеллист, избегай явной рекурсии!
Ну и ссылочка, куда без неё!
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png){kind=small}
no subject
Date: 2012-11-30 01:53 pm (UTC)no subject
Date: 2012-11-30 01:56 pm (UTC)no subject
Date: 2012-11-30 02:27 pm (UTC)no subject
Date: 2012-11-30 03:45 pm (UTC)Вот об этом было бы интересно подробнее послушать.
no subject
Date: 2012-11-30 03:58 pm (UTC)Зачем нам алгебраические структуры в самом деле? Чтобы их использовать! :-)
Ну, и в нагрузку ещё немножко про дизайн (http://lukepalmer.wordpress.com/2008/07/18/semantic-design/) от Люка Палмера (правда, это оффтопик).
no subject
Date: 2012-11-30 04:07 pm (UTC)no subject
Date: 2012-11-30 04:48 pm (UTC)Кажется, ссылка потерялась, и ЖЖ вместо неё подставил адрес текущей страницы.
no subject
Date: 2012-11-30 05:18 pm (UTC)Пишем же мы монады для ограничения контекста, для задания собственного подъязычка, мало ли для чего. При этом мы отслеживаем семантику, проверяем выполняются ли законы.
Так вот нужно не забывать реализовывать другие стандартные классы вместо того, чтобы рисовать собственные функции. Точно так же как с монадами: не забывая о семантике и законах.
ZipList, например. Структура та же, что и у списка, а семантика другая. Она отражена в реализации instance Applicative. Однако он неполноценный — это просто представление (view) списка. Если мы захотим работать с ним, как и с нормальным типом, добавить свёртку, например, то нам придётся это реализовывать. Так вот я стараюсь сразу делать это в Foldable, к примеру.
Ну и со всеми типами так. Пишешь монаду для работы с БД, например, или с пользовательскими сессиями, не забудь реализовать Functor, Applicative, если надо MonadPlus. Код получается более generic.
Напишешь какую-то функцию, смотришь, а это <|> из Alternative. Ну и чего сразу этот класс не реализовать и получить бесплатно другие функции с проверенными свойствами. Если твой код удовлетворяет законам класса, разумеется.
Как-то так. Несложное правило, позволяющее не писать кучу кода и рассуждать одинаково в кажущихся различными ситуациях.
no subject
Date: 2012-11-30 05:20 pm (UTC)no subject
Date: 2012-11-30 05:42 pm (UTC)no subject
Date: 2012-11-30 06:45 pm (UTC)no subject
Date: 2012-11-30 07:06 pm (UTC)no subject
Date: 2012-11-30 07:14 pm (UTC)И можно на ты.
no subject
Date: 2012-11-30 08:03 pm (UTC)Структурная рекурсия, это один простой паттерн, легко укладывающийся в довольно простой Тьюринг-худой язык.
А значит, имеем простой и предсказуемый reasoning.
Что вполне подтверждается на практике.
Общая рекурсия заставляет думать в рамках уже Тьюринг-полноты, что в общем случае, неразрешимо даже теоретически, а не то, чтобы уложилось человеку в голову.
Конечно же, при реальном программировании, возникает ряд "паттернов" (навроде отслеживания разборки значения индуктивного типа), иначе бы было очень сложно сделать что-то.
Ну вот, структурная рекурсия, это один из таких паттернов — простой, чОтко формализованный и весьма общий.
no subject
Date: 2012-11-30 08:39 pm (UTC)no subject
Date: 2012-11-30 08:55 pm (UTC)no subject
Date: 2012-11-30 09:05 pm (UTC)2. Этот пост возник из-за этой дискуссии (http://levgem.livejournal.com/420910.html?thread=5124654#t5124654). Т.е. "как заменить" уже есть.
Не стоит заменять. Если нужно, скажем, делать разбор двух структур по условию, то я пишу рекурсивный код. Пример: merge двух сортированных списков.
no subject
Date: 2012-11-30 09:31 pm (UTC)В качестве возможного примера могу предложить Omega monad: http://hackage.haskell.org/package/control-monad-omega
Комбинатор рекурсивной обработки потенциально бесконечных списков с гарантированным перечислением всех элементов.
no subject
Date: 2012-11-30 09:53 pm (UTC)Где, грубо говоря, file -- это исходник, а module -- директория. Нужно написать функцию, которая применит функцию компиляции к каждому исходному файлу, причём в правильном порядке, с учётом что от чего зависит.
Для данного примера порядок может быть таким: f1, f2, f4, f5, f3, f6, f0, f7.
В идеале ещё бы обнаружить циклические зависимости.
Как это сделать двойной рекурсией -- очевидно, а вот комбинаторного решения я придумать не могу.
no subject
Date: 2012-11-30 09:54 pm (UTC)no subject
Date: 2012-11-30 10:09 pm (UTC)http://www.haskell.org/haskellwiki/Scrap_your_boilerplate
(есть ещё более навороченные и/или удобные варианты, более поздние)
Например, одной строкой можно получить все файлы. Другой - все зависимости. Отображение (map compile) на файлы даст компиляцию и тп.
Наверное, это ближе всего к нужному тебе.
no subject
Date: 2012-11-30 10:27 pm (UTC)no subject
Date: 2012-11-30 10:28 pm (UTC)no subject
Date: 2012-11-30 10:42 pm (UTC)Сортируем пары вида (файл, зависимость) вот таким сравнением:
compareTopo (fa,depsa) (fb,depsb)
| fa `elem` depsb && fb `elem` depsa = error "cycle!"
| fa `elem` depsb = LT
| otherwise = EQ
sortDeps = sortBy compareTopo filesDeps
Первыми должны оказаться файлы без зависимостей.
Не однострочник, но близко.
no subject
Date: 2012-11-30 10:59 pm (UTC)Единственное, не могу сообразить, как scrap your boilerplate позволит мне одной строкой собрать из дерева все зависимости всех файлов, но верю на слово, что такое возможно.