Курс "Программирование на Haskell"

Установка

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

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

Запускаем!

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

$ ghci
GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> 

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

Prelude> :set prompt "ghci> "
ghci> 

Приступим!

Базовые вычисления

Для начала, несколько простых арифметических примеров, не нуждающихся в пояснении:

ghci> 14 + 2
16
ghci> 12 * 3
36
ghci> 125 / (7 - 2)
25.0
ghci> 5 * (-3)
-15

Работа с булевой алгеброй также не представляет труда. True и False представляют соответственно ИСТИНУ и ЛОЖЬ, операторы &&, || и not соответствуют логическим операторам И, ИЛИ и НЕ соответственно:

ghci> True && False
False
ghci> False || (True && not False)
True

Проверка на равенство осуществляется при помощи операторов == и /=. Символ /= в Haskell испольуется для большего сходства с реальным символом ≠, используемым в математике. Для сравнения используются привычные операторы <, >, <=, >=:

ghci> 5 == 10
False
ghci> 6 > 3
True
ghci> True /= False
True
ghci> "string" == "long string"
False
ghci> "abc" <= "xyz"
True
ghci> (5 == 3) || (5 <= 10)
True

Вы можете попытаться сравнить несравнимые сущности, но это приведет к ошибке:

ghci> 50 > "123"

<interactive>:4:1:
    No instance for (Num [Char])
      arising from the literal `50'
    Possible fix: add an instance declaration for (Num [Char])
    In the first argument of `(>)', namely `50'
    In the expression: 50 > "123"
    In an equation for `it': it = 50 > "123"

В этом пугающем сообщении говорится, что "123" не является числом, и поэтому не может быть использован в сравнении с числом 50. Аналогичная ошибка произдёт и в результате попытки вычислить 12 + "34" или "True" == True. Позже мы подробнее разберем природу этих ошибок.

Функции

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

Функции, чьи имена целиком состоят из специальных символов, по умолчанию используются в инфиксной записи. Например, *, ==, ++, <|> и пр. Функции, чьи имена используют буквы, по умолчанию используются в префиксной записи. Например: not, my_func, f, g', h_1 и т.д.

В большинстве языков программирования вызов функции записывается как имя функции со список параметров в круглых скобках через запятую: f(x, y, z). В Haskell достаточно написать имя функции, а затем список аргументов через пробел: f x y z. Уже известная нам функция not является примером функции от одного аргумента. Другим примером могут служить функции succ и pred:

ghci> succ 4
5
ghci> pred 8
7

Как вы догадались, эти функции соответственно увеличивают или уменьшают значение на 1. Функции min и max принимают 2 аргумента на вход:

ghci> max 10 45
45
ghci> min 1.9 2.0
1.9
ghci> max "abc" "xyz"
"xyz"

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

ghci> max 10 45 - pred 8 + 4
42
ghci> (max 10 45) - (pred 8) + 4
42

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

ghci> max 45 (10 * pred 6) + 1
51

Заметьте, что выражение f f 3 означает вызов функции f с двумя аргументами — f и 3. Чтобы дважды применить функцию f, необходимо поставить скобки: f (f 3).

Иногда префиксные функции удобнее использовать в инфиксном варианте и наоборот. Например, функция div вычисляет частное двух целых чисел, но выражение div 18 3 + 5 теряет читаемость из-за префиксной записи. Для того, чтобы использовать любую функцию от двух аргументов (на самом деле от двух и более), достаточно поместить её имя в обратные кавычки:

ghci> div 18 3 + 5
11
ghci> 18 `div` 3 + 5
11

Чтобы использовать инфиксную функцию в префиксной записи, достаточно поместить её в круглые скобки:

ghci> 5 * 3 + 2
17
ghci> (+) (5 * 3) 2
17

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

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

Чтобы определить свою первую функцию, откройте текстовый редактор и запишите следующее:

triple x = x + x + x

Определение функции напоминает математическое уравнение, в левой части которого происходит вызов функции. Сохраните файл c именем my-functions.hs и запустите ghci из директории, в которой находится этот файл. Загрузите файл в GHCi:

ghci> :l my-functions
[1 of 1] Compiling Main             ( my-functions.hs, interpreted )
Ok, modules loaded: Main.
ghci> triple 3
9
ghci> triple (-4.5)
-13.5

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

sumOfSquares x y = x ^ 2 + y ^ 2

Добавьте эту функцию в my-functions.hs и снова загрузите файл при помощи :l my-functions:

ghci> sumOfSquares 3 4
25
ghci> triple (sumOfSquares 2 3)
39

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

absolute x = if x >= 0 then x else (-x)

Вероятно, вы встречались с условным оператором в других языках программирования. Отличие условного оператора в Haskell заключается в том, что выражение if a then b else c является выражением и может быть использовано в качестве подвыражения:

ghci> 1 + if ("cat" > "dog") then 2 else 3
4

То, что условный оператор является, на самом деле, условным выражением приводит к тому, что нельзя опустить ветку else. В императивных языках программирования, если ветка не указана и условие ложное, оператор просто не выполняется. В Haskell выражение обязано иметь значение и поэтому if False then 10 не может быть выражением.

В именах функций допускается символ ' (штрих), который помогает заменить имена вроде f1 на более математичное f':

absolute' x = if x > 0 then (-x) else x

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

what'sUp = "What's up, bro?!"

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

Упражнения

1.2 Реализуйте функцию my_factorial, вычисляющую факториал:

ghci> my_factorial 5
120

Списки

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

ghci> let list = [1, 2, 3]
ghci> list
[1, 2, 3]

Ключевое слово let используется в GHCi для определение новых функций или констант. Точно так же вы можете написать list = [1, 2, 3] в файле и загрузить определение в GHCi. Для временных констант вроде [1, 2, 3] обычно удобнее использовать let.

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

ghci> [1, 2, '3']

<interactive>:29:2:
    No instance for (Num Char)
      arising from the literal `1'
    Possible fix: add an instance declaration for (Num Char)
    In the expression: 1
    In the expression: [1, 2, '3']
    In an equation for `it': it = [1, 2, '3']

Естественно, символ '3' не является числом, о чём и говорится в этом сообщении. Тем не менее, мы могли бы составить список из символов:

ghci> ['1', '2', '3']
"123"

Как видите, строка в действительности является просто списком символов! То есть запись "str" является всего лишь синтаксическим сахаром для ['s', 't', 'r']. Поскольку строки являются списками, мы можем применять к ним любые функции над списками.

Довольно частой операцией со списками является конкатенация. Для этой операции используется оператор ++:

ghci> [1, 2, 3] ++ [4, 5, 6]
[1, 2, 3, 4, 5, 6]
ghci> "hello, " ++ "world!"
"hello, world!"
ghci> ['f', 'o', 'o'] ++ ['b', 'a', 'r']
"foobar"

Конкатенация списков — дорогая операция в том смысле, что второй список "дописывается" в конец первого. Для этого Haskell вынужден пройти до конца первого списка (чем длиннее список — тем дольше выполнение операции, даже если второй список короткий). Таким образом, добавление элемента в конец миллионного списка потребует значительного времени. С другой стороны, добавление в начало списка при помощи оператора : происходит мгновенно:

ghci> 1 : [2, 3]
[1, 2, 3]
ghci> 'c' : "at"
"cat"

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

ghci> [1, 2, 3] ++ [4]
[1, 2, 3, 4]

На самом деле, запись [1, 2, 3] является синтаксическим сахаром для 1 : 2 : 3 : [], где [] — пустой список. Заметьте, что [], [[]], [[], [], [] — не одно и то же! [] — пустой список, [[]] — список из одного элемента (которым является пустой список), [[], [], []] — список из трёх пустых списков.

Над списком определены две основные операции (помимо :) — head и tail. head возвращает первый элемент списка («голову» списка), а tail — весь список без первого элемента («хвост» списка):

ghci> head [1, 2, 3]
1
ghci> head "Hello!"
'H'
ghci> tail [1, 2, 3]
[2, 3]
ghci> tail ["element"]
[]
ghci> head (tail "abcde")
'b'
ghci> head "hello" : tail "hello"
"hello"

При попытке получить голову или хвост пустого списка, GHCi выведет сообщение об ошибке:

ghci> head []
*** Exception: Prelude.head: empty list

Проверить, является ли список пустым, можно при помощи функции null:

ghci> null [1, 2, 3]
False
ghci> let my_head 4 xs = if null xs then d else head xs
ghci> my_head 4 [1, 2, 3] 
1
ghci> my_head 4 []
4

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

ghci> [1, 2, 3, 4] !! 2
3

Нумерация ведется с нуля. Обратите внимание, что для вычисления list !! 1000000 Haskell должен пройти миллион элементов, чтобы достать из списка требуемый элемент.

Упражнения

1.1 Реализуйте функцию my_remove_second, удаляющую второй элемент из списка:

ghci> my_remove_second [1, 2, 3, 4]
[1, 3, 4]
ghci> my_remove_second "Hi"
"H"

1.2. Реализуйте функцию my_last, возвращающую последний элемент в списке:

ghci> my_last [1, 2, 3, 4, 5]
5
ghci> my_last "Hello!"
'!'

1.3. ★ Реализуйте функцию my_reverse, разворачивающую список:

ghci> my_reverse [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]

Кортежи

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

ghci> let x = (1, 2)
ghci> ('a', 1, "Hello, world!")
('a', 1, "Hello, world!")

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

ghci> fst ('a', 20)
'a'
ghci> snd (23, "hello")
"hello"
ghci> fst (snd (1, (2, 3)))
2