Рекурсия

[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]

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

[kurilka.livejournal.com]

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

[lomeo.livejournal.com]

Мне кажется, что он противопоставляет практику и математику.

[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, рекурсивная версия оказывалась понятнее.

[lomeo.livejournal.com]

Ну, я не говорил о равенстве математики и программирования. Я оспаривал противопоставление, которое сделал Влад. Статью не читал, поэтому ничего не скажу.

> Например, в твоем примере incAll содержит в себе неявный case-analysis
Это зависит от реализации комбинатора. А то получается, что мы сравниваем вызов, использующий комбинатор, и явный инлайн этого комбинатора в реализацию и говорим, что вызов содержит в себе неявный инлайн :-)

Что касается того, что функцию надо переписывать - да, такое встречается. pointfree страшен, лямбда туманнее вызова, а вложенная функция требует придумать ей имя. Выбираем то, что удобнее в данной ситуации.

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

> при его применении мне не хватает ключевых слов then и else, вот такая мелочь, а неприятно.
Ну, Haskell позволяет же строить DSEL, надо этим пользоваться

{-# LANGUAGE EmptyDataDecls #-}

data ThenM
thenM = undefined

data ElseM
elseM = undefined

ifM cond _ t _ e = cond >>= \x -> if x then t else e

> ifM (return True) thenM (print "yes") elseM (print "no")

или, если скобки не нравятся

ifM = id

thenM c t = c >>= \b -> return (b,t)

elseM ct e = ct >>= \(c,t) -> if c then t else e

> ifM (return True) `thenM` print "yes" `elseM` print "no"

Тут можно кучу всего придумать.

Насчёт unfoldr согласен. Бывает, что пользоваться комбинатором неудобно, но это проблема комбинатора, а не подхода, мне кажется. Хотя тут надо думать.

[palm-mute.livejournal.com]

> ifM (return True) thenM (print "yes") elseM (print "no")
Прикольный фокус, я не додумался. thenM, естественно, будет типа ThenM, и у ifM будет тип ifM :: m Boold -> ThenM -> ...?

>А то получается, что мы сравниваем вызов, использующий комбинатор, и явный инлайн этого комбинатора
Если мы говорим только о понятности кода, это вполне допустимое сравнение. Вернемся к катаморфизмам, вот пример из статьи Джонса:

len = cata (\fa -> case fa of
                     Nil       -> zero
                     Cons z zs -> succ zs)

Та же самая функция без катаморфизмов выглядела бы так:

len xs = case xs of
            Nil       -> zero
            Cons z zs -> succ (len zs)

Ее можно получить из первой совершенно автоматически.
foldr из стандартной библиотеки можно использовать без сопоставления с образцом только потому, что foldr не совсем катаморфизм, т.к. принимает 2 аргумента вместо одного - тут можно вспомнить о том, что любой АТД с N конструкторами можно представить в виде функции с N аргументами, и вместо встроенного в язык паттерн-матчинга использовать вызов функции. Похожий случай и стандартной библиотеки - функция either, которая ничего, кроме паттерн-матчинга, собственно, не делает. Ее вызов с двумя лямбдами ничем не лучше case-выражения, ее удобно использовать только в point-free стиле.
Потому мне кажется, что, повторюсь, с точки зрения понятности кода, foldr не намного лучше рекурсии. Более специализированные комбинаторы типа map - естественно, лучше.

>Спасибо за коммент, кстати, ты всегда заставляешь меня задуматься.
Да ну, не стоит благодарностей. Хорошо, что ты опять пишешь.

[lomeo.livejournal.com]

Насчёт того, что foldr это не совсем катаморфизм, т.к. принимает два аргумента - не согласен. Катаморфизм применяет стрелку, а не функцию, а как мы её расписываем - дело наше. Я не видел такую запись катаморфизма, как у Джонса, но не один раз встречал

φ . in

где φ (стрелка) представляется в виде тапла функций. Подразумевается, что (f,g) (x,y) = (f x, g y). Впрочем, из одного можно получить другое, но, что важнее, foldr удобнее cata. Именно потому что скрывает case.

Но насчёт either, maybe, unfoldr и т.д. я соглашусь - лямбды выглядят не очень. Но если у нас pointfree, при чём разумный, без ужасных (.).(.), то эти комбинаторы спасают. Именно потому, что поднимают уровень абстракции, и частично понятность кода.

[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]

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

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

[lomeo.livejournal.com]

Спасибо за коммент, кстати, ты всегда заставляешь меня задуматься.

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

[(Anonymous)]

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