Рекурсия

[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

[thesz.livejournal.com]

data Then = Then
data Else = Else

ifM condM Then thenM Else elseM = ...

main = do { ... ifM cond Then (print "yep!") Else (print "nope."); ... }

Украдено на LtU.

К слову. Генри Бейкер всего один смыслящий из немногих, отстаивающих позицию, напоминающую позицию Влада. А вот Вадлеров, Стилов, всяких, там, Брэди и прочих Пейтон-Джонсов с другой точки зрения - куча. ;)

[lomeo.livejournal.com]

Э... Я ничего не крал :-) Видел похожий приём со искусственными скобками не помню где.

Генри Бейкера до сих пор не прочёл :-(