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

«Что такое этот ваш 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 без меры, я хочу лишь рассказать вам правду о нём. Мой вывод об этом языке я уже сделал, а свой вывод о нём вы должны сделать сами.

Теоретические основы императивного программирования были заложены ещё в 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 предоставляет дополнительные механизмы по сравнению с чистыми языками программирования (по сравнению с функциональными языками - поиск и вычисления по неполным данным, по сравнению с логическими языками - более эффективный механизм вычислений благодаря детерминизму и вызову по необходимости для функций).

Популярность

На сайте Github сейчас занимает 23-ю строчку по популярности среди языков программирования.

Интерпретатор/компилятор Pugs для языка Perl 6.

Язык описания аппаратных средств Lava .

Система обработки натурального языка LOLITA.

Системы доказательства теорем Equinox / Paradox и Agda .

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

Функциональное программирование на Haskell

Часть 1. Введение

Серия контента:

Императивное программирование

Наиболее распространены императивные языки , в которых вычисление сводится к последовательному выполнению инструкций. Решение задачи на императивном языке сводится к описанию того, что необходимо проделать, чтобы получить результат. Классические примеры – FORTRAN (1957), ALGOL (1958) и C (1972).

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

Переменные рассматриваются как изменяющиеся во времени ячейки памяти. Текущие значения переменных в программе образуют изменяющееся состояние.

Пример императивного кода – процедура для вычисления факториала на C:

int fac (int n) { int x = 1; while (n > 0) { x = x*n; n = n-1; } return x; }

Здесь повторение операции умножения выражено через цикл. В процессе вычисления изменяются значения переменных x и n .

Инициализация: n:= 3; x:= 1; Первый виток цикла: x:= 1*3 = 3; n:= 3-1 = 2; Второй виток цикла: x:= 3 * 2 = 6; n:= 2 - 1 = 1; Третий виток цикла: x:= 6 * 1 = 6; n:= 1 - 1 = 0; Результат - 6

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

Функции и функциональность

В математическом смысле функция f: X → Y – это правило, сопоставляющее элементу x из множества X (области ) элемент y = f x из множества Y (кообласти ).

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

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

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

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

fac 0 = 1 fac n = n * fac (n-1)

n – формальный аргумент функции fac . В правой части после знака = описано, что функция делает со своим аргументом. Базовые функции для умножения и вычитания записаны через инфиксные (указываемые между аргументами) операторы * и - .

Здесь уравнений два. При вычислении функции уравнения просматриваются по порядку. Если n = 0, то будет использовано первое уравнение. Если n ≠ 0, то оно не подойдет, и задействуется второе.

Обратите внимание: аргументы функции перечисляются рядом с ее именем через пробел. Это удобно, потому что применение функции очень часто встречается в функциональных программах (таблица 1).

Запись в математике	Запись в Haskell
f(x)	f x
f(x,y)	f x y
f(g(x))	f (g x)
f(g(x),h(y))	f (g x) (h y)
f(x) + g(x)	f x + g x
f (x+y)	f (x+y)
f(-x)	f (-x)

Таблица 1. Запись применения функции в математике и в Haskell

Уравнения для fac составляют точное определение функции, а не последовательность действий по вычислению, как это было в императивном коде.

Используется рекурсия, т. е. fac определяется через саму себя. Такое определение работает, потому что fac выражается через более простой случай и, в конечном счете (если n ≥ 0), доходит до базового случая n = 0. Вычисление fac 3 по такому определению можно произвести так (на каждом шаге подчеркнуты упрощаемые выражения):

fac 3 → 3 * fac 2 → 3 * (2 * fac 1) → 3 * (2 * (1 * fac 0)) → 3 * (2 * (1 * 1)) → 3 * (2 * 1) → 3 * 2 → 6

Здесь мы применили f к значению 3 . При этом 3 называется фактическим аргументом .

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

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

Обратите внимание, что для n < 0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).

Теперь запишем функцию, вычисляющую для целых k и вещественных r биномиальный коэффициент

При k ≥ 0 мы имеем выражение, где в знаменателе стоит только что определенный факториал числа k, а в числителе – убывающая факториальная степень (falling factorial power)

Запишем для нее рекурсивное определение:

ffp r 0 = 1 ffp r k = (r-k+1) * ffp r (k-1)

В первом уравнении r не используется, поэтому можно использовать заменитель _ и писать ffp _ 0 = 1 .

Можно убедиться, что

(проверьте это). Поэтому уравнения факториала можно заменить на

fac n = ffp n n

Как только мы записали уравнения функции ffp , ее можно рассматривать как абстрактный черный ящик с двумя входами и одним выходом не заботясь о том, что именно происходит внутри. Всё, что для нас теперь важно, – это корректное отображение входов в выход.

Рисунок 2. Черный ящик, вычисляющий убывающую факториальную степень

Возьмем еще один черный ящик (/) с двумя входами x и y и выходом, равным частному x/y:

будет вычислять такая схема:

Рисунок 3. Схема из черных ящиков, вычисляющая биномиальный коэффициент

Она соответствует выражению

ffp r k / fac k

Определим искомую функцию:

binc r k | k >= 0 = ffp r k / fac k | otherwise = 0

Такая запись называется уравнением с условиями (сравните с математической записью определения). После | и до знака = стоят условия. « otherwise » означает «иначе». Подробно это будет рассмотрено в последующих статьях.

Пример вычисления binc 6 2:

binc 6 2 → ffp 6 2 / fac 2 → (5 * ffp 6 1) / fac 2 → (5 * (6 * ffp r 0)) / fac 2 → (5 * (6 * 1)) / fac 2 → (5 * 6) / fac 2 → 30 / fac 2 → 30 / ffp 2 2 → 30 / (1 * ffp 2 1) → 30 / (1 * (2 * ffp r 0)) → 30 / (1 * (2 * 1)) → 30 / (1 * 2) → 30 / 2 → 15

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

Это приводит к важному понятию чистоты.

Чистота

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

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

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

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

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

Каждое выражение в функциональном языке соответствует своему значению; вычисление только модифицирует выражение, но на значение не влияет.

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

Язык без побочных эффектов называется чисто функциональным .

Такие языки, как ML и Scheme, в целом являются функциональными по стилю, однако допускают как присваивания, так и побочные эффекты.

Примеры чисто функциональных языков: Miranda , Haskell и Clean .

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

Ленивость и нестрогость

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

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

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

Например, наша функция binc всегда будет требовать значение k , но значение r требуется, только если k ≥ 0.

В соответствии с этим, говорят о языках со строгой семантикой и языках с нестрогой семантикой. («Нестрогость» и «ленивость» – не одинаковые, но близкие понятия.)

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

В нестрогом языке вычисление производится по необходимости. Если f нестрогая, то вычисление f e может завершиться, даже если вычисление e не завершается.

Например,

обозначает список из трех элементов. Вычисление fac (-1) зацикливается. Значит, вычисление списка также зациклится.

Пусть теперь функция length возвращает длину списка. Выражение

length

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

Примеры нестрогих языков: Miranda и Haskell. Строгие языки – ML и Scheme.

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

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

Краткая история

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

Одними из первых языков с функциональным стилем были LISP (1958), APL (1964), ISWIM (1966) и (1977).

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

• (1973) – первый язык с типизацией Хиндли–Милнера.
• SASL , KRC , Miranda (1972–1985) – одни из первых ленивых языков.
• Hope (1980) – один из первых языков с алгебраическими типами данных. Haskell разрабатывался многочисленной группой исследователей с 1987 г. Он назван в честь Хаскелла Карри .

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

Нововведения Haskell – монады и классы типов. Другие сильные стороны, заимствованные из других языков – каррирование, алгебраические типы данных, сопоставление с образцом. (Здесь мы просто приводим набор ключевых слов; все эти понятия скоро будут разъяснены.)

Последнее зафиксированное описание – Haskell 98, однако язык постоянно развивается и усложняется; сейчас планируется выход Haskell" .

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

• Компиляторы и другие средства разработки.
• Распределенная система управления версиями Darcs .
• Оконный менеджер xmonad .
• Сервер Web-приложений HAppS .
• Интерпретатор/компилятор Pugs для языка Perl 6.
• Операционная система House .
• Язык описания аппаратных средств Lava .
• Система обработки натурального языка LOLITA.
• Системы доказательства теорем Equinox / Paradox и Agda .

Основные источники информации по Haskell

У Haskell имеется широкое и дружелюбное сообщество.

Основной источник информации – сервер haskell.org .

• [email protected] – свободное обсуждение.
• [email protected] – более простые темы для новичков.

  Есть очень оживленный IRC-канал #haskell на irc.freenode.net . В нем можно быстро получить любезный ответ практически на любой вопрос.

  Множество тематических блогов собирается на http://planet.haskell.org/

• Хорошим введением в Haskell может быть руководство A Gentle Introduction to Haskell 98 .
• Документацию по обширным библиотекам смотрите по адресу http://haskell.org/ghc/docs/latest/html/libraries/
• Формальный отчет – The Haskell 98 Report .

Редактирование и выполнение кода

Реализации Haskell

Формально, Haskell не имеет какой-то одной «стандартной» реализации.

Для интерактивной работы подойдет легковесный интерпретатор Hugs .

Также есть интересный проект Yhc , компилирующий исходные тексты в байткод, и Helium – учебный вариант Haskell, дружественный к новичкам (например, выдающий более ясные сообщения об ошибках). Однако они еще находятся в процессе разработки.

Де-факто стандартным стал компилятор/интерпретатор GHC. Он является наиболее продвинутым, во всём соответствует стандарту и предлагает ряд экспериментальных расширений. Мы сконцентрируемся на нем.

GHC можно загрузить по адресу http://haskell.org/ghc/ . Если вы используете GNU/Linux, то посмотрите готовые сборки в своем дистрибутиве. Для MacOS X и Windows можно также найти бинарные файлы. (Учтите, что сборка GHC прямо из исходников может быть довольно утомительным занятием.)

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

Итак, после установки GHC вы можете запустить в терминале ghci:

Здесь Prelude – это название загруженного модуля. В Prelude содержатся основные определения, и он всегда задействуется по умолчанию. Изучая или переписывая самостоятельно код Prelude, начинающие могут узнать много нового. (Мы с вами тоже отчасти будем это делать.)

Символ > означает, что ghci ожидает пользовательский ввод. Это могут быть выражения Haskell, а также команды для интерпретатора.

Клавишами ← и → можно перемещать курсор по командной строке ghci. и ↓ пролистывают историю команд назад и вперед.

Вместо Prelude> или других имен модулей мы дальше будем писать ghci> (если хотите сделать так же, выполните в ghci команду:set prompt "ghci> ").

Для начала ghci можно использовать как продвинутый калькулятор:

ghci> 1*2 + 2*3 + 3*5 23 ghci> 23^23 ghci> gcd 3020199 1161615 232323

Операторы совпадают с принятыми в других языках (таблица 2).

Таблица 2. Арифметические операторы из Prelude

Для них используется инфиксная запись и соответствующий приоритет. Например, 2*3+4 соответствует (2*3)+4 , а 2^3^4 – 2^(3^4) . Чтобы изменить принятый приоритет, можно расставить скобки.

В ghci имеется специальная переменная it , равная значению последнего успешно вычисленного выражения.

ghci> 15 - 2 13 ghci> it + 10 23

Редактирование исходного кода

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

• Расширение для Emacs : http://www.iro.umontreal.ca/~monnier/elisp/
• Расширение для Vim : http://projects.haskell.org/haskellmode-vim/

Другие средства разработки описаны на странице http://haskell.org/haskellwiki/Libraries_and_tools/Program_development

Для кода Haskell используется расширение файлов.hs .

Если вы запишете код на Haskell в файл foo.hs , то определения загружаются в ghci командой:load foo . Параллельно файл можно редактировать и при необходимости перезагружать определения при помощи:reload .

Текущая директория изменяется командой:cd (например, :cd /home/bob).

Вы можете загрузить прилагающийся к статье исходный код и вычислить выражения:

$ ghci ghci, version 6.10.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> :load fph01.lhs Compiling Main (fph01.lhs, interpreted) Ok, modules loaded: Main. *Main> ffp 6 6 720 *Main> fac 6 720 *Main> binc 6 2 15.0 *Main> binc 6.5 4 23.4609375

Эти и другие команды можно сокращать – вместо:load использовать:l , вместо:reload – :r и так далее.

Список команд интерпретатора выводит:help . Для выхода из ghci нужно набрать:quit .

В ходе нашего изложения часто будут встречаться простые примеры, состоящие из одного-двух уравнений. Их можно сразу вводить в ghci при помощи let:

ghci> let double x = 2*x ghci> double 23 46

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

ghci> let { fac 0 = 1; fac n = n * fac (n-1) } ghci> fac 23 25852016738884976640000

Заключение

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

Функциональное программирование
на языке Haskell

Конспект лекций

Рыбинск 2010

Введение..................................................................................................................... 3

1 История функционального программирования.................................................... 4

2 Особенности функциональных языков................................................................... 5

2.1 Основные свойства........................................................................................ 5

2.2 Преимущества............................................................................................... 9

2.3 Недостатки................................................................................................... 11

3 Обзор существующих языков............................................................................... 13

4 Базовые принципы языка Haskell......................................................................... 16

4.1 Интерактивная среда.................................................................................. 16

4.2 Структура программы............................................................................... 18

4.3 Типы функций............................................................................................. 22

4.4 Условные вычисления (ветвление).............................................................. 24

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

4.6 Списки......................................................................................................... 29

4.7 Локальные определения............................................................................. 33

4.8 Дополнительные возможности интерактивной среды.............................. 35

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

4.10 Бесконечные структуры данных.............................................................. 37

5 Типы данных и модули......................................................................................... 40

5.1 Пользовательские типы и структуры данных........................................... 40

5.2 Модули........................................................................................................ 44

6 Классы и монады................................................................................................... 47

6.1 Классы......................................................................................................... 47

6.2 Ввод-вывод.................................................................................................. 49

7 Примеры................................................................................................................ 53

Заключение.............................................................................................................. 54

Список использованных источников...................................................................... 55

Введение

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

Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Следующим шагом после ассемблера стали так называемые императивные языки высокого уровня: Бейсик, Паскаль, Си, Ада и прочие, включая объектно-ориентированные. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (т. е. присваиваний), и итеративные циклы . Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности.

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

2 История функционального программирования

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

Теория так и оставалась теорией, пока в начале 1950-х годов Джон Маккарти не разработал язык Лисп (Lisp), который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется, после многих лет эволюции он удовлетворяет современным запросам .

В связи с все возрастающей сложности программного обеспечения всё большую роль начинает играть типизация. В конце 70-х - начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм . Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов. Практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов.

3 Особенности функциональных языков

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

3.1 Основные свойства

Среди свойств функциональных языков обычно выделяют следующие:

– краткость и простота;

– строгая типизация;

– функции – это значения;

– чистота (отсутствие побочных эффектов);

– отложенные (ленивые) вычисления;

– модульность.

Рассмотрим каждое из этих свойств подробнее.

Краткость и простота

Программы на функциональных языках обычно короче и проще, чем те же самые программы на императивных языках. Одним из самых распространенных примеров является быстрая сортировка Хоара.

На императивном языке C быстрая сортировка обычно реализуется следующим образом:

void qsort (int a, int l, int r)

int i = l, j = r, x = a[(l + r) / 2];

while (a[i] < x) i++;

while (x < a[j]) j--;

int temp = a[i];

while (i <= j);

if (l < j) qsort (a, l, j);

if (i < r) qsort (a, i, r);

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

qsort (x:xs) = qsort

++ [x] ++ qsort

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

Код на функциональном языке выигрывает по размеру кода и его наглядности. Кроме того, приведенная реализация на языке C сортирует массив, элементы которого имеют целочисленный тип (int), а реализация на Haskell может сортировать списки элементов любых типов, на которых определена операция сравнения.

Строгая типизация

Большинство языков функционального программирования имеют строгую типизацию. Строгая типизация подразумевает выполнение следующих обязательных условий :

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

– функции могут принимать и возвращать значения, имеющие строго тот же тип данных, что указан при описании функции;

– каждая операция требует аргументов строго определённых типов;

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

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

Функции как значения

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

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

Чистота

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

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

Отложенные вычисления

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

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

Модульность

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

3.2 Преимущества

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

Надежность программирования

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

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

Удобство модульного тестирования

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

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

Возможности оптимизации

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

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

Доказательство свойств функций

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

3.3 Недостатки

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

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

4 Обзор существующих языков

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

Рассмотрим особенности каждого из этих языков:

– Lisp . Получил название от английского LISt Processing – обработка списков. Lisp является одним из самых первых языков функционального программирования. Программы и данные в Lisp представляются системами линейных списков символов. Язык Lisp, наряду с языком Ada, прошел процесс фундаментальной стандартизации для использования в военном деле и промышленности, в результате чего появился стандарт Common Lisp. Его реализации существуют для большинства платформ. Первые области применения Лиспа были связаны с символьной обработкой данных и процессами принятия решений . Наиболее популярный сегодня диалект Common Lisp является универсальным языком программирования. Он широко используется в самых разных проектах: Интернет-серверы и службы, серверы приложений и клиенты, взаимодействующие с базами данных , научные расчёты и игровые программы.

– Haskell . Является одним из самых распространённых ленивых языков программирования. Имеет очень развитую систему типизации. В последнее время расширяется набор прикладных библиотек, язык интегрируется в распространённые программные системы, что делает язык всё более и более привлекательным для профессиональных программистов. Основные особенности языка: возможность использования лямбда-абстракции; функции высшего порядка; частичное применение; недопустимость побочных эффектов (чистота языка); ленивые вычисления (lazy evaluation); сопоставление по образцу, функциональные образцы (pattern matching); параметрический полиморфизм и полиморфизм классов типов; статическая типизация; автоматическое выведение типов (основано на модели типизации Хиндли – Милнера); алгебраические типы данных; типы данных с параметрами; рекурсивные типы данных; абстрактные типы данных (инкапсуляция); списочные включения (list comprehensions); охраняющие выражения (guards); возможность писать программы с побочными эффектами без нарушения парадигмы функционального программирования с помощью монад; возможность интеграции с программами, реализованными на императивных языках программирования посредством открытых интерфейсов (стандартное расширение языка Foreign Function Interface).

– ML (Meta Language) – семейство строгих языков функционального программирования с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих западных университетах. Сильно типизированный язык со статическим контролем типов и аппликативным выполнением программ. Основные достоинства ML – высокая верифицируемость программ, простота отладки, потенциал для высокой оптимизации, уникальная краткость записи. Основные недостатки – сложность синтаксиса, непривычность принятых соглашений и ограничений, практическая невозможность макротрансформаций.

– Erlang – функциональный язык программирования, позволяющий писать программы для разного рода распределённых систем. Разработан и поддерживается компанией Ericsson. Язык включает в себя средства порождения параллельных процессов и их коммуникации с помощью посылки асинхронных сообщений. Программа транслируется в байт-код, исполняемый виртуальной машиной, что обеспечивает переносимость. Главное в Erlang – его модель легковесных процессов. Перефразируя для Erlang слоган «Everything is an object» («Всё является объектом»), можно сказать «Everything is a process» («Всё является процессом»). Процессы дёшевы, создание процесса занимает не больше ресурсов, чем вызов функции. Единственным способом взаимодействия процессов является асинхронный обмен сообщениями.

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

5 Базовые принципы языка Haskell

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

Для начала рассмотрим необходимый инструментарий для работы. Самым распространенным и эффективным на сегодняшний день является компилятор GHC (Glasgow Haskell Compiler). Он распространяется под открытой лицензией, и любой желающий может загрузить его исходные коды или скомпилированную версию для популярных операционных систем с официального сайта http://haskell. org/ghc/ (кроме того, на сайте http://haskell. org/ можно найти много дополнительной информации по языку).

Кроме самого компилятора в GHC входит интерактивная среда GHCi (GHC interactive) - интерпретатор Haskell, позволяющий вычислять любые выражения и интерпретировать написанные программы.

К сожалению, полнофункциональной среды разработки для Haskell еще не разработано (кроме, возможно, Leksah - среды разработки для Haskell, написанной на Haskell, и нескольких плагинов для Visual Studio и Eclipse), но зачастую хватает возможностей лишь расширенного текстового редактора (например, Notepad++, gedit, kate) с подсветкой синтаксиса и некоторыми другими возможностями.

5.1 Интерактивная среда

Интерактивная среда GHCi может вычислять любые выражения на языке Haskell. Рассмотрим основы работы с этой средой. Для ее запуска (после установки GHC или Haskell-Platform) достаточно запустить в консоли программу ghci (либо выбрать соответствующую программу в списке всех программ). После запуска в консоли появится приглашение:

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

Здесь мы можем вычислить любое выражение, например обыкновенное арифметическое выражение:

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

Prelude> 1-2*(4-3^2)

Возведение в степень (^) является стандартным оператором, определенным в стандартном модуле Prelude наравне с операциями сложения и умножения.

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

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

Prelude> max 7 100

В данном примере вычисляется максимальное из двух чисел - семи и ста. Как мы видим, результатом вычисления функции является число 100.

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

Prelude> max (2^^3)

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

Prelude> max (2^10) 10^3

Без скобок данное выражение интерпретируется как максимум из двух чисел (1024 и 10), возведенный в третью степень.

Кроме того, интерактивная среда GHCi может автоматически дополнять имена вводимых функций. Если набрать только начальную часть имени функции и нажать на клавиатуре клавишу «Tab», то GHCi попытается дополнить имя функции до имеющегося среди доступных определений (из стандартного модуля, либо подключенных пользователем). Например, если набрать «maxi» и нажать «Tab», то GHCi дополнит имя функции до «maximum». В том случае, если однозначно дополнить невозможно (есть несколько подходящих вариантов), то выводятся все возможные варианты:

max maxBound maximum

Теперь можно уточнить имя функции (дописав несколько букв) и снова нажать клавишу «Tab».

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

5.2 Структура программы

Компиляторы и интерпретаторы языка Haskell работают с файлами с расширением *.hs , содержащими текст программы. Текст программы имеет следующую структуру:

1. в начале программы может быть указано имя текущего модуля и экспортируемые определения;

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

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

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

В данном примере объявляется символ с именем five, который имеет значение, равное целому числу 5. Имена в Haskell чувствительны к регистру, то есть Five и five являются различными именами. Кроме того, вводится дополнительное ограничение на первую букву имени - имена функций и их аргументов могут начинаться только со строчной буквы (five, max, min, x, y), а имена типов данных (Bool, Integer, Double), модулей (Main, Test) и классов (Eq, Ord, Num) - только с прописной (заглавной).

Рассмотрим пример посложнее:

three = one + two

Здесь объявляется три символа - one, two, three. Как видно из примера, каждое определение занимает одну строчку и разделяются они только концом строки (пустые строчки будут игнорироваться). Символы one и two определены также, как и символ five в предыдущем примере, а при определении символа three используются уже существующие определения. Как несложно догадаться, символ three будет иметь значение 3.

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

three = one + two

Загрузим наш пример в интерактивную среду GHCi. Для этого достаточно при запуске ghci в качестве параметра командной строки указать имя файла с текстом программы (например, Test. hs) (в ОС семейства Windows достаточно просто открыть файл, установленный GHC автоматически назначает ghci для открытия файлов *.hs). Если программа не содержит ошибок, то мы увидим уже знакомое приглашение:

Здесь Main - имя текущего модуля (подробнее модули рассматриваются в соответствующей главе). GHCi позволяет вычислять любые функции из текущего модуля. Например, вычислим наш символ three:

Более сложные выражения также возможны:

*Main> (three+two)^2

*Main> max one two

Далее рассмотрим функции с аргументами. В отличие от привычных языков программирования для передачи аргументов не требуется записывать их в скобках и через запятую. Вызов функции происходит в следующем виде: func x1 x2 x3… xN, где func – имя функции, а xi – i-й аргумент. Результатом функции будет являться какой-либо объект, например, число, список, функция, лямбда-выражение либо любая другая структура данных.

Описание функции с аргументами практически не отличается от описания символов в предыдущих примерах. Определение функции располагается на отдельной строчке и имеет следующий вид: func x1 x2 x3… xN = expression, где func - имя новой функции, xi – имя i-го аргумента, expression - выражение.

Например, добавим функцию, складывающую два числа, в существующий файл Test. hs.

Теперь мы можем перезагрузить в интерактивной среде измененный модуль. Для этого достаточно перезапустить ghci, либо воспользоваться стандартной командой «:r»:

Compiling Main (Test. hs, interpreted)

Ok, modules loaded: Main.

После этого новая функция становится доступной из интерактивной среды:

*Main> plus one 8

Еще один пример функции с аргументами:

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

Однострочные комментарии в языке Haskell начинаются с двух тире:

plus x y = x+y --функция сложения

Блочный комментарий начинается с “” и заканчивается “”:

эта функция возвращает число на 1 большее

чем полученное в качестве аргумента

5.3 Типы функций

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

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

	Описание
	целое число от - до
	длинное целое число, без границ (предусмотрено использование встроенной длинной арифметики)
	вещественное число
	вещественное число удвоенной точности
	список элементов некоторого типа a, например, список целых чисел записывается как
	строка (или список символов), эквивалент
	логический тип (принимает значения True или False)
	кортеж из двух элементов типа a и b (например, (String, Bool))
	кортеж из трех элементов типа a, b и c (например, (String, Bool, Int))

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

Первая строчка означает, что функция pi имеет тип Double, затем идет само определение функции, означающее, что функция pi возвращает приближенное значение числа пи. Если же функция имеет один аргумент, то ее тип описывается следующим образом:

inc:: Integer -> Integer

Данная запись означает, что функция inc преобразует аргумент типа Integer в результат типа Integer.

Если функция имеет два аргумента, то ее описание выглядит так:

power:: Double -> Integer -> Double

Функция power принимает два аргумента – вещественное основание x и целая степень n, результатом же вычисления функции является вещественное число.

В общем виде описание типа функции выглядит так так:

name:: X1 -> X2 -> ... ->XN -> Y

Здесь name – имя функции, Xi – тип i-го аргумента, Y – тип функции.

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

Перечислим некоторые стандартные функции.

Функции	Описание
	традиционные арифметические операции
	деление вещественных чисел
	возведение числа в целочисленную положительную степень
	возведение числа в вещественную степень
	целочисленное деление и остаток от деления целых чисел
	квадратный корень
	тригонометрические функции
asin, acos, atan	обратные тригонометрические функции
	сравнение на равенство и неравенство
>, <, >=, <=	сравнение
	логические операции
	первый элемент пары (кортежа из двух элементов)
	второй элемент пары
	хвост (все элементы кроме первого) списка

5.4 Условные вычисления (ветвление)

В традиционных языках программирования основными способами организации ветвления являются условный оператор (if then else) и оператор выбора (case или switch). Кроме них в языке Haskell используется сопоставление с образцом в определениях функций и так называемые охраняющие выражения. Рассмотрим подробнее каждый из этих способов.

Конструкция if-then-else

Синтаксическая конструкция «if-then-else» позволяет вычислять различные выражения в зависимости от результатов некоторого условия:

if <условие> then <выражение1> else <выражение2>

Здесь <условие> - некоторое выражение, имеющее тип Bool. В отличие от императивных языков, в языке Haskell конструкция «if-then-else» является выражением, которое обязательно должно иметь какой-либо результат. В связи с этим ветка else является обязательной и типы выражений <выражение1> и <выражение2> должны совпадать.

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

max a b = if a>b then a else b

Как уже было сказано, конструкция «if-then-else» является выражением, которое имеет результат. Следовательно, ее можно использовать как часть другого выражения:

*Main> 5 + if False then 1 else 0

*Main> (if True then 1 else 0) + 5

Заметим, что в последнем примере скобки обязательны. Без скобок выражение будет интерпретироваться иначе:

*Main> if True then 1 else 0 + 5

Все, что записано после слова «else» относится к выражению ветки else.

Конструкция case

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

fib n = case n of

_ -> fib (n-1) + fib (n-2)

Также как и условное выражение «if-then-else» выражение case имеет результат и, следовательно, может быть частью других выражений.

Рассмотрим case выражение в общем виде:

case <выражение0> of

<образец1> -> <выражение1>

<образец2> -> <выражение2>

<образецN> -> <выражениеN>

Здесь результат вычисления <выражение0> последовательно сопоставляется с образцами. При удачном сопоставлении с i-м образцом, результатом всего case будет являться результат i-го выражения. Подробнее сопоставление с образцом будет рассматриваться в соответствующем разделе, а пока его можно рассматривать как сравнение с заданными константами.

Обратим внимание, что каждый образец должен быть записан на новой строчке с отступом большим, чем отступ у зарезервированного слова case. Также отступы перед образцами должны быть равны между собой.

Кроме того, допустим альтернативный способ записи case-выражений без использования отступов:

fib n = case n of {1->1;2->1;_->fib (n-1) + fib (n-2)}

Такой способ более компактен, но менее нагляден. В общем виде:

case <выражение0> of { <образец1> -> <выражение1> ; <образец2> -> <выражение2> ; ... ; <образецN> -> <выражениеN> }

Определения функций

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

Рассмотрим в качестве примера функцию вычисления числа Фибоначчи.

fib n = fib (n-1) + fib (n-2)

При вычислении значения функции ее единственный аргумент сопоставляется с образцами ее определений сверху вниз. Если аргументом было число 2, то первое сопоставление окажется неудачным, а второе – удачным, и в результате функция примет значение 1. Если же аргумент не сопоставится с образцами в первых двух определениях, то он обязательно сопоставится с именем аргумента n (в данном случае n примет значение переданного аргумента), и будет вычислена сумма двух предыдущих чисел Фибоначчи.

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

Охраняющие выражения

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

<имя функции> <список аргументов функции>

|<условие1> = <выражение1>

|<условие2> = <выражение2>

|<условиеN> = <выражениеN>

Все символы “|” должны начинаться на своей строке и с одного отступа. При вычислении значения функции перебираются сверху вниз все условия, являющиеся выражениями типа Bool. Когда найдется i-е условие, результат которого равен True, вычисляется выражение i, результат которого будет результатом функции.

Например, запишем функцию нахождения числа Фибоначчи:

|otherwise = fib (n-1) + fib (n-2)

Здесь otherwise – это заведомо истинное условие, всегда равное True.

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

Сопоставление с образцом (pattern matching) - это удобный способ связать различные части некоторого значения с заданными именами (символами) . Сопоставление с образцом используется в определениях и в case выражениях.

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

f x = fst x + snd x

Данная функция вычисляет сумму элементов кортежа. Стандартные функции fst и snd получают первый и второй элемент кортежа соответственно.

*Main> f (2,4)

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

При вычислении этой функции от (2,4) элементы этого кортежа будут сопоставлены с указанным в определении функции образцом, то есть символ «a» примет значение 2, а символ «b» примет значение 4.

Так мы можем определить аналоги функций fst и snd:

Обратим внимание, что в определении функции fst1 не используется x, а в определении функции snd1 не используется y. В таких случаях, когда часть образца (или целый аргумент) не используется нет необходимости указывать имя этой части (или аргумента) - вместо имени достаточно указать символ подчеркивания «_». Переопределим эти функции:

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

В образцах могут указываться любые конструкторы (в предыдущих примере использовался конструктор кортежа), например, конструкторы списка, кортежа, или любых пользовательских типов данных, а также конкретные значения аргументов (как в примере про числа Фибоначчи). В некоторых случаях сопоставление может оказаться неудачным, тогда происходит попытка использовать следующее сопоставление (из следующего определения или образца case). Рассмотрим пример:

f _ 0 = error "division by zero"

f (a, b) c = (a+b)/c

Здесь при вычислении функции f второй аргумент будет равен 0, то для вычисления функции будет выбрано первое определение, иначе - второе, так как сопоставление с именем всегда удачно. Функция error останавливает выполнение программы с заданным текстом ошибки. Примеры использования описанной функции:

*Main> f (1,2) 3

*Main> f (3,2) 1

*Main> f (5,5) 5

*Main> f (5,5) 0

*** Exception: division by zero

Кроме того, каждый образец может быть поименован для того чтобы к структурированному аргументу был доступ и поэлементно и целиком. Для именования образца используется оператор @. Перед ним идет имя, через которое можно осуществлять доступ к аргументу как к единому целому, а затем сам образец. Например,

func1 p@(a, b) = a + b + func2 p

func2 (a, b) = a*b

5.6 Списки

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

Списки создаются с помощью конструктора списка - операции «:». Список может быть либо пустым, либо состоять из головы (первый элемент списка) и хвоста (список из остальных элементов). Пустой список обозначается пустыми квадратными скобками: «», а список, состоящий из головы x и хвоста y записывается с помощью конструктора списка: «x:y».

Существует и более удобный способ записи списков: перечислением элементов в квадратных скобках. Например, список целых чисел от 1 до 3 может быть записан так:

1: = 1:2: = 1:2:3:

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

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

В приведенной выше реализации функции head хвост списка не используется, можно заменить его имя подчеркиванием:

Аналогично можно описать операцию взятия хвоста списка.

Эти две функции (head и tail) вызовут ошибку при передачи им пустого списка, так как сопоставление не будет успешным.

Рассмотрим еще пример функции работы со списками: функция вычисления длины списка:

length (_:t) = 1 + length t

Если входной список пуст, то в результате сопоставления сработает первое определение, иначе – второе.

Строки в языке Haskell являются списками символов. Символы записываются в апострофах (например, "c"), а строки – в кавычках (например, "string"). Любую строку можно представить в стандартной записи списков, например, строка "string" аналогична списку ["s","t","r","i","n","g"]. Работа со строками выполняется точно так же, как со списками.

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

getN (x:_) 0 = x

getN (_:t) n = getN t (n-1)

Взятие n-го элемента списка реализовано в стандартной функции "!!". Она используется так:

Здесь list – список, n – номер искомого элемента. Нумерация элементов начинается с нуля. Если длина списка окажется меньше или рана номеру искомого элемента, вычисление этой функции приведет к ошибке.

Кроме того, возможно задание списков из перечислимых элементов (например, целые числа или символы) следующим образом:

Здесь X1 – начало арифметической прогрессии, а X2 – ее конец. Например, является списком . Таким способом можно задавать только возрастающие списки с шагом равным единице. Если нужно задать последовательность с другим шагом, то можно использовать следующую запись:

В этом варианте X1 – первый элемент последовательности, X2 – второй, X3 – возможный последний. Шаг последовательности выбирается как X2-X1, и последовательность содержит элементы, расположенные только между X1 и X3. Например, является списком .

Также существует способ задания списков на основе уже существующих. В общем виде этот способ можно записать так:

[<выражение> | <образец> <- <список>, <ограничение1>, ..., <ограничениеN>]

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

[ x^2 | x <- ,mod x 3 == 0]

Данное выражение конструирует список из квадратов нечетных чисел от одного до 30, которые делятся на 3. Результатом будет:

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

map:: (a -> b) -> [a] -> [b]

map f xs =

То есть, она принимает в качестве первого аргумента функцию, преобразующую объекты типа a в объекты типа b, а в качестве второго аргумента – список из элементов типа a. Результатом функции map является список элементов типа b.

При использовании функции map удобно применять безымянные функции, которые описываются в виде λ-выражений (рассматриваются подробнее в разделе о функциях высшего порядка). Например, список квадратов чисел от 1 до 10 может быть описан следующим образом:

map (\x->x*x)

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

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

map (^2)

Также, можно применять и любые другие функции, например:

map inc

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

Имя функции		Описание
		голова (первый элемент) списка
		хвост (все кроме первого элемента) списка
		последний элемент списка
		все элементы списка кроме последнего
	[a] → Int → a	элемент с заданным номером
		вычисление длины списка
	Int → [a] → [a]	взять из списка n первых элементов
	Int → [a] → [a]	отбросить из списка n первых элементов
		разворачивание списка в обратном порядке
	(Num a) => [a] → a	сумма элементов списка
	(Num a) => [a] → a	произведение элементов списка
	[a] → [a] → [a]	конкатенация списков

5.7 Локальные определения

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

Существует два способа описания локальных функций: с помощью зарезервированного слова where и let . Определение локальных функций с помощью where может использоваться только в определении функции. Определим функцию вычисления среднего арифметического трех чисел:

average3 x y z = s / 3

В общем виде использование where может быть записано так:

<имя функции> <аргументы> = <выражение>

<определение 1>

<определение 2>

<определение N>

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

<имя функции> <аргументы> = <выражение> where { <определение 1> ; <определение 2> ; ... ; <определение N> }

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

average3 x y z =

В общем виде этот способ выглядит так:

<определение 1>

<определение 2>

<определение N>

<выражение>

Все определения должны находиться на одном и том же отступе, но большем чем строка, содержащее let. Слово in должно находится на отступе не меньшем чем let. При желании можно использовать следующий синтаксис:

let { <определение 1> ; <определение 2> ; ... ; <определение N> } in <выражение>

В таком случае отступ игнорируется.

5.8 Дополнительные возможности интерактивной среды

В интерактивной среде GHCi кроме вычисления функций или выражений есть множество дополнительных возможностей. Многие из них доступны через команды, начинающиеся с символа «:». Например, написав в строке GHCi команду «:?» можно увидеть список всех остальных команд (по командам также работает автодополнение). Рассмотрим наиболее полезные команды.

:t - получение типа указанного выражения. Например:

*Main> :t reverse (tail "mama")

reverse (tail "mama") ::

:i - получение информации о функции (тип, в каком модуле или классе определена). Например:

*Main> :i reverse

reverse:: [a] -> [a] -- Defined in GHC. List

:l - загрузить указанный модуль и сделать его текущим.

:m - загрузить или выгрузить указанный модуль.

:q - закрыть GHCi.

Еще одной полезной особенностью является возможность задания определений функций прямо в GHCi. Для этого используется упрощенная конструкция let. Например:

*Main> let f x = x+2*x

Полная же конструкция let действует только в пределах своего выражения:

*Main> let z = 10 in z+z

:1:0: Not in scope: `z"

GHCi сообщает, что данное имя не определено в текущей области видимости.

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

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

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

Дописать как следует этот раздел

Рассмотрим функцию сложения двух чисел:

plus x y = x + y

Функцию plus можно описать иначе:

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

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

Еще вариант описания функции plus:

Используя функцию plus (любую вышеприведенную реализацию), можно написать функцию инкрементации:

inc x = plus 1 x

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

Получается, что функция inc возвращает функцию, прибавляющую 1 к одному своему параметру.

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

plus = \x y -> x+y

Здесь “\” означает начало λ-выражения, затем перечисляются параметры (x y), и после стрелки (->) идет выражение.

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

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

(\x y -> x+y) 3 6

Результатом будет число 9.

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

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

Либо, в обычной записи:

firstoftwo x _ = x

5.10 Бесконечные структуры данных

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

Очевидно, что её значение не может быть вычислено. При попытке это сделать, произойдет зацикливание. Рассмотрим еще одну функцию:

Её значение не зависит от параметра х. Следовательно нет необходимости его вычислять. И вычисление выражения

не приведет к зацикливанию и вернет результат равный 1.

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

Они задаются только первыми двумя элементами, по которым вычисляется шаг прогрессий. Если второй элемент прогрессии не указан (как в первом примере), то шаг принимается равным 1.

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

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

fact n = factlist !! n

factlist = fl 1 1

where fl x n = x:(fl (x*n) (n+1))

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

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

6 Типы данных и модули

6.1 Пользовательские типы и структуры данных

При описании типов функций могут потребоваться пользовательские синонимы уже существующих типов. Например, при громоздком определении некоторого типа удобно назвать его одним именем. Не очень приятно каждый раз писать что-нибудь наподобие [(Integer,)], удобнее дать этому типу имя, например, MyType1. Такое определение имеет вид:

type MyType1 = [(Integer,)]

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

Для того чтобы определить собственный тип данных используется следующая запись:

data <имя> = <значение1> | <значение2> | ... | <значениеN>

Таким образом, описывается структура данных с именем <имя>, которая может принимать значение 1, значение 2, и так далее до значения N. Этими значениями типа данных являются конструкторы данных. Каждый конструктор должен иметь уникальное имя, начинающееся с прописной буквы. Имя конструктора данных может совпадать с именем типа данных Например, описание типа данных «цвет» может быть представлено так:

data Color = Red | Green | Blue

Кроме того конструктор может принимать некоторые данные как функция. Например, можно дополнить тип данных «цвет», добавив представление цвета в комбинации красного, зеленого и синего цветов:

data Color = Red | Green | Blue | RGB Double Double Double

Такая запись означает, что объекты типа Color могут принимать значения Red, Green, Blue либо RGB r g b, где r g b - вещественные числа. Например, можно определить функцию, возвращающую желтый цвет:

Задание типов данных может быть полиморфным, так же как задание функций. То есть, можно задать такой тип данных, который содержит в себе некоторый другой, но не конкретный тип. Например, стандартный тип Maybe может быть описан следующим образом:

data Maybe a = Nothing | Just a

Это означает, что объект типа (Maybe a) может быть принимать значение Nothing, либо Just x, где x – объект некоторого типа a. Для доступа к таким объектам используется сопоставление с образцом. Например, можно реализовать функцию unJust, которая вернет содержимое контейнерного класса Maybe если оно не равно Nothing.

unJust (Just a) = a

Рассмотрим еще пример:

find:: (Eq a) => a -> [a] -> Maybe Int

find _ = Nothing

| x == a = Just 0

| otherwise = case (find a xs) of

(Just i) -> Just (i+1)

Nothing -> Nothing

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

С помощью ключевого слова data можно описывать любые структуры данных. Опишем в качестве еще одного примера бинарное дерево:

data Tree a = Nil | Node a (Tree a) (Tree a)

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

Опишем функцию добавления элемента в бинарное дерево поиска.

addtotree Nil x = Node x Nil Nil

addtotree (Node y left right) x

|x

|x>y = Node y left (addtotree right x)

|otherwise = Node y left right

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

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

showtree tree = showtr tree 0 where

showtr (Nil) n = replicate n "\t" ++ "-\n"

showtr (Node x left right) n =

showtr right (n+1) ++

replicate n "\t" ++ show x ++ "\n" ++

showtr left (n+1)

Локальная функция showtr принимает два аргумента - дерево и уровень глубины. Используемая функция show является стандартной функцией для перевода в строковый вид практически любых объектов в Haskell.

Теперь в результате вычисления выражения

addtotree (addtotree (addtotree (addtotree

(addtotree (addtotree (addtotree Nil

которое означает последовательное добавление в дерево целых чисел 5, 3, 8, 1, 4, 6, 9, получим некоторый объект типа Tree. Передав его нашей функции showtree, получим строковое представление этого дерева.

Существует еще один способ определения пользовательских данных - ключевое слово newtype. Его использование практически аналогично data, за исключением одного: типы данных, описанные с помощью newtype имеют только один конструктор данных ровно с одним полем. Этот способ используется для создания нового типа данных на основе уже имеющегося:

newtype MyInt = MyInt Int

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

<имя записи> {

<имя поля 1> :: <тип поля 1>,

<имя поля 2> :: <тип поля 2>,

<имя поля N> :: <тип поля N>}

Например:

data Human = Human {

height:: Double,

Для задания объекта данного типа можно записать:

mike = Human{name="Mike",height=173.4,weight=81.3}

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

john = mike{name="John"}

6.2 Модули

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

Каждый модуль должен иметь вид:

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

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

import <модуль1>

import <модульN>

<остальной код>

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

import <модуль> hiding (<скрываемые определения>)

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

module <Имя>(<определения>) where <код>

Из всех описаний для внешних модулей будут доступны только перечисленные в скобках.

В качестве примера можно привести программу из 3х модулей:

-- Prog . hs

module Prog where

import Mod2 hiding(modfun)

module Mod1(modfun) where

modfun = five * 2

module Mod2 where

Из модуля Prog доступна функция modfun, определенная в модуле Mod1, но не доступна функция five.

7 Классы и монады

7.1 Классы

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

Для определения класса используется следующая запись:

сlass [(<ограничения>) =>] <имя> <переменная типов> where <функции>

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

class Eq a where

(==), (/=) :: a -> a -> Bool

x == y = not (x/=y)

x /= y = not (x==y)

Класс Eq является классом сравнимых типов. Для каждого экземпляра этого класса должны быть определены функции равенства и неравенства. Вторая строка означает, что функции (==) и (/=) должны принимать два аргумента типа a и возвращать объект типа Bool, то есть True или False.

Следующие строчки в определении класса говорят о том, что если определена функция (/=), то функция (==) определяется через нее соответствующим образом, и наоборот. Благодаря этому программисту достаточно определить только функцию сравнения на равенство (или неравенство), а другую функцию интерпретатор определит сам.

Еще пример определения класса, но с наследованием:

class Eq a => MyClass a where

myFunc:: [a] -> a -> Int

Когда класс определен, можно объявить какой-либо тип данных экземпляром этого класса:

instance MyClass Double where

|x==z = 1 + myFunc xs z

|otherwise = myFunc xs z

Таким образом мы объявляем стандартный тип Double экземпляром нашего класса MyClass и определяем функцию myFunc как функцию, вычисляющую количество элементов в первом аргументе, равных второму аргументу функции.

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

test = myFunc x 2 where

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

Когда программист описывает свою структуру данных, она не принадлежит ни к какому из классов. При необходимости программист должен реализовать соответствующие функции для своей структуры и указать ее принадлежность к классу. Например, ранее описанную структуру данных Tree можно объявить экземпляром класса Show, для того что бы интерпретатор мог выводить ее на экран, не прибегая к ручному вызову функции showtree. Для этого напишем:

instance Show a => Show (Tree a) where

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

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

data <имя> = <значение1> | <значение2> | ... | <значениеN> deriving (<класс1>,<класс2>,...,<классM>)

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

data Tree a = Nil | Tree a (Tree a) (Tree a)

Теперь возможно сравнение деревьев операцией “==”, и позволяет использовать их в функциях, требующих это.

7.2 Ввод-вывод

Возможно написать побольше про монады

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

putStrLn "Hello world!"

putStrLn "Good bye world!"

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

При использовании нотации do программирование «нечистых» функций с помощью монад сводится практически к привычному императивному программированию.

Каждая следующая строчка должна быть функцией специального типа - монадического типа. В случае работы с вводом-выводом это тип (IO a).

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

putChar:: Char -> IOвывод символа

putStr:: String -> IOвывод строки

putStrLn:: String -> IOвывод строки с переходом на новую строку

IO a - это монадический тип ввода-вывода, скрывающий побочные эффекты в себе. Тип IO String означает, что функция вернет результат, содержащий строку, а IO () означает, что функция возвращает результат, ничего не содержащий, смысл ее вызова только в побочных эффектах (например, вывод). Пример:

putStrLn "What is you name?"

name <- getLine

Здесь появилось «присваивание». По аналогии с императивными языками можно сказать, что в строке

name <- getLine

произошло присваивание переменной name результата функции getLine. Но, как мы знаем, в Haskell"е нет переменных и значит и присваиваний. В данном случае произошло создание некоторого объекта с именем name, значение которого равно результату вычисления функции getLine. То есть, если после этого написать еще раз

name <- getLine

то создастся новый объект, имя которого перекроет предыдущий.

Таким образом выполняется извлечение результатов монадических функций. Для того чтобы задать подобным образом «переменные» значениями обыкновенных функций используется упрощенная нотация let:

let name = "John"

Ветвление вычислительного процесса осуществляется с помощью тех же if then else и case:

putStrLn "What is you name?"

name <- getLine

"GHC" -> putStrLn "No! I am GHC!"

_ -> putStrLn ("Hi, " ++ name ++ "!")

Если ветвление должно состоять из нескольких функций, то используется ключевое слово do:

putStrLn "What is you name?"

name <- getLine

putStrLn "No! I am GHC!"

_ -> putStrLn ("Hi, " ++ name ++ "!")

Циклы осуществляются с помощью рекурсии, как показано выше, или с помощью специальных функций (реализованных также рекурсивно). К таким функциям относится функция mapM_. Принцип ее работы аналогичен функции map для списков - она применяет монадическую функцию ко всем элементам списка и последовательно выполняет их. Пример:

writeDigit x = do

putStr "Digits:"

mapM_ writeDigit

8 Примеры

Привести различные примеры (деревья поиска, AVL дерево, еще что-нибудь)

Заключение

Заключение

Список использованных источников

1 http://ru. wikibooks. org/wiki/Основы_функционального_программирования

2 http://www. *****/article/funcprog/fp. xml

3 Душкин программирование на языке Haskell – ДМК Пресс, 2007 – 608 с.

4 http://en. wikibooks. org/wiki/Haskell/Pattern_matching

5 http://www. haskell. org/tutorial/

• Tutorial

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

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

Базовые типы языка Haskell - это:
Числа
Логические величины
Символы
Списки
Упорядоченные множества (tuples)
Функции

Числа
Целые:
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 и всего функционального программирования - это, конечно, сами функции!

Функции

Функция, в современной математике, это закон соответствия, который сопоставляет каждому элементу x из данного множества A один единственный (или ни одного) элемент y из множества B.
Haskell, по своему назначению, это, прежде всего, язык математиков, поэтому синтаксис тут максимально точно соответствует этому определению.
Пример:
square:: Integer -> Integer square x = x*x
Как вы, наверное, догадались, это функция возведения числа в квадрат. Разберем её подробно:

Первая строка - это объявление функции:
Имя_функции:: область_определения - > область _значений
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

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

Как и в любом языке, в Haskell есть конструкции ветвления.
Разберем их на примере функции abs (модуль).
If … then … else …
abs1 x = if x>=0 then x else -x

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», но это, опять же, моветон.

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

Один из наиболее распространенных и эффективных приемов в Haskell - это сопоставление с образцом. Вместо параметра мы можем подсунуть функции пример того, как должен выглядеть параметр. Если образец подошел функция выполняется, если нет - переходит к следующему образцу. Например, определение факториала через рекурсию с помощью образцов:
fact:: Integer -> Integer fact 0 = 1 fact n = n * fact (n-1)
Тоже самое, но, с помощью охранных выражений:
fact:: Integer -> Integer fact n | n==0 = 1 | n>0 = n*fact (n-1)
Есть очень распространенный образец для списка: (x:xs). X - обозначает первый элемент, XS - остальной список (кроме первого элемента). «:» - операция присоединения элемента к списку. Примеры из прелюдии:
head:: [a] -> a head (x:_) = x head = error "Prelude.head: empty list" tail:: [a] -> [a] tail (_:xs) = xs tail = error "Prelude.tail: empty list"
Функция head принимает на вход список чего угодно [a] и возвращает первый элемент этого списка. Функция tail принимает на вход список чего угодно [a] и изымает из этого списка первый элемент.
«_» - означает, что данный элемент нас не интересует.

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