Рекурсия

[lomeo]

На RSDN я очередной раз дискутировал с VladD2 и, кстати, для меня дискуссия получилась довольно полезной. Речь шла, в частности, и о Haskell. Один из необсуждённых (пока?) тезисов высказал VladD2:

Лично по мне так чем дальше инструмент от математического смысла, тем лучше.

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


Один из примеров, кстати, это мои два предыдущих поста. Здесь математический подход, а здесь практический.

Итак, одно из первых правил, которое зазубривает юный хаскелист, это "Избегайте явной рекурсии". Целесообразность этого правила не вызывает сомнений. Однако демонстрации строятся на одном типе данных - на списках. Очевидно, что мощный набор рекурсивных комбинаторов для списка (см. Data.List), покрывает бОльшую часть задач, требующих рекурсии (списка). Мы, конечно, можем вспомнить об отсутствующем split, но в целом, стоит признать, что явная рекурсия при работе со списком встречается не так уж часто. Один из самых мощных комбинаторов - это foldr, которым я тут всех уже замучил. К сожалению, для понимания он сложнее, чем более простые (и более конкретные) map и filter. Достаточно сравнить foldr (\x xs -> f x : xs) [] с простым map f. Однако, с помощью foldr мы можем определить большое число функций. И уже здесь видим, что

incAll = foldr (\x xs -> x + 1 : xs) []

понятнее, чем

incAll [] = []
incAll (x:xs) = x + 1 : incAll xs

если мы хорошо понимаем свёртку. Ну, по крайней мере, запись короче :-) В целом, даже сложный комбинатор (foldr) предпочтительнее явной рекурсии. Комбинаторы (или композиция комбинаторов) имеют перед явной рекурсией следующие преимущества:

• Короче и понятнее запись.


• Не разбивается цепочка (композиция) - больше простора для оптимизации. Например, можем описать rewrite rule для своего fusion.


• Работа на более высоком уровне абстракции - с коллекцией, а не элементами (wholemeal programming).

Очевидно, что если мы применяем это правило и на другие структуры данных, то пользуемся всё теми же преимуществами. Таким образом, даже только универсальные комбинаторы (бананы, линзы и компания) уже дают нам в руки мощный инструмент. Обычно же мы ещё описываем кучу специальных, являющихся частными случаями универсальных.

Итак, мат.аппарат позволяет определять формальным путём комбинаторы для решения проблемы явной рекурсии - проблемы практической. Близость инструмента (Haskell в нашем случае) к математике позволяет выражать на нём эти формальные решения более явным образом. Следовательно, близость инструмента к "математическому смыслу" определяет также и его практичность. Не прямо пропорционально, но это одна из характеристик практичности, по моему, очень важная.

Для тех, кто дочитал до этого места - бонус. Как можно описать разные сортировки с помощью разных паттернов рекурсии, читай: рекурсивных комбинаторов - Sorting Morphism.

Comments

[antilamer.livejournal.com]

Покажи Владу вот это:
http://apfelmus.nfshost.com/monoid-fingertree.html
http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html
http://sigfpe.blogspot.com/2008/11/approach-to-algorithm-parallelisation.html
http://citeseer.ist.psu.edu/blelloch90prefix.html

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

[kurilka.livejournal.com]

Меня тоже смутил этот тезис Влада.
Хорошо хоть слово "монада" не было произнесено :)

[palm-mute.livejournal.com]

Да простят мне ссылку на авторитет, но равенство между математикой и программированием оспаривает не только Влад. Генри Бейкер, на статью (http://home.pipeline.com/~hbaker1/ForthStack.html) о линейной логике которого пару раз ссылался thesz, тоже критикует этот взгляд.

Про комбинаторы - опять же, не совсем соглашусь. Ценность нерекурсивных определений для оптимизаций, rewrite rules и т.д. очевидна, а вот понятность - штука формально неопределенная, тут есть о чем поспорить. По-моему, однозначная экономия получается, если у нас есть под рукой готовые функции, которые можно передать комбинатору, получается короткое и понятное point-free выражение, в этом случае я согласен с тезисом о более высоком уровне абстракции и wholemeal programming. Если же для того, чтобы воспользоваться комбинатором, функцию нужно написать специально так, чтобы комбинатору понравилось, и понятность, и экономия уже не так очевидны. В point-free стиле начинается кошмар из (flip (.) . flip flip), а в pointful стиле рекурсивная и нерекурсивная версии изоморфны, экономятся считанные символы, а количество информации совпадает. Например, в твоем примере incAll содержит в себе неявный case-analysis, есть значение, которое нужно возвращать в случае пустого списка - [], и функция, которая вызывается в случае непустого списка. Сэкономили на визуальных подсказках, которые в данном случае не очень нужны, а в другом месте понадобились бы. Например, когда я определяю монадную версию условного оператора:
(ifM cond t e = cond >>= \ x -> if x then t else e),
при его применении мне не хватает ключевых слов then и else, вот такая мелочь, а неприятно.
Другой пример: сколько раз ни пробовал использовать unfoldr, рекурсивная версия оказывалась понятнее.

Правильный антиквариат в Санкт-Петербурге

[(Anonymous)]

Антикварный салон «Янус» (http://yanusantik.ru/)продает, приобретает антиквариат, проводит оценку предметов старины и антиквариата в Санкт-Петербурге.