Рекурсия

[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

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

[lomeo.livejournal.com]

Ага, спасибо!