Рекурсия
На 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) предпочтительнее явной рекурсии. Комбинаторы (или композиция комбинаторов) имеют перед явной рекурсией следующие преимущества:
Итак, мат.аппарат позволяет определять формальным путём комбинаторы для решения проблемы явной рекурсии - проблемы практической. Близость инструмента (Haskell в нашем случае) к математике позволяет выражать на нём эти формальные решения более явным образом. Следовательно, близость инструмента к "математическому смыслу" определяет также и его практичность. Не прямо пропорционально, но это одна из характеристик практичности, по моему, очень важная.
Для тех, кто дочитал до этого места - бонус. Как можно описать разные сортировки с помощью разных паттернов рекурсии, читай: рекурсивных комбинаторов - Sorting Morphism.
Лично по мне так чем дальше инструмент от математического смысла, тем лучше.
Смысл в том, как я понял, что чем ближе инструмент "к математическому смыслу", тем дальше он от практического. Я с этим совершенно не согласен, однако быстро доказать его неправоту не могу. Поэтому попробую продемонстрировать практичность математического аппарата.
Один из примеров, кстати, это мои два предыдущих поста. Здесь математический подход, а здесь практический.
Итак, одно из первых правил, которое зазубривает юный хаскелист, это "Избегайте явной рекурсии". Целесообразность этого правила не вызывает сомнений. Однако демонстрации строятся на одном типе данных - на списках. Очевидно, что мощный набор рекурсивных комбинаторов для списка (см. 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.