lomeo | Functional pearls

Entry tags:

Functional pearls

Недавно на LTU проходила ссылка на Functional Pearls. Наконец то я до неё добрался и начал читать Richard Bird. How to Write a Functional Pearl. Понравившиеся, по исключительно субъективным причинам, моменты:

В одном из советов о том, как писать, Bird пишет: "Find an author whose style you admire and copy it (my personal favourites are Martin Gardner and Don Knuth).". Порадовало, собственно, наличие Мартина Гарднера в образцах подражания.

Во вторых, в примере решалки судоку, в коде не используются индексы для получения значений из матрицы. Когда я учил Haskell, мы с товарищем как раз писали такую решалку. В качестве одного из критерия сравнения декларативного и императивного подхода я тогда как раз понял то, что использование (!!), map ... [1..n] и тому подобное - это просто-напросто императивный код на функциональном языке. Избавляясь от подобного подхода, я сократил (и ускорил) программу. Собственно тогда я более-менее чётко понял, что такое декларативность и почувствовал, что она даёт.

Bird пишет об этой ситуации (с матрицей судоку) так:

Instead of thinking about coordinate systems, and doing arithmetic on subscripts to extract information about rows, columns and boxes, we have gone for denitions of these functions that treat the matrix as a complete entity in itself.

Geraint Jones has aptly called this style Wholemeal Programming

Wholemeal programming is good for you: it helps to prevent a disease called indexitis, and encourages lawful program construction.

Слово очень понравилось. На РСДН, например, замечен неоднократный оживляж по поводу паттерн-матчинга. Его превозносят, считая одной из основных черт функционального программирования. Не хочется его принижать - ПМ, действительно, вещь замечательная. Но у неё есть и недостатки, первый и главный из которых - это отсутствие сокрытия данных. Чуть поменялась структура - и вперёд по всему коду менять паттерны! Я стараюсь использовать ПМ для типов модуля внутри этого же модуля, а снаружи использовать комбинаторы над этим типом. И вот поэтому слово Wholemeal Programming мне очень нравится ;-)

Ну, и вообще насчёт статьи - метод, который применяется для разработки программы, очень интересен, что то вроде ручного fusion.

Flat | Top-Level Comments Only

>В одном из советов о том, как писать, Bird пишет: "Find an author whose style you admire and copy it (my personal favourites are Martin Gardner and Don Knuth).". Порадовало, собственно, наличие Мартина Гарднера в образцах подражания.

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

Про цельнозерновое программирование +10

> На Гарднере вообще вырос

Аналогично. Причём первая книга была ещё отцовская ;-)

Три толстых тома. Издательство Мир. "Математические новеллы", "Математические досуги", "Математические головоломки и развлечения". Зачитаны до дыр :-) И ещё куча тонких. "Крестики-нолики" появились, когда уже в универе учился.

Заглянул на Озон - есть переизданное: http://www.ozon.ru/context/detail/id/239949/?type=305#305. У меня - старые книжки.

Вот. Приятно похвастаться :-)

Супер! У меня не было "новелл", зато была A-ha (забыл как на русский переводится). А "Математические головоломки и развлечения" - это как раз и была отцовская (наверное, самая лучшая, в похожем стиле крестики-нолики написаны).

> Вот. Приятно похвастаться :-)

Да что там! Вспомнить приятно :-)

>На РСДН, например, замечен неоднократный оживляж по поводу паттерн-матчинга. Его превозносят, считая одной из основных черт функционального программирования. Не хочется его принижать - ПМ, действительно, вещь замечательная. Но у неё есть и недостатки, первый и главный из которых - это отсутствие сокрытия данных. Чуть поменялась структура - и вперёд по всему коду менять паттерны! Я стараюсь использовать ПМ для типов модуля внутри этого же модуля, а снаружи использовать комбинаторы над этим типом.

Собсно "оживляш" там идёт просто из-за новой игрушки, со временем практика использования устоится и все недостатки пропишутся вначале в неявном кодексе использования (это даже уже наблюдается на том коде, что пишут на N), а потом уже на уровень code style tools/language restrictions/some else. А так вся эйфория из-за постоянного использования императива в котором кроме switch и if ничего нету, и тут когда появляется новое средство аля ПМ, то это как отдушина сразу возникает. И с туплами та же история.

С Уважением, Andir!

Скорее всего так и есть. Я тут подумал, что, возможно, это субъективное. Я до Haskell'a знал ещё пролог, во всяких статьях встречал ML-ный код, писал на схеме - и необходимости в ПМ не возникало. У меня от ПМ эйфории не было - поэтому я удивляюсь, когда вижу её у других.

На Прологе без ПМ - поподробнее, пожалуйста

:-))) Проблема в пунктуации:

Я до Haskell'a

1. знал ещё пролог,
2. во всяких статьях встречал ML-ный код,
3. писал на схеме - и необходимости в ПМ не возникало
4...

Но у неё есть и недостатки, первый и главный из которых - это отсутствие сокрытия данных. Чуть поменялась структура - и вперёд по всему коду менять паттерны!

1. Нам в том поможет компилятор и
2. Это, оказывается, серъезная проблема, над которой работал и Вадлер в том числе.
От тут http://lambda-the-ultimate.org/node/2231 и тут http://lambda-the-ultimate.org/node/2232

Конечно, компилятор поможет, но не избавит от этой проблемы.
За статьи спасибо. Вот

palm_mute ниже напоминает о том, что patten guards есть.

> Но у неё есть и недостатки, первый и главный из которых - это отсутствие сокрытия данных. Чуть поменялась структура - и вперёд по всему коду менять паттерны

Вроде бы всевозможные Pattern Guards, Active Patterns, Views и т.д. призваны эту проблему решить

В общем, да. Я скорее о РСДН с его примерами ПМ на АСТ.

Хотя, если честно, я всё же обычно отдаю предпочтение функциям над данными. Здесь правда тоже по разному - со стандартными типами вроде Maybe работаешь с ПМ легко, зная, что они то никогда не изменятся ;-)

pattern guards ЭТУ проблему не решает. views не являются частью языка. что такое active patternms - я просто не в курсе, но как понимаю они тоже не реализованы даже в ghc

Как же не решают, если потроха не видно, а представление можно матчить? Ещё view patterns (http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns), кстати есть.

Активные паттерны - интересная идея из F#, я о ней читал на LTU (http://lambda-the-ultimate.org/archive/2007/04/09). Те же views, в принципе, сделаны удобно. Смысл тот же - удлиняем связь между АТД и его использованием, за счёт чего можем менять АТД не затрагивая код, где он используется.

>Как же не решают, если потроха не видно, а представление можно матчить?

этой фичи в языке нет, даже в ghc, это только предложение

а pattern guards, afair, это вот что:

f x | A y <- g x = ...

т.е. как раз возможность использовать в гуардах паттерны по обычным конструкторам типа, что как понимаешь, нифига ничего не скрывает

Смысл такой

f x | A y <- g x

x здесь типа T1, а (A y) типа T2. Т1 - это абстракция, а T2 - представление этой абстракции, перевод в это представление через комбинатор g. При изменении абстракции меняются только сама абстракция и комбинатор перевода в представление. Функция f не меняется.

Т.е. Т1 мы всё таки скрываем и при этом при изменении правим только один модуль.

>Но у неё есть и недостатки, первый и главный из которых - это отсутствие сокрытия данных

уже почти 20 лет есть предложение о добавлении в язык views. к сожалению этого так и не произошло - это несколько осложняет формальную сенмантику языка и следовательно использование его, скажем в системах автоматической верификации. на другой чаше весов лежит удобство порграммирование, причём не просто какие-то мелкие удобства, а приницпиально необходимая вохзможность сокрытия информации о представлении, ищзменения его без изменения клиентского кода. но увы - первые соображения джо сиз пор перевешивают

а вообще - я просто удивляюбсь, почему людям так сложно понять этот функциональный стиль. возможно, дело в том, что я-то знаком с языком АПЛ, которфй был построен именно на таком подходе - обрабатывать массивы целиком

помню, как там выглядит конструкция поиска подстроки в строке на основе простейшей операции - сравнения двух символов. всё выражение целиком - это примерно 10-15 символов. первым делом из этих двух строк конструируется матрица(!) сравнения каждого исмвола из одной строки с скаждым сиволом из другой. затем пара редукций - и мы полчаем список всех позиций одной строки в другой

> уже почти 20 лет есть предложение о добавлении в язык views

Увы, имеющиеся механизмы симпатичны, но недостаточны. views подразумевает, мол это не тип, а представление, в pattern guards же, или view patterns нам приходится создавать тип для представления самим. Для языка он так и будет типом. Т.е. это просто эмуляция views :-(

> а вообще - я просто удивляюбсь, почему людям так сложно понять этот функциональный стиль
Мне кажется, понять сложно, потому что раньше действовали по другому. Я помню, что когда я это понял (почувствовал), это был прорыв - дальше ФП было для меня легко и прекрасно.

> помню, как там выглядит конструкция поиска подстроки в строке на основе простейшей операции - сравнения двух символов ...
substr sub = findIndex id . init . map (and . zipWith (==) sub) . tails

> и мы полчаем список всех позиций одной строки в другой
findIndices т.е. вместо findIndex тогда

> wholemeal programming

Что же, мля, никто с более явной и развитой концепцией работать не хочет, а всё придумывает всякое полу-ad-hoc?...

Ой... Это же 5.5 лет назад! ;-)

:-) Да, было дело.

Flat | Top-Level Comments Only

Functional pearls

no subject

no subject

no subject

no subject

О паттерн-матчинге на RSDN

Re: О паттерн-матчинге на RSDN

Re: О паттерн-матчинге на RSDN

Re: О паттерн-матчинге на RSDN

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject