Рекурсия

[lomeo]

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

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

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

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

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

Comments

[inv2004.livejournal.com]

Могу только поддержать.

[mrparker.livejournal.com]

Могу только плюсанутся...

[nealar.livejournal.com]

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

[lomeo.livejournal.com]

Я стараюсь использовать её для реализации комбинаторов. Ну, т.е. вот есть модуль с объявленным типом, сначала, конечно typeclass morphism, потом более конкретные функции для этого типа. И вот всё это можно и через рекурсию. А наружу уходят чистые комбинаторы.

[thedeemon.livejournal.com]

>сначала, конечно typeclass morphism

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

[lomeo.livejournal.com]

Да собственно тут (http://conal.net/papers/type-class-morphisms/) всё сказано.

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

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

[thedeemon.livejournal.com]

Первое я видел, но хотелось бы примеров из личной практики.

[miserakl.livejournal.com]

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

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

[lomeo.livejournal.com]

:-) Явная рекурсия - зло.

[miserakl.livejournal.com]

А, так это специально. Небось до вечера пятницы тоже нарочно откладывали? :)

[nealar.livejournal.com]

Отложенные вычисления :)

[lomeo.livejournal.com]

Нет, так вышло ;-)

И можно на ты.

[nivanych.livejournal.com]

Можно ещё такой довод.
Структурная рекурсия, это один простой паттерн, легко укладывающийся в довольно простой Тьюринг-худой язык.
А значит, имеем простой и предсказуемый reasoning.
Что вполне подтверждается на практике.
Общая рекурсия заставляет думать в рамках уже Тьюринг-полноты, что в общем случае, неразрешимо даже теоретически, а не то, чтобы уложилось человеку в голову.
Конечно же, при реальном программировании, возникает ряд "паттернов" (навроде отслеживания разборки значения индуктивного типа), иначе бы было очень сложно сделать что-то.
Ну вот, структурная рекурсия, это один из таких паттернов — простой, чОтко формализованный и весьма общий.

[lomeo.livejournal.com]

Один раз реализовать свёртку полезно для типа ;-) Хотя сейчас уже deriving Foldable есть.

[nivanych.livejournal.com]

> полезно для типа

Ему от этого становится лучше, да! ;-)

[swizard.livejournal.com]

А можно вот такой теоретический вопрос: как предлагается заменять, например, двойную (или более широкую) рекурсию комбинаторами?

[lomeo.livejournal.com]

1. "Избегайте" /= "Никогда не используйте".
2. Этот пост возник из-за этой дискуссии (http://levgem.livejournal.com/420910.html?thread=5124654#t5124654). Т.е. "как заменить" уже есть.

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

[swizard.livejournal.com]

Понятно, спасибо.

[thesz.livejournal.com]

А что это такое?

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

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

[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) на файлы даст компиляцию и тп.

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

[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

[lomeo.livejournal.com]

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

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

[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