В 1985 году был разработан первый полностью функциональный язык, названный Мирандой (предшественником его был Lisp, который нельзя считать чисто функциональным). Он был очень популярен в среде программистов, однако, к сожалению, принадлежал только одной компании. Поэтому его дальнейшее развитие было сильно ограничено, что привело к возникновению множества похожих на него независимых языков. В 1987 в Орегоне был собран комитет, состоящий из энтузиастов функционального программирования, который постановил, что им необходим единый язык, который бы сосредоточил в себе лучшие достижения ФП за последние годы. В результате этого в 1990 году вышла первая версия, названная по имени Хаскелла Карри, известного математика. В 1999 был опубликован стандарт языка, а компилятор GHC, разработанный в университете Глазго стал самой известной реализацией языка (кстати, GHC, примерно на 80 % написан на самом хаскелле).

Философия языка Haskell

Haskell, мягко говоря, не похож на большинство своих объектно-ориентированных собратьев. Например, здесь нет привычных операторов присваивания значения переменной (вообще, переменных тоже нет) или циклов (вместо циклов используется рекурсия). А ещё, он с самого начала поддерживал такие вещи, как лямбда-исчисления, нестрогую семантику, монадическую систему. Некоторые элементы из этого (лямбда-выражения, которые происходят от лямбда-исчислений) только недавно внедрили в такие языки, как Java, Python или JavaScript.

Особо стоить отметить так называемые ленивые (отложенные) вычисления. Суть их сводится к тому, что вычисления не производятся, пока они не будут необходимы. Так, например, если мы определили некоторые выражения (пусть будут две разных суммы чисел или два разных произведения), то они не будут вычислены до тех пор, пока их не потребуется сравнить между собой или произвести с ними другие операции. Отсюда же происходит и другая потрясающая возможность Haskell - манипулирование бесконечными последовательностями (списками). Если на объектно ориентированном языке попробовать работать с такими данными, то получим просто переполнение памяти. А ленивые вычисления позволяют получать только необходимые элементы из этих списков, поэтому программа на хаскелле будет иметь большое преимущество перед другими. Например, в задачах по сортировке данных. Это также позволяет сокращать число шагов выполнения и экономить ресурсы оперативной памяти и решить проблему распараллеливания программы не прикладывая никаких усилий.

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

Где применяется Haskell

Haskell некоторое время назад был известен только в сфере фанатов математики и функционального программирования, однако, вопреки слухам, это уже давно не так. Сейчас его используют в Facebook для фильтров спама и он успешно справляется со своей задачей. Возможности Хаскель изучали специалисты в Microsoft Research, в результате чего появилась урезанная версии языка, названная F#, которая сейчас доступна в Visual Studio.

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

Haskell также хорошо подходит для создания оконных приложений (GUI). Можно найти сделанные на Haskell текстовые редакторы, оконные менеджеры, торрент-клиенты, игры (шутеры и логические), браузеры, движки для рендеринга 3D и.т.д. Уже существуют веб-фреймворки на нем, а также приложения для работы с базами данных. Также известен инструмент для криптографии под названии Cryptol и система управления версиями Darcs.

Сложность обучения Haskell

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

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

Плюсы/минусы Haskell

Плюсы Хаскелля - это его красота и лаконичность. Программы на Haskell проще читать и понимать (даже не зная некоторых деталей языка). Его синтаксис защищает программиста от типичных ошибок. На нем проще спроектировать и создать даже большие сложные программы. И он лишен многих типичных проблемы других языков.

Из минусов:

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

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

Сопутствующие технологии

GHC - самый популярный, на сегодняшний день, компилятор для хаскелля.

Snap, Yesod, Happstack - фреймворки, предназначенные для веб-разработки.

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

Bluespec SystemVerilog - расширение для хаскелля, применяется для проектирования полупроводниковых схем.

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

Большинство современных функциональных языков так же предоставляют некоторые гарантии касательно программ. В частности, 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.

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

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

Несмотря на то, что он не соответствует одному из ваших больших критериев (статический * ввод), я собираюсь сделать дело для Python. Вот несколько причин, по которым я думаю, вам стоит взглянуть на это:

• Для императивного языка это удивительно функционально. Это было одно из того, что меня поразило, когда я узнал об этом. Например, обратите внимание на списки . Он имеет лямбды, первоклассные функции и множество функционально вдохновленных композиций на итераторах (карты, складки, молнии...). Это дает вам возможность выбрать любую парадигму, которая лучше всего подходит для этой проблемы.
• ИМХО, это, как и Haskell, красиво кодировать. Синтаксис прост и элегантен.
• У этого есть культура, которая сосредотачивается на том, чтобы делать вещи прямолинейно, вместо того, чтобы сосредотачиваться слишком аккуратно на эффективности.

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

* Я предполагаю, что вы подразумеваете статическую типизацию здесь, так как вы хотите объявить типы. Techincally, Python - это строго типизированный язык, поскольку вы не можете произвольно интерпретировать, скажем, строку как число. Интересно, что существуют производные Python, которые позволяют статическую типизацию, например Boo .

2018-12-04T00:00Z

Если вам нужен сильный (эр) личный пролог, Mercury - интересный выбор. В прошлом я занимался этим, и мне нравилась другая перспектива, которую он мне дал. Он также имеет moded-ness (какие параметры должны быть свободными / фиксированными) и детерминизм (сколько результатов есть?) В системе типов.

Clean очень похожа на Haskell, но имеет уникальную типизацию, которая используется как альтернатива Monads (более конкретно, монада IO). Уникальность ввода также делает интересный материал для работы с массивами.

2018-12-11T00:00Z

Поскольку вы не указали никаких ограничений, кроме своих субъективных интересов, и подчеркиваете «вознаграждение учиться» (хорошо, хорошо, я проигнорирую ограничение статического набора текста), я бы предложил изучить несколько языков различных парадигм и, предпочтительно, те, которые являются «образцовыми» для каждого из них.

• Липский диалект для кода-данных-данных / гомоконичности и потому что они являются хорошими, если не лучшими, примерами динамических (более или менее строгих) языков функционального программирования
• Пролог как преобладающий логический язык программирования
• Smalltalk как единственный истинный язык ООП (также интересный из-за его обычно чрезвычайно ориентированного на изображение подхода)
• возможно, Erlang или Clojure, если вас интересуют языки, выкованные для параллельного / параллельного / распределенного программирования
• Форвард для программирования, ориентированного на стек
• (Haskell для строгого функционального статически типизированного ленивого программирования)

Особенно Lisps (CL не так много, как Scheme) и Prolog (и Haskell) охватывают рекурсию.

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

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

2018-12-18T00:00Z

С точки зрения того, что подходит вашему майору, очевидный выбор кажется логическим языком, таким как Prolog или его производные. Логическое программирование может быть сделано очень аккуратно на функциональном языке (см., Например, The Reasoned Schemer), но вам может понравиться работать с логической парадигмой напрямую.

Интерактивная теоретическая система доказательства, такая как twelf или coq, может также поразить вашу фантазию.

2018-12-25T00:00Z

Я хотел бы расширить свои знания в области программирования. (...) Я думал, что поставил бы здесь вопрос, а также несколько положений о типе языка, который я ищу. Некоторые из них субъективны, некоторые из них предназначены для облегчения перехода от Haskell.

Сильная система типов. (...) Он также делает неформальные рассуждения о правильности моей программы более легкими. Меня беспокоит правильность, а не эффективность.

Акцент на рекурсии, а не на итерации. (...)

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

Не обращайте внимания на практичность и отправляйтесь на «больше Haskell, чем Haskell» : система типа Haskell полна дыр, из-за прекращения и других беспорядочных компромиссов. Очистите беспорядок и добавьте более мощные функции, и вы получите такие языки, как Coq и Agda , где тип функции содержит доказательство ее правильности (вы можете даже читать функцию arrow -> как логическую импликацию!). Эти языки использовались для математических доказательств и для программ с чрезвычайно высокими требованиями к правильности. Coq, вероятно, является самым выдающимся языком стиля, но у Agda больше чувство Haskell-y (а также написано в Haskell).

Не учитывайте типы, добавляйте больше магии : если Haskell - колдовство, Lisp - это сырая первобытная магия творения. Языки семейства Lisp (включая Scheme and Clojure ) обладают почти беспрецедентной гибкостью в сочетании с экстремальным минимализмом. Языки по существу не имеют синтаксиса, написание кода непосредственно в виде структуры данных дерева; метапрограммирование в Lisp проще, чем не-мета-программирование на некоторых языках.

Компромисс немного и приближайтесь к мейнстриму : Haskell попадает в широкую семью языков, сильно влияющих на ML, любой из которых вы, вероятно, могли бы перейти без особых трудностей. Haskell является одним из самых строгих, когда речь заходит о гарантиях правильности от типов и использования функционального стиля, где другие часто являются либо гибридными стилями, либо / или делают прагматические компромиссы по разным причинам. Если вы хотите подвергнуть ООП и доступ к множеству основных технологических платформ, либо Scala на JVM, либо F # на.NET имеет много общего с Haskell, обеспечивая легкую совместимость с платформами Java и.NET. F # поддерживается непосредственно Microsoft, но имеет некоторые досадные ограничения по сравнению с Haskell и проблемами переносимости на платформах, отличных от Windows. У Scala есть прямые аналоги с системой типов Haskell и кросс-платформенным потенциалом Java, но она имеет более тяжелый синтаксис и не обладает мощной поддержкой сторонних разработчиков, которой пользуется F #.

На 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 )

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

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

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

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

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

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 )

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

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

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

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

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

Fibonacci :: Integer -> Integer fibonacci n | n == 0 = 0 | n == 1 = 1 | n > 1 = fibonacci (n - 1 ) + fibonacci (n - 2 ) | n < 0 = fibonacci (n + 2 ) - fibonacci (n + 1 ) | otherwise = undefined

Реализация функции для вычисления числа Фибоначчи, основанная на прямом рекурсивном определении, крайне неэффективна - количество вызовов функции растет экспоненциально с ростом значения аргумента. 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

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

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

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

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 )

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

Prelude > fst (1 ,2 ) 1

* 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 :: (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 очень эффективной.

• Tutorial

Привет Habr! Сегодня я достал свои старые конспекты по курсу «Haskell как первый язык программирования» Сергея Михайловича Абрамова и попробую максимально доходчиво и с примерами рассказать об этом замечательном языке тем, кто с ним еще не знаком. Рассказ ориентирован на неподготовленного читателя. Так что, даже если вы впервые услышали слово Haskell…

Базовые типы Haskell

Числа
Целые:
Integer (-∞,∞)
Int (-2^31, 2^31-1)
В прелюдии (стандартной библиотеке) определенно много полезных функций для целых чисел, в том числе, и преобразование в число с плавающей точкой (fromInt и fromInteger)

Числа с плавающей точкой:
Float (7 знаков после запятой)
Double (16 знаков после запятой)

Логические величины
Bool (True | False)
Операции конъюнкции, дизъюнкции и отрицания (&&, ||, not)

Символы
Char (’a’)
И функции Char в Int и Int в Char (ord, chr)

Списки
Списки могут быть разные:
- список целых чисел
- список символов (строка)
[] - массив
- это список функций
и т. д.

Несколько стандартных операций в примерах:
Main> head
1
Main> tail
Main> length
2
Main> reverse
Main> 0:
Main> - строка приглашения в консоли компилятора ghci
«:» - операция присоединения элемента к списку.

Упорядоченные множества
Примеры:
(2.4, ”cat”) (Float, )
(’a’, True, 1) (Char, Bool, Int)
(,sqrt) (, Float->Float)
(1, (2, 3)) (Int, (Int, Int))

Но, сердце Haskell и всего функционального программирования - это, конечно, сами функции!

Функции

Первая строка - это объявление функции:
Имя_функции:: область_определения - > область _значений
square:: Integer -> Integer
Тут следует сказать, что в Haskell совсем необязательно всегда объявлять функцию. В ряде случаев интерпретатор и так поймет какие у данной функции области определения и значения. Однако, опускать объявления - моветон.

Вторая строка - это определение функции:
Имя_функции параметры = правило_вычисления
square x = x*x

Функция без параметров есть ничто иное, как константа:
e:: Float e = exp 1.0

Функция с несколькими параметрами:
Спасибо janatem за разъяснения ().
abcFormula:: Float -> Float -> Float -> abcFormula a b c = [ (-b+sqrt(b*b-4.0*a*c))/(2.0*a), (-b-sqrt(b*b-4.0*a*c))/(2.0*a) ] -- находит корни уравнения ax^2+bx+c=0

Определения функций с альтернативами

Case … of …
abs2 x = case x>=0 of True -> x False -> -x

Но, помимо стандартных if и case, в Haskell есть очень красивая и наиболее используемая конструкция ветвления. Так называемые, охранные выражения . Пример:
abs3 x | x>0 = x | x<0 = -x | otherwise = 0
Прямую черту следует читать, как: «при».
Читаем: «Функция abs3, с входным параметром x, при x>0 принимает значение x, при x<0 принимает значение -x, и в любом другом случае принимает значение 0».
Конечно, мы могли записать все с помощью двух охранных выражений, но я записал три, что бы было понятно, что их может быть сколько угодно.
Otherwise в прелюдии определен очень просто:
otherwise:: Bool otherwise = True
То есть, можно спокойно написать вместо «otherwise» «True», но это, опять же, моветон.

Сопоставление с образцом

Ну вот, на сегодня и все. Если будет интерес, в ближайшее время напишу продолжение.