Wunderwaffe: супероружие Третьего рейха. Подземное боевое средство

Мне задавали их множество раз. Отвечаю.

«Что такое этот ваш Haskell?»

Haskell - чисто функциональный язык программирования общего назначения, может быть использован для решения самого широкого круга задач. Компилируемый, но может вести себя и как скриптовый. Кроссплатформенный. Ленивый, со строгой статической типизацией. И он не похож на другие языки. Совсем.

«Это что, какой-то новый язык?»

Вовсе нет. История Haskell началась ещё в 1987 году. Этот язык был рождён в математических кругах, когда группа людей решила создать лучший функциональный язык программирования. В 1990 году вышла первая версия языка, названного в честь известного американского математика Хаскелла Карри . В 1998 году язык был стандартизован, а начиная с 2000-х началось его медленное вхождение в мир практического программирования. За эти годы язык совершенствовался, и вот в 2010 мир увидел его обновлённый стандарт. Так что мы имеем дело с языком, который старше Java.

«И кто его сделал?»

Haskell создавался многими людьми. Наиболее известная реализация языка нашла своё воплощение в компиляторе GHC (The Glasgow Haskell Compiler), родившегося в 1989 году в Университете Глазго. У компилятора было несколько главных разработчиков, из которых наиболее известны двое, Simon Peyton Jones и Simon Marlow . Впоследствии весомый вклад в разработку GHC внесли ещё несколько сотен человек. Исходный код компилятора GHC открыт . Кстати, сам компилятор на 82% написан на Haskell.

Для любопытных: исчерпывающее повествование об истории Haskell и GHC читайте .

«А библиотеки для Haskell имеются?»

О да! Их даже не сотни - их тысячи. В процессе чтения вы познакомитесь со многими из них.

«И что, его уже можно в production?»

Он уже в production. С момента выхода первого стандарта язык улучшался, развивалась его экосистема, появлялись новые библиотеки, выходили в свет книги. Haskell полностью готов к серьёзному коммерческому использованию, о чём свидетельствуют истории успешного внедрения Haskell в бизнесе, в том числе крупном .

«А порог вхождения в Haskell высокий?»

И да и нет. Освоение Haskell сложно в первую очередь из-за его непохожести на остальные языки, поэтому людям, имеющим опыт работы с другими языками, мозги поломать придётся. Именно поломать, а не просто пошевелить ими: Haskell заставляет иначе взглянуть даже на привычные вещи. С другой стороны, Haskell проще многих известных языков. Не верьте мне на слово, вскоре вы и сами в этом убедитесь. И знайте: многие люди, узнав вкус Haskell, категорически не желают возвращаться к другим языкам. Я вас предупредил.

«А я слышал ещё про какие-то монады…»

Да, есть такое дело. Некоторые вещи из мира Haskell не имеют прямых аналогов в других языках программирования, и это вводит новичков в ступор. Но не беспокойтесь: я сам прошёл через этот ступор и хорошо вас понимаю. Помните: новое лишь кажется страшным.

«А если сравнить его с C++/Python/Scala…»

Сравнение Haskell с другими языками выходит за рамки этой книги. Несколько раз вы встретите здесь кусочки кода на других языках, но я привожу их исключительно для того, чтобы подчеркнуть различие с Haskell, а вовсе не для сравнения в контексте «лучше/хуже». И вообще, я буду изо всех сил стараться не восхвалять Haskell без меры, я хочу лишь рассказать вам правду о нём. Мой вывод об этом языке я уже сделал, а свой вывод о нём вы должны сделать сами.

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

Большинство современных функциональных языков так же предоставляют некоторые гарантии касательно программ. В частности, Haskell в большинстве случаев гарантирует, что программа не завершится с ошибкой доступа к памяти, как, скажем C++, или с ошибкой преобразования типов, как, скажем, Python или Ruby. Большинство подобных ошибок будут обнаружены на этапе компиляции программы.

В основе функционального программирования лежит простое представление о том, что функции в языке ничем не отличаются от переменных. Обычно к этому добавляют, что функции в целом должны быть функциями в математическом смысле, то есть не должны иметь некого внутреннего состояния и не должны неявно изменять внешнего состояния (окружения). Прямым следствием отсутствия состояния является тот факт, что функция, вызванная с одними и теми же аргументами возвращает одно и то же значение. Следствием неизменности внешнего состояния является отсутствие побочных эффектов. Например, printf в C/C++ принимает некие аргументы, и возвращает число. Но кроме этого, printf выводит символы в терминал. Последнее является побочным эффектом. В общем случае, неявные изменения внешнего (по отношнению к программе) состояния считаются побочными эффектами.

Но если внешнее состояние неизменно, программа неизбежно превращается в некую Кантовскую “вещь в себе” – она не может читать/записывать файлы, терминал, и т.д. Это не выглядит очень полезным. На самом деле, ФЯП выходят из положения, вводя некую псевдопеременную “мир”, которая может явно быть передана главной функции программы (main), и ее измененное состояние явно возвращается главной функцией программы. Таким образом, функциональную программу можно алгебраически представить как некую функцию:

\[ W_{n+1} = P(W_{n}), \]

где $W$ – состояние окружения (“мир”), а $P$ – это программа.

Другая особенность ФЯП, прямо следующая из того, что функции не имеют и не изменяют состояния заключается в том, что в ФЯП очень часто нет “переменных”. Любые выражения являются константами, если смотреть с точки зрения императивных языков. Это свойство называется “ссылочной прозрачностью”: если вы видите, что функция принимает переменную, вы всегда точно знаете, какое значение имеет эта переменная.

Подобный подход значительно упрощает “думание” о программах: больше не нужно держать в голове состояние – код работает ровно так, как читается – никаких скрытых параметров.

Использование чистых функций, помимо прочего, позволяет значительно упростить реализацию функций высших порядков, т.е. функций, оперирующих с функциями (которые тоже могут оперировать с функциями, и так далее). Поэтому, большинство ФЯП имеют поддержку функций высшего порядка “встроенными” в язык интуитивным образом. В качестве небольшого примера, приведу сравнение реализаций функции for_each , работающей со списком на C++ и Haskell.

Функции высшего порядка

На Haskell аналогичный код будет выглядеть так:

На самом деле, вызов функции с аргументами в Haskell является настолько фундаментальным, что не имеет специального синтаксиса, поэтому аналогичный код можно записать так:

На самом деле в языке уже есть такая функция, и она называется map . Вернемся к ней чуть позже.

Каррирование

Очень интересным мометном здесь является использование (1+) для добавления 1. Для этого придется рассказать про нотацию Хаскеля Брукса Карри (американского математика, 1900-1982), в честь которого назван язык. Эта нотация называется частичной аппликацией функций или каррирование .

Вкратце, любая функция нескольких аргументов $f(x,y)$ может быть разложена на последовательное применение нескольких функций одного аргумента. Например, $f(2,3)$ может быть разложена как:

\[ g(y) = f(2,y) \] \[ f(2,3) = h(g(3)) \]

Можно заметить, что функция двух аргументов $f(x,y)$ превращается в функцию одного аргумента $g(y)=f(x,y)$ . Это и есть каррирование. Если записать то же самое в нотации Haskell:

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

Какое отношение это имеет к (1+) ? Самое прямое. (1+) . Сложение является функцией двух аргументов и может быть записано как x+y = (+) x y . Тогда применение к одному аргументу (+) 1 даст нам функцию одного аргумента, которая прибавляет к аргументу 1. (1+) – это просто синтаксическое соглашение (“сахар”), которое сводится к (+) 1 .

Порядок применения функции

Чтобы каррирование работало, аргументы функции применяются слева направо (или лево-ассоциативно). Таким образом, выражение вида

Означает то же самое, что

Это отвечает на вопрос, почему нельзя записать print for_each (1+) и ожидать адекватных результатов (на самом деле такой код просто не скомпилируется, поскольку print for_each не может принимать аргументы)

Существует оператор $ , который является право -ассоциативным применением функции. Поэтому код можно записать так:

Это позволяет слегка экономить на скобках, однако применимость зависит от конкретного случая.

Эта-редукция, композиция функций и pointfree-нотация

Другой способ экономии – это эта-редкукция.

Эта-редукция позволяет писать достаточно компактный и при этом вполне понятный код, опуская “лишние” переменные. Такая нотация называется “pointfree” (аргументы иногда называют “точками”, отсюда такое название). Напишем программу, которая читает строки и выводит их в обратном порядке.

Пока не обращая внимания на последнюю строчку (считаем что там магия), рассмотрим функцию revlines. Очевидно, что x здесь вполне избыточен. В математике есть нотация композиции функций, обозначаемая точкой:

\[ f(g(x)) = (f\cdot g)(x) \]

Haskell имеет аналогичную нотацию: f (g x) = (f . g) x . Тогда мы можем переписать revlines в виде

Или, применяя эта-редукцию:

Использование функций высшего порядка возможно и в этом контексте. Скажем, мы можем хотеть не только вывести строки в обратном порядке, но и произвести каую-то другую операцию над массивом строк. Тогда мы можем написать:

Аннотации типов

Можно заметить, что во всем до сих пор написанном коде нигде не указаны типы. Haskell является строго типизированным языком, но типы указывать не обязательно. Это потому, что Haskell выводит типы автоматически. Тем не менее, для повышения читаемости кода (и для уменьшения вероятности ошибки), типы можно указывать . Запишем типы некоторых функций, и обсудим что это значит:

По соглашению, типы начинаются с заглавной буквы. Если тип обозначен маленькой буквой, то Haskell автоматически выводит его исходя из контекста. Так, например, мы использовали for_each с целыми. Тогда a=Int , b=Int . С тем же успехом, мы могли бы использовать ее со строками и т.д.

Оператор -> – право -ассоциативен (ввиду каррирования), поэтому

т.е. “функция принимает два аргумента”, эквивалентно

т.е. “функция принимает один аргумент и возвращает функцию одного аргумента”

map как функция высшего порядка

Попробуем написать свою функцию для работы со строками. Допустим, мы пишем программу, автоматически форматирующую код.

Получаем чудовищное, по виду, сообщение об ошибке

Couldn"t match type ‘Char’ with ‘’ Expected type: -> Actual type: -> In the first argument of ‘withLines’, namely ‘indent’ In the expression: withLines indent

Почему это происходит? Давайте запишем типы всех функций.

Ошибка становится вполне очевидна: withLines ожидает функцию типа -> , а мы ему даем String->String . Вообще, String определен как , т.е. список символов. Это объясняет сообщение компилятора.

Вспомним про функцию map , которая производит операцию над каждым элементом массива. Ее тип

Подставляя a,b=String , обнаруживаем то, что ищем:

Оказывается, map – это функция высшего порядка, которая преобразует функцию над элементами в функцию над массивами (списками). Подобные операции называются “поднятием” (lift), поскольку “поднимают” функцию из более простой категории типов в более сложную. Вообще, система типов Haskell сильно основана на теории категорий. Однако про теорию категорий сейчас не будем.

Секционирование операторов

Еще один пример использования функций высшего порядка

Здесь есть достаточно странный синтаксис. Для начала будем иметь ввиду, что любой бинарный оператор (а вообще говоря любая бинарная функция) может быть частично применен как

Вообще, `op` – это использование бинарной функции op как бинарного оператора

C тем же успехом можно частично применить второй аргумент:

Этот синтаксический сахар называется “секционирование операторов”

. – это бинарная функция высшего порядка:

Соответственно, если мы перепишем, скажем, withLines с аргументом, то получим:

Типы данных

В примерах раннее мы использовали тип данных списка (массива). Как этот тип устроен? Давайте попробуем сделать пользовательский тип списка.

Теперь мы можем записать что-то такое, например:

В Haskell, естественно, есть встроенный тип списка. Он определен следующим образом:

Можно просмотреть параллели. : – это Добавить, или cons , – это Пусто, или nil , а Список а – это [a] . Мы можем легко определить собственные операторы:

Или использовать их сразу в определении типа.

Единственное, что встроено в язык – это синтаксис вида , который автоматически преобразуется в x:y:...: .

Здесь Добавить и Пусто называются конструкторами типа Список . Это функции, которые “конструируют” значение типа Список. Не имеют практически ничего общего с конструкторами объектов в C++/Java.

Несколько примеров с нашим пользовательским типом:

С mystery1 , mystery2 все должно быть понятно. mystery3 – это бесконечный список, и Haskell все устраивает (поскольку это ленивый язык – значения вычисляются только при использовании), mystery4 – это ошибка типа. Int и String не могут находиться в одном списке.

Аналогично пишутся прочие типы данных.

Шаблоны аргументов

Для простоты, переопределим наш тип списка в латинице и сразу используем оператор:

Напишем несколько функций для нашего пользовательского списка:

Выглядит как какая-то черная магия. На самом деле все просто, мы определяем функцию, которая работает только для конкретного конструктора . _ означает только что мы игнорируем это поле. Мы так же могли бы конкретизировать аргументы, например:

Шаблоны проверяются в порядке объявления, поэтому во втором случае мы можем просто игнорировать значение.

Если мы не указываем все возможные варианты, то компилятор сообщает об этом, например:

Приводит к сообщению

Pattern match(es) are non-exhaustive In an equation for ‘isOne’: Patterns not matched: Nil

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

Тип Maybe

Немного странно кажется, что наша функция takeOne возвращает список, а не значение. Аналогичная библиотечная функция head возвращает значение, однако на пустом списке кидает исключение (да, в Haskell есть исключения, но их стараются избегать по очевидным причинам). Ее можно было бы записать в виде

undefined – ключевое слово, которое подходит под любой тип и аварийно завершает программу при попытке вычисления. Другой вариант undefined – это error x , где x имеет вид String . error выведет строку x перед завершением.

На помощь приходит тип Maybe . Он определен так:

В целом похоже на список, только без списка. takeOne можно переписать в виде:

Выглядит несколько более осмыслено, чем вариант со списком и гораздо более безопасно, чем undefined .

Попробуем написать поиск символа в строке с использованием типа Maybe:

Pattern guards

Предыдущий код можно переписать несколько короче:

Этот синтаксис называется “pattern guards”, или ограничители шаблонов в вольном переводе на русский. По сути, если выражение после | вычисляется как True , то шаблон срабатывает. Если нет – то проверяется следующий ограничитель, или следующий шаблон, если это был последний. otherwise – это просто более читаемый синоним для True .

В ограничителях так же возможно производить сравнения шаблонов. Синтаксис для этого:

Тогда код выше можно переписать в виде:

Классы типов

На самом деле мы можем записать более общий вариант поиска элемента в списке , практически ничего не делая:

Мы изменили только сигнатуру типа, остальное осталось прежним. Сигнатура выглядит странновато: в ней появилось выражение Eq a => . Оно означает, что тип a принадлежит классу Eq – классу типов, для которых определена эквивалентность, т.е. опреатор (==) .

Eq определен следующим образом:

Видно, что это просто сигнатура типа. Чтобы определить реализацию для конкретного типа, определяется экземпляр класса:

Каким конкретно образом реализовано сравнение символов – довольно долгая история. Примитивные типы типа Int , Char или скажем Double достаточно глубоко встроены в язык. Мы, однако, можем определить экземпляры для более сложных типов:

Здесь мы опять вводим ограничение на класс. По сути мы утверждаем, что для всех типов a в классе Eq существует тип Maybe a , так же в классе Eq . Ничто не мешает добавлять собственные типы.

Классы типов позволяют писать обобщенные, и при этом типобезопасные функции.

Опять про Maybe

Тип Maybe достаточно простой и при этом удивительно полезный. Очень многие функции, которые возможно определены могут использовать этот тип в качестве возвращаемого значения. Например:

Это гораздо лучше, чем возвращать NULL , как в C/C++ . Во-первых, глядя на сигнатуру типа, сразу становится ясно, чего можно ожидать от функции. Во-вторых, компилятор не позволит производить вычисления с несуществующим значением. Если в “классических” языках типы в основном служат компилятору, то в функциональных типы служат в первую очередь программисту.

Очевидный вопрос с Maybe заключается в следующем: допустим у нас есть функция

Рассмотрим такой код:

Каков результат такого кода? Правильный ответ – ошибка типа. 1 имеет тип Int , в то время как takeOne возвращает тип Maybe Int . Проблема очевидна. Наивное решение этой проблемы в том, чтобы написать условие:

Однако ясно, что для сколько-нибудь сложных выражений это становится весьма трудоемкой задачей.

Теперь давайте вспомним, что, когда я говорил про map , я сказал, что эта функция “поднимает” свой первый аргумент в категорию списков. Эта же концепция применима ко всем производным типам. В языке сущесвтует обобщенная функция fmap . Посмотрим, как она работает:

Это выражение возвращает Just 2 . fmap “поднимает” свой аргумент в категорию производных типов. Каких именно – компилятор выводит автоматически из контекста.

Тип fmap определен как

Здесь используется класс Functor , единственное требование которого – чтобы был определен fmap . Для Maybe экземпляр определяется тривиально:

В общем случае класс Functor – это класс типов, принимающих один аргумент типа. Другой пример функтора – список. Таким образом, map является всего лишь частным случаем fmap .

Монады

Пока скажу только, что Maybe , и список являются монадами. Понятие монады происходит из теории категорий. Это понятие в большинстве функциональных языков является ключевым, поскольку, например, Haskell, инкапсулирует состояние окружения (то, которое функции не изменяют) в монаде IO (ввод-вывод). Наконец мы можем записать сигнатуру для main:

Функция main возвращает “пустоту” (на самом деле читается как unit, и аналогично по смыслу void в С) в монаде IO . IO , в свою очередь, где-то “внутри” содержит информацию о состоянии окружения.

Сточка, которая часто нам встречалась

использует следующие функции:

return и (>>=) (читается как bind) определены в классе Monad . return просто “поднимает” значение в монаду, а bind берет значение в монаде и передает его в функцию, возвращающую монаду. При этом некое “состояние”, инкапсулированное монадой (если оно есть), может неявно передаваться из функции в функцию через оператор bind.

Для интересующихся, хорошее объяснение:

Если есть интерес, выделим лекцию на продолжение.

Синтаксис двух последовательных идентификаторов означает применение функции foo к своему аргументу bar:

На Haskell вызов функции не требует заключения аргумента в скобки.

Скобки используются для группировки аргументов:

acos (cos pi)

Функция нескольких аргументов:

max 5 42

Операция применения функции ассоциативна влево:

(max 5) 42

Функция max последовательно применяется к двум аргументам.
Компилятор понимает конструкцию f x y как (f x) y , а не наоборот f (x y) .

Выражение (max 5) это так называемое частичное применение функции. В общем виде его можно сформулировать следующим образом: если у нас имеется функция N переменных и мы смотрим на неё как на функцию N переменных, то мы можем взглянуть на неё с другой стороны и сказать, что это функция одной переменной возвращающая нам функцию N - 1 переменной.

3 + sin 42

3 + (max 5) 42

Синтаксис объявления пользовательской функции

Функция, которая осуществляет суммирование квадратов двух переданных в неё аргументов:

SumSquares x y = x ^ 2 + y ^ 2 rock"n"roll = 42

Имя функции и имена формальных параметров должны начинаться с символа в нижнем регистре. А символы в верхнем регистре служат для определения типов данных.

Функция трех аргументов, которая вычисляет длину трехмерного вектора:

LenVec3 x y z = sqrt (x ^ 2 + y ^ 2 + z ^ 2 )

Для определения функции в интерпретаторе GHCi нам нужно использовать ключевое слово let.

Let sumSquares x y = x ^ 2 + y ^ 2

Свойство чистоты функции

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

Функция, которая не принимает ни одного аргумента это константа. Такая функция всё время возвращает одно и то же значение независимо ни от каких обстоятельств.

Prelude > let fortyTwo = 39 + 3 Prelude > fortyTwo 42

На Haskell нельзя определить функцию не принимающую никаких аргументов, которая бы возвращала разные значения при разных вызовах.

Механизм определения функций с помощью частичного применения

На любую функцию мы можем смотреть как на функцию одного аргумента возвращающую некоторую функцию.

Prelude > let max5 x = max 5 x Prelude > max5 4 5 Prelude > max5 42 42

Альтернативный синтаксис определения функции:

Prelude > let max5" = max 5 Prelude > max5" 4 5 Prelude > max5" 42 42

Мы сократили слева и справа дополнительный аргумент x. И написали, что функция max5" это просто частично примененная функция max. Таким образом можно определять функцию не указывая всех аргументов. Соответствующий стиль программирования называется бесточечным.

Часто дизайн функций в Haskell настраивается таким образом чтобы частичное применение было удобным;

Prelude > let discount limit proc sum = if sum >= limit then sum * (100 - proc) / 100 else sum Prelude > let standardDiscount = discount 1000 5 Prelude > standardDiscount 2000 1900.0 Prelude > standardDiscount 900 900.0

Параметры limit и proc меняются редко. А вот параметр sum меняется часто. Фактически при каждом вызове этой функции.

Предположим, мы разрабатываем на Haskell интерфейс системы перевода для естественных языков. Он должен содержать функцию translate с параметрами text, languageFrom и languageTo. Для того чтобы было удобно реализовывать следующие функции:

translateFromSpanishToRussian,
translateFromEnglishToRussian
и translateToRussian

надо расположить параметры в таком порядке: translate languageTo languageFrom text.

Оператор над типами ->

Для того чтобы написать тип функции нужно написать тип её аргумента и тип результата этой функции. В Haskell для описания типа функции служит оператор -> это бинарный оператор у которого левый операнд это тип аргумента, а правый операнд это тип результата. Стрелочка находится между левым и правым операндом т,к, это инфиксный оператор.

Prelude > : t not not :: Bool -> Bool Prelude > (&& ) False True False Prelude > ((&& ) False ) True False

Тип последнего выражения может быть записан следующим образом:
Bool -> (Bool -> Bool)
Оператор над типами рассматривается как право-ассоциативный. Поэтому Bool -> (Bool -> Bool) можно переписать как Bool -> Bool -> Bool

Prelude > : t (&& ) (&& ) :: Bool -> Bool -> Bool

Вспомним функцию discount, которая возвращала итоговую сумму покупки с возможной скидкой. В качестве параметров ей передавались сумма без скидки sum, процент скидки proc, причем скидка начислялась, если переданная сумма превышает порог limit. Все эти параметры, как и возвращаемое значение, можно хранить в типе Double. Тип функции можно задать в файле исходного кода вместе с ее определением:

discount :: Double -> Double -> Double -> Double discount limit proc sum = if sum >= limit then sum * (100 - proc) / 100 else sum

Отметим, что объявление типа необязательно, хотя часто рекомендуется в качестве документации. Его обычно располагают перед определением функции, хотя это объявление верхнего уровня можно расположить в любом месте файла с исходным кодом.

StandardDiscount :: Double -> Double standardDiscount = discount 1000 5

Рассмотрим функцию twoDigits2Int, которая принимает два символа и возвращает число, составленное из этих символов, если оба символа числовые, и 100 в противном случае. (Первый символ рассматривается как количество десятков, второй — единиц.)

Import Data.Char twoDigits2Int :: Char -> Char -> Int twoDigits2Int x y = if isDigit x && isDigit y then digitToInt x * 10 + digitToInt y else 100

GHCi > twoDigits2Int "4" "2" 42

Рекурсия

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

вызовы функции в правой части должны осуществляться на значениях параметра отличного от формального параметра функции;
рекурсивные вызовы должны где-то прерываться (должно быть так называемое терминирующее условие).

Факториал

Factorial n = if n == 0 then 1 else n * factorial (n - 1 )

Реализация вычисления факториала с помощью аккумулирующего параметра:

Factorial5 n | n >= 0 = helper 1 n | otherwise = error "arg must be >= 0" helper acc 0 = acc helper acc n = helper (acc * n) (n - 1 )

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

Двойной факториал

Рассмотрим функцию, вычисляющую двойной факториал, то есть произведение натуральных чисел, не превосходящих заданного числа и имеющих ту же четность. Например: 7!!=7⋅5⋅3⋅1, 8!!=8⋅6⋅4⋅2. Предполагается, что аргумент функции может принимать только неотрицательные значения.

DoubleFact :: Integer -> Integer doubleFact n = if n <= 0 then 1 else n * doubleFact (n - 2 )

Последовательность чисел Фибоначчи

На Haskell данное определение задаётся следующей функцией:

Реализация функции для вычисления числа Фибоначчи, основанная на прямом рекурсивном определении, крайне неэффективна - количество вызовов функции растет экспоненциально с ростом значения аргумента. GHCi позволяет отслеживать использование памяти и затраты времени на вычисление выражения, для этого следует выполнить команду :set +s :

* Fibonacci > : set + s * Fibonacci > fibonacci 30 832040 (16.78 secs, 409 ,318 ,904 bytes)

С помощью механизма аккумуляторов можно написать более эффективную реализацию, имеющую линейную сложность (по числу рекурсивных вызовов):

Fibonacci" :: Integer -> Integer fibonacci" n = helper n 0 1 helper n a b | n == 0 = a | n > 0 = helper (n - 1 ) b (a + b) | n < 0 = helper (n + 1 ) b (a - b) | otherwise = undefined

Функции высших порядков

Функцией высших порядков называется функция, которая принимает в качестве аргумента другую функцию. В императивных языках функции высших порядков встречаются редко. В качестве примера можно привести функцию сортировки из стандартной библиотеки языка Си. В качестве первого аргумента в функцию сортировки передается бинарный предикат сравнения с помощью которого массив, который передается в качестве второго аргумента и сортируется. В функциональных языках и в Haskell функции высших порядков используются очень часто.

Prelude > : t ($ ) ($ ) :: (a -> b) -> a -> b

Это полиморфный тип. Оператор доллар представляет собой функцию двух аргументов. Его левый операнд или первый аргумент (a -> b) это функция. Его правый операнд a это значение произвольного типа. Оператор доллар просто применяет свой первый аргумент(a -> b) ко своему второму аргументуa . Поэтому здесь необходимо чтобы типы были согласованы. Тип второго аргумента оператора доллар должен совпадать с типом параметра функции, которая передается в первом аргументе. Более того результатом выполнения оператора доллар служит результат выполнения функции, которая передана в качестве первого аргумента. Поскольку тип результата это b то результатом выполнения оператора доллар служит тип b.

Следующее применение допустимо только когда a и b это одно и то же.

Prelude > let apply2 f x = f (f x) Prelude > : t apply2 apply2 :: (t -> t) -> t -> t Prelude > apply2 (+ 5 ) 22 32 Prelude > apply2 (++ "AB" ) "CD" "CDABAB"

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

Функция flip из стандартной библиотеки определена следующим образом: flip f y x = f x y.

Prelude > flip (/ ) 4 2 0.5 Prelude > (/ ) 4 2 2.0 Prelude > flip const 5 True True Prelude > : t flip flip :: (a -> b -> c) -> b -> a -> c Prelude > : t flip const flip const :: b -> c -> c

{- В модуле Data.Function определена полезная функция высшего порядка -} on :: (b -> b -> c) -> (a -> b) -> a -> a -> c on op f x y = f x `op` f y {- Она принимает четыре аргумента: 1) бинарный оператор с однотипными аргументами (типа b), 2) функцию f:: a -> b, возвращающую значение типа b, 3,4) и два значения типа a. Функция on применяет f дважды к двум значениям типа a и передает результат в бинарный оператор. Используя on можно, например, записать функцию суммирования квадратов аргументов так: -} sumSquares = (+ ) `on` (^ 2 ) {- Функция multSecond, перемножающая вторые элементы пар, реализована следующим образом -} multSecond = g `on` h g = (* ) h = snd

Анонимные функции

В Haskell как и в математике функции обычно именованы. Когда нам нужно вызвать какую-нибудь функцию мы обращаемся к ней по имени. Однако есть и альтернативный подход, который называется анонимные функции.

Prelude > (\ x -> 2 * x + 7 ) 10 27 Prelude > let f" = (\ x -> 2 * x + 7 ) Prelude > f" 10 27

Это анонимная функция или лямбда-функция.

Существует синтаксический сахар упрощения записи.

Prelude > let lenVec x y = sqrt $ x^ 2 + y^ 2 Prelude > let lenVec x = \ y -> sqrt $ x^ 2 + y^ 2 Prelude > let lenVec = \ x -> \ y -> sqrt $ x^ 2 + y^ 2 Prelude > lenVec 3 4 5.0 Prelude > let lenVec = \ x y -> sqrt $ x^ 2 + y^ 2 Prelude > lenVec 3 4 5.0

Анонимные функции применяются в использовании функций высших порядков.

{- Функция on3, имеет семантику, схожую с on, но принимает в качестве первого аргумента трехместную функцию -} on3 :: (b -> b -> b -> c) -> (a -> b) -> a -> a -> a -> c on3 op f x y z = op (f x) (f y) (f z) {- Сумма квадратов трех чисел может быть записана с использованием on3 так -} sum3squares = (\ x y z -> x+ y+ z) `on3` (^ 2 )

Каррированные и некаррированные функции

При синтаксисе вызова функций в Haskell можно перечислить не все аргументы, а только их часть. Несколько первых аргументов функции можно указать, а остальные отбросить. Эта идея частичного применения функций была придумана Хаскеллом Карри и в честь него такие функции с аргументами передающимися по одному называют каррированными. В Haskell не все функции являются каррированными. В Haskell можно определять функции над кортежами. В этом случае синтаксис вызова функций будет выглядеть также как в обычных языках:
имя_функции (первый_аргумент, второй_аргумент)

Prelude > fst (1 ,2 ) 1

Каррирование - процедура перехода от некаррированных функций к функциям, которые принимают аргументы по одному. Представьте, что у нас есть функция высшего порядка, например комбинатор on, он ожидает в качестве 2 из своих 4 аргументов функции. Первый аргумент это функция двух аргументов, которая является каррированной. В языке Haskell есть специальный комбинатор curry, который выполняет переход от некаррированной функции к каррированной. В следующем примере curry превращает функцию заданную над парой в стандартную каррированную функцию двух аргументов.

* Demo > : t on on :: (b -> b -> c) -> (a -> b) -> a -> a -> c * Demo > : t curry fst `on` (^ 2 ) curry fst `on` (^ 2 ) :: Num b => b -> b -> b

Еще пример, некаррированная функция avg:

Avg :: (Double ,Double ) -> Double avg p = (fst p + snd p) / 2

Функция curry avg `on` (^2) это функция, которая вычисляет среднее значение квадратов двух переданных в неё значений.

Устройство функции curry:

Prelude > let cur f x y = f (x,y) Prelude > : t cur cur :: ((t1, t2) -> t) -> t1 -> t2 -> t Prelude > : t curry curry :: ((a, b) -> c) -> a -> b -> c

В качестве первого аргумента она принимает некаррированную функцию, т.е. функцию над парой, а превращает её в качестве возвращаемого значения в каррированную функцию в которую аргумента передаются последовательно.

Есть и обратная функция uncurry:

Prelude > : t uncurry uncurry :: (a -> Prelude > : t uncurry (flip const) uncurry (flip const) :: (b, c) -> c Prelude > : t snd snd :: (a, b) -> b

В модуле Data.Tuple стандартной библиотеки определена функция swap:: (a,b) -> (b,a), переставляющая местами элементы пары:

GHCi > swap (1 ,"A" ) ("A" ,1 )

Эта функция может быть выражена в виде:

Prelude > let swap = uncurry (flip (,)) Prelude > swap (1 ,"A" ) ("A" ,1 )

Строгие и нестрогие функции

Ленивые вычисления приводят к тому что во многих ситуациях можно элиминировать незавершаемость программ.

Const42 :: a -> Int const42 = const 42

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

* Demo > const42 True 42 * Demo > const42 123 42 * Demo > const42 (1 + 3 ) 42 * Demo > const42 undefined 42

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

Рефакторинге, TDD, багтрекерах, и даже (наконец-то!) о моем любимом Haskell. К сожалению, тема «чем же так хорош этот ваш Haskell» не была в должной мере раскрыта. Такое чувство, что большинство айтишников действительно не понимают плюсов функционального программирования. В этой заметке я постарался развернуто описать, за что лично мне нравится Haskell.

Как обычно, я не ставлю перед собой цели кого-то в чем-то убедить или что-то доказать. К тому же, я не претендую на знание истины и по поводу некоторых моментов вполне могу заблуждаться. Соглашаться с написанным или нет — дело ваше. Несмотря на то, что пункты пронумерованы, они никаким образом не отсортированы. Другими словами, нет такого, что первый пункт важнее пятого или вроде того.

1. Красота и декларативность языка

Будучи вещью субъективной и не имеющей строгого определения, «красота языка программирования» является прекрасной темой для холиваров. Потому скажу так — лично мне Haskell кажется очень красивым языком. Некоторые считают, что Haskell сложен, но на самом деле это не так. Одной из причин, по которым мне нравится Haskell, является простое и логичное ядро языка.

Грустный и несчастный Java-программист, который вынужден писать всякие private static final transient volatile List> dramaticallyTerribleList = new ArrayList>; когда где-то совсем рядом есть чудесный Haskell // «о себе» одного хабраюзера

Приведу немного цифр. Описание языка в «Справочнике по языку Haskell» Романа Душкина занимает всего лишь 100 страниц. Остальные 430 страниц занимает описание модулей, которое мне еще ни разу не понадобилось. Объем книги Learn You a Haskell for Great Good! (кстати, скоро будет издан русский перевод) составляет 400 страниц. Лично мне кажется, что при желании ее можно ужать вдвое, ничего при этом не потеряв. Для сравнения, Язык программирования Си Кернигана и Ритчи имеет объем 300 страниц, а Язык программирования C++ Страуструпа — почти 1100 страниц. Вы действительно считаете сложным язык, описание которого даже по самым скромным оценкам имеет примерно тот же объем, что и описание языка Си, которое в свою очередь в 3-4 раза короче описания языка C++ ?

Тут самое время привести немного кода, продемонстрировав, как любят выражаться некоторые программисты, «высокую декларативность» языка. Например, вот так задается функция, возвращающая список делителей некого числа num:

getDivisors num
| num < 1 =
| otherwise = [ x | x <- [ 1 .. num] , num `mod ` x == 0 ]
-- ^ очевидная оптимизация -

Прямо как написать определение! Если обозначить множество делителей числа n, как D(n), и перевести написанное выше на язык математики, то получим D(n) = { x | x ∈ ℤ + , x ≤ n, mod(n, x) = 0 } , где n ∈ ℤ + . А теперь давайте напишем функцию проверки числа на простоту:

isPrime num
| num <= 1 = False
| otherwise = getDivisors num == [ 1 , num]

И снова — как будто пишешь математическую формулу. Теперь получим список всех простых чисел:

allPrimeNumbers = [ 2 ] ++ filter isPrime [ 3 , 5 .. ]

Да, Haskell умеет работать с бесконечными списками. Это возможно благодаря механизму ленивых вычислений . То есть, ни один из элементов списка простых чисел не будет вычислен до тех пор, пока он на самом деле не будет где-то использован. Помимо удобства, ленивые вычисления позволяют писать более быстрые программы , о чем еще будет рассказано в соответствующем пункте.

Если думаете, что «высокая декларативность» Haskell распространяется только на математические задачи, то вы ошибаетесь. Посмотрите, к примеру, как выглядит код GUI-приложения на Haskell . Или как к базе данных с помощью библиотеки HaskellDB. Фактически, в запросе используется обычная реляционная алгебра. Преимущество перед SQL здесь заключается в том, что корректность запроса проверяется на этапе компиляции программы. Впрочем, если хотите писать запросы на обычном SQL , никто не будет вам препятствовать.

А еще борцы против оператора goto будут рады узнать, что в Haskell его нет.

2. Автоматическое управление памятью

Haskell полностью берет управление памятью на себя. Цитата из WikiBooks :

Функциональные языки освобождают программиста от этой непростой обязанности. Память выделяется неявно, автоматически, а специальный сборщик мусора (garbage collector) возвращает системе неиспользуемые куски памяти. Оптимальные алгоритмы управления памятью сложны, но сегодня уже достаточно хорошо проработаны. Использование этих алгоритмов не сильно увеличивают время работы программы в целом (в сравнении с тем, когда программист сам, по-умному, занимается выделением и освобождением памяти).

Тем самым в программах на Haskell гарантируется отсутствие таких сложных в обнаружении ошибок, как переполнение буфера, пустой указатель, неинициализированные данные и утечки памяти. Считается, что многие люди испытывают трудности при работе с указателями, так что полностью избавиться от них, видимо, неплохая идея.

Кстати, далеко не все из перечисленных проблем по-настоящему решены в таких высокоуровневых языках, как Java, Perl и Python (о проблемах C++ я вообще молчу). Например, в книге Дэвида Бизли приводится пример программы (в моем экземпляре — на стр 174), использующей паттерн «наблюдатель» , в которой сборщик мусора не в состоянии освободить память, если только не воспользоваться weakptr.

Люди, 21-ый век на дворе! Будем еще 90 лет управлять памятью с помощью костылей типа счетчиков ссылок и weakptr, а то и вообще вручную? Или наконец забудем, как страшный сон, и будем двигаться дальше?

3. Чистые функции

Функция называется детерминированной , если возвращаемое ею значение зависит только от аргументов. Говорят, что функция не имеет побочных эффектов , если при ее вызове не производится запись в файл, чтение из сокета, изменение глобальных переменных и так далее. Функция называется чистой , если она является детерминированной и не имеет побочных эффектов.

В Haskell горячо приветствуется написание чистых функций. Сколько бы мы не передавали функции одни и те же аргументы, она все время будет возвращать один результат. Кроме того, мы можем быть уверены, что при вызове чистой функции не происходит запись в файл или передача каких-то данных по сети. Это существенно упрощает разработку программ.

Вот что написано в книге Роберта Мартина Чистый код — создание, анализ и рефакторинг по поводу побочных эффектов:

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

Но неужели Haskell обходится без чтения из файлов, работы с сетью и пользовательского ввода? Ведь это все — побочные эффекты. Следовательно, соответствующие действия не могут производиться в чистых функциях.

Дело в том, что в Haskell функции поделены на чистые и «грязные», то есть недетерминированные и имеющие побочные эффекты. «Грязные» функции используются для ввода данных, передачи их в чистые функции и вывода результата. Другими словами, существует эдакий небольшой процедурный мирок внутри чистого функционального языка. Или наоборот, это еще как посмотреть. Все гениальное — просто!

4. Быстродействие

Повторюсь на счет ленивых вычислений. В Haskell что-то начинает вычисляться только тогда, когда оно действительно понадобится. Вы можете объявить список из 9000 элементов, но если вам понадобятся только один из них (и он не будет зависеть от других элементов списка), то будет вычислено значение только этого одного элемента. И этот принцип работает везде , а не только в списках. В каком-нибудь C++ такое тоже можно сделать, но придется самому написать соответствующий код или подключить какую-нибудь библиотеку, а в Haskell все уже есть «из коробки».

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

Рассмотрим другой пример. Допустим, у нас есть некая функция f(a, b) . Пусть аргументы a и b — результаты вычислений неких других функций, которые по счастливому стечению обстоятельств являются чистыми. В этом случае a и b могут быть вычислены параллельно! Согласитесь, в эпоху многоядерных процессоров это немаловажно. В ООП языках такую оптимизацию провести намного сложнее.

Кроме того, что мы получаем прирост производительности, мы также автоматически распараллеливаем программу и синхронизируем потоки выполнения! А ведь многопоточное программирование с его дэдлоками — это чуть ли не вторая по важности проблема современного программирования после ручного управления памятью. Если вы думаете, что описанное выше — лишь теория, посмотрите список расширений компилятора GHC и проект Data Parallel Haskell . Все уже реализовано!

Дополнение: См также проект Haskell STM . Транзакционная память интересна тем, что позволяет избавиться от блокировок в многопоточных приложениях.

К сожалению, мне не удалось найти ни одного бэнчмарка программ на Haskell, кроме shootout.alioth.debian.org . «К сожалению» — потому что у меня к этому бенчмарку много вопросов . Я отказываюсь верить, что программы на Pascal выполняются в 2 раза медленнее программ на Си. Также вызывают сомнения погрешности в стиле ±100% для скриптовых языков. Тем не менее, если верить этому бенчмарку, Haskell на сегодняшний день является самым быстрым языком функционального программирования. По скорости он сравним с языками Java и C#.

5. Меньше рефакторинга

Давайте откроем оглавление книги Рефакторинг — улучшение существующего кода Фаулера и посмотрим, какие типы рефакторинга бывают. Выделение метода, встраивание метода, перемещение метода, встраивание временной переменной, замена временной переменной вызовом метода, введение пояснительной переменной, расщепление временной переменной, замена ссылки значением, замена значения ссылкой… как считаете, многое ли из перечисленного применимо в Haskell при условии, что в этом языке нет ни ссылок, ни переменных (let и where не считаются)?

Недавно я провел на Хабре два опроса, один — в блоге «Java», второй — в блоге «Haskell». Вопрос был одним и тем же — «Как часто вам приходится производить рефакторинг кода на %PROGRAMMING_LANGUAGE%?». На этих опросах я слил почти всю свою карму (кому-то правда глаза режет?), но оно того стоило:

Я готов признать, что часть опрошенных могла ответить, что не занимается рефакторингом на Haskell, потому что не пишет на нем, но едва ли это сильно исказило картину. Во-первых , в опросах есть кнопочка «воздержаться», а во-вторых , вероятно, среди читателей блога «Java» также далеко не все пишут на Java .

Что интересно, сам синтаксис Haskell подталкивает к написанию кода, состоящего из большого количества простых функций. Это связано с тем, что код на Haskell очень любит разрастаться в ширину экрана, а не в высоту, как в ООП языках. Кроме того, если внутри конструкции if-then-else требуется нечто большее, чем просто вернуть значение, то вместо if-then-else намного удобнее определить новую функцию. В действительности, благодаря сопоставлению с образцами и охране , на Haskell можно писать вообще без использования конструкции if-then-else.

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

6. А нужны ли TDD и UML?

Вспомним, чему нас учит любой учебник по Python или Java. Все является объектом. Используйте объекты, и ваш код станет намного легче сопровождать, расширять и повторно использовать. Уверуйте и покайтесь! Вот, правда, чтобы сопровождать код, извольте составить диаграммы классов, иначе в нем будет невозможно разобраться. И обязательно напишите тесты, покрывающие как можно бо льшую часть кода, иначе любое его изменение сделает вашу программу нерабочей. Прошу вопросы. Да, пожалуйста. Что-что, простите? В каком это смысле «всего лишь надстройка над процедурным программированием »?! Вы что, не слушали? Инкапсуляция, наследование, полиморфизм!

Нет, правда, вы никогда не задумывались, сколько нужно использовать костылей, чтобы ООП работало? Скачайте хотя бы уже упомянутый 253-ий выпуск Radio-T и послушайте, что там говорят о TDD . Фактически, нам предлагают делать в два, а то и в три раза (считая UML) больше работы!

Люди иногда спрашивают, «Что служит аналогом UML для Haskell?». Когда меня впервые спросили об этом 10 лет назад, я подумал, «Ума не приложу. Может быть, нам стоит придумать свой UML». Сейчас я думаю, «Это просто типы!». // Саймон Пейтон Джонс

При этом обычно умалчивается, что далеко не любая задача легко вписывается в рамки ООП. Фактически, ООП неплохо себя зарекомендовало только в игростроении, создании GUI и графических редакторов. Зайдите, к примеру, на CPAN . Возьмите 10 случайных модулей и посмотрите, сколько из них действительно используют ООП (да, в Perl есть ООП), а не просто оформляют модуль в виде класса. Или загляните на Hackage и посчитайте, сколько модулей вполне успешно решают практические задачи вообще без единого намека на ООП.

Примечание: В действительности, функциональным языкам вовсе не чужды инкапсуляция, наследование и полиморфизм. Например, в Haskell инкапсуляция производится на уровне модулей, полиморфизм обеспечивается благодаря классам типов, а наследование существует в чистом виде . О применении идиом ООП на языке Haskell можно прочитать в четвертой главе книги 14 занимательных эссе о языке Haskell и функциональном программировании .

Почему мне кажется, что «костылей» должно быть меньше при использовании Haskell? Ну, во-первых, раз нет классов (не путать с классами типов ) — не нужно рисовать их диаграммы:) Теоретически ничто не мешает рисовать диаграммы классов типов, но лично мне такие еще ни разу не попадались. Во-вторых, как мы уже выяснили, Haskell — «очень декларативный» язык. То есть, обычно мы пишем на нем, что хотим получить, а не как . Таким образом, программа документирует сама себя. И в-третьих, строгая статическая типизация языка позволяет ликвидировать целые классы ошибок еще на этапе компиляции программы. Это не отменяет необходимость временами писать тесты, но существенно сокращает их количество.

Кстати, важными свойствами Haskell являются отсутствие побочных эффектов и кроссплатформенность языка, притом настоящая кроссплатформенность, а не как у C++. Программа, написанная один раз, одинаково хорошо работает под любой ОС и любой архитектурой процессора без необходимости писать какие-то макросы или вроде того. Это приводит к тому, что программисты на Haskell часто (!) вообще не компилируют свои программы.

Знаю, звучит нелепо. Сам не верил, пока не попробовал. Это выглядит примерно так. Создаем новый модуль. Вводим пару новых типов, объявляем первую функцию. Запускаем интерпретатор ghci, проверяем функцию на типичных данных и паре краевых случаев. Если работает — забываем про только что написанную функцию и пишем следующую. Когда весь необходимый функционал реализован, смотрим, какие сущности следует экспортировать из модуля и вносим соответствующие правки. Все, работа выполнена! Без единой компиляции. Если программа заработала в ghci, то ее правильно соберет любой компилятор Haskell, под любую платформу. Вот, что такое настоящая кроссплатформенность.

7. Широкая область применения

Распространенное заблуждение в отношении Haskell заключается в том, что этот язык якобы пригоден для решения только узкого круга хитроумных математических задач. И действительно, как прикажете решать «обычные» задачи, если у нас даже циклов нет? На самом деле, рекурсия ничем не хуже циклов. Думать итерациями или думать рекурсиями — это всего лишь дело привычки. И нет, рекурсия совсем не обязательно должна использовать какую-то память. Вообще-то , именно злоупотребление ООП в конечном счете приводит к мышлению по шаблону, и выводам в стиле «видимо, эта задачка с олимпиады по спортивному программированию , раз я не знаю, как ее решить».

Однако вернемся к области применения. Как я уже отмечал, Haskell прекрасно подходит для написания GUI приложений . Писать на нем для веб я еще не пробовал, но, судя по отзывам, Haskell и тут справляется не хуже PHP:

Я только что закончил написание простенькой FastCGI программы на Haskell. Мне хотелось понять, как работают веб-приложения на Haskell и подходит ли этот язык для создания сайта, посвященного изучению языков. Haskell не только справился с задачей. Оказалось, что писать на нем намного веселее, чем на PHP // jekor.com . На Haskell можно писать даже.

В заключение , мне хотелось бы поблагодарить Романа Душкина за помощь в написании заметки. Благодаря ему, текст был существенно улучшен, а также обогащен интересными фактами о мире функционального программирования.

Надеюсь, заметка показалась вам интересной. Как обычно, я буду рад любым комментариям и вопросам читателей.

Дополнение: Книгу «Learn You a Haskell for Great Good!» в русском переводе уже можно заказать в интернет-магазинах . Также на просторах интернета была найдена годная книга Антона Холомьёва «Учебник по Haskell» . Если у вас «нет времени» на изучение Haskell, попробуйте ознакомиться с учебником Макеева Григория , в нем всего лишь 114 страниц.

Теоретические основы императивного программирования были заложены ещё в 30-х годах XX века Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, формировалась в 20-х и 30-х годах. В числе разработчиков математических основ функционального программирования - Мозес Шёнфинкель (Германия и Россия) и Хаскелл Карри (Англия), а также Алонзо Чёрч (США). Шёнфинкель и Карри заложили основы комбинаторной логики, а Чёрч является создателем лямбда-исчисления.

Функциональное программирование как раз основано на идеях из комбинаторной логики и лямбда-исчисления.

Но теория так и оставалась теорией, пока в начале 50-х прошлого века Джон МакКарти не разработал язык Lisp (1958), который стал первым почти функциональным языком программирования. На протяжении многих лет у Lisp не было конкурентов. Позднее появились функциональные языки программирования APL (1964), ISWIM (1966) и FP (1977), которые не получили столь широкого распространения.

Со временем Lisp перестал удовлетворять некоторым требованиям разработчиков программ, особенно с ростом объема и сложности программного кода. В связи с этим обстоятельством всё большую роль стала играть типизация. В конце 70-х - начале 80-х годов XX века интенсивно разрабатывались модели типизации, подходящие для функциональных языков.

Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм. Появилось множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивалось число диалектов.

ML (1973) – первый язык с типизацией Хиндли–Милнера;
Scheme (1975) - это один из двух самых популярных диалектов языка Lisp;
SASL, KRC, Miranda (1972–1985) – одни из первых ленивых языков;
Hope (1980) – один из первых языков с алгебраическими типами данных.

Хаскелл Карри

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

История языка Haskell начинается в 1987 году. Один за другим появлялись новые функциональные языки программирования. После выхода Miranda (Research Software Ltd, 1985 год) возрос интерес к ленивым вычислениям: к 1987 году возникло более дюжины нестрогих чисто функциональных языков программирования.

Miranda использовался наиболее широко, но это было запантетованное ПО. На конференции по функциональным языкам программирования и компьютерной архитектуре (FPCA, 1987) в Портленде (Орегон) участники пришли к соглашению, что должен быть создан комитет для определения открытого стандарта для подобных языков. Целью комитета являлось объединение существующих функциональных языков в один общий, который бы предоставлял базис для будущих исследований в разработке функциональных языков программирования.

Так появился Haskell. Он был назван в честь одного из основателей комбинаторной логики Хаскела Кaрри (Haskell Curry).

К концу 1980-х годов было создано много функциональных языков. Часть из них оказали значительное влияние на Haskell:

Новый язык должен был стать свободным языком, пригодным для исследовательской деятельности и решения практических задач. Свободные языки основаны на стандарте, который формулируется комитетом разработчиков. Дальше любой желающий может заняться реализацией стандарта, написать компилятор языка. Первая версия стандарта Haskell была опубликована 1 апреля 1990 года.

Haskell 1.0 - 1.4

Первая версия Haskell (Haskell 1.0) была выпущена в 1990г. Попытки комитета вылились в серию реализаций языка (1.0, 1.1, 1.2, 1.3, 1.4).

Haskell 98

В конце 1997 года версии Haskell 98 необходимо было специфицировать в одну стабильную, минимальную и портативную версию языка и сопроводительную стандартную библиотеку для изучения, как основу будущего развития. Комитет положительным образом принял создание расширений и вариаций haskell 98 путем добавления и внедрения экспериментальных особенностей.

В феврале 1999 года стандарт языка Haskell 98 впервые был опубликован, как «The Haskell 98 Report». В январе 2003 года измененная версия была опубликована как «Haskell 98 Language and Libraries: The Revised Report». Язык продолжил стремительно развиваться, реализация компилятора Glasgow Haskell Compiler (GHC) представляет фактический стандарт языка.

Haskell 2010

Современный стандарт Haskell - Haskell 2010 - был анонсирован 24 ноября 2009 года; GHC поддерживает его с версии 7.0.1.

По сравнению с Haskell "98 он содержал следующие изменения:

Do и If Then Else
Иерархические модули
Объявления пустых переменных
Решение устойчивости
Интерфейс сторонних функций
Линейный синтаксис комментариев
Охраняющие паттерны
Облегченных анализ зависимостей
Указания для языка (pragma)
Отсутствие паттернов n+k

Отсутствие контекста типов данных
Маркированные списки переменных

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

От создателя Haskell

Curry - встраиваемый язык программирования общего назначения, реализованный поверх языка Haskell. Язык Curry плавно соединяет в себе возможности функционального программирования (вложенные выражения, функции высших порядков, ленивые вычисления), логического программирования (логические переменные, частичные структуры данных, встроенная система поиска) и методов программирования для параллельных систем (параллельное вычисление выражений с синхронизацией по логическим переменным).
Более того, язык Curry предоставляет дополнительные механизмы по сравнению с чистыми языками программирования (по сравнению с функциональными языками - поиск и вычисления по неполным данным, по сравнению с логическими языками - более эффективный механизм вычислений благодаря детерминизму и вызову по необходимости для функций).

Facebook

Фильтрация спама - одна из самых главных задач, которую решают инженеры Facebook. Крупнейшая социальная сеть обрабатывает сообщения от более 1,5 миллиарда человек, так что можно оценить масштаб проблемы. В 2015 году компания внедрила новые антиспамерские фильтры, для разработки которых использовала язык программирования Haskell.

Несмотря на молодость, экспериментальный статус и относительно низкую популярность, Facebook выбрал именно Haskell для создания важного модуля. Один из инженеров Луис Брэнди (Louis Brandy), который входит в группу разработчиков нового антиспамерского фильтра, провел два года за этим проектом вместе с коллегами. В интервью Wired он объяснил, чем они руководствовались.

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

Если посмотреть на развитие современного интернета, то по этому пути должны пойти многие интернет-проекты, для которых важны масштабируемость и реагирование в реальном времени. По мнению разработчиков Facebook, у языка Haskell есть все шансы на широкую популярность. Мешает только тот факт, что Haskell довольно сильно отличается от других языков - и это затрудняет массовую миграцию на него.

Тем не менее, индустрия точно двигается в нужном направлении, как показывает пример новых языков программирования, ориентированных на выполнение параллельных процессов, например, Go от Google и Rust от Mozilla. Пусть они не такие эффективные, как Haskell, зато проще в изучении. В любом случае, Haskell можно поблагодарить за то, что он подтолкнул к развитию другие языки программирования и способствовал запуску новых перспективных проектов.

Евгений Козлов в своем блоге рассказал о впечатлениях от работы с Haskell:

Недостатки

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

Положительные стороны

В первую очередь, конечно же чистота языка. Чистота в обоих смыслах: чистота функций и полное отсутствие ООП-парадигмы. Это очень здорово, что ты можешь посмотреть на сигнатуру функции и понять, может ли она производить побочные эффекты или нет. Отсутствие ООП означает, что нет возможности сделать страшные вещи вроде непроверенных приведений из базового класса в подкласс.
Если написан код, то его сложно интерпретировать двумя способами. Например, нельзя перепутать применение функции и ссылку на функцию, как в Scala, так как в Haskell функции являются объектами первого класса. Или, например, нельзя перепутать функцию с типом или классом, так как все функции должны начинаться с маленькой буквы, а типы/классы – с большой.
Свойство языка, без которого разговор о Haskell был бы бессмысленным – это полиморфизм. Вряд ли будет преувеличением, если я скажу, что Haskell является языком с максимальным количеством переиспользованного кода. Любая хоть сколько-нибудь повторяющаяся функциональность выносится в абстракцию.