Рекурсия

[lomeo]

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

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

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

Comments

[inv2004]

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

[mrparker]

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

[nealar]

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

[lomeo]

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

[thedeemon]

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

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

[lomeo]

Да собственно тут всё сказано.

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

Ну, и в нагрузку ещё немножко про дизайн от Люка Палмера (правда, это оффтопик).

[miserakl]

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

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

[lomeo]

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

[miserakl]

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

[nealar]

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

[nivanych]

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

[lomeo]

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

[nivanych]

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

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

[swizard]

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

[lomeo]

1. "Избегайте" /= "Никогда не используйте".
2. Этот пост возник из-за этой дискуссии. Т.е. "как заменить" уже есть.

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

[swizard]

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

[thesz]

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

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

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