Haskell. Основы

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

02 Поэтому я захотел написать серию статей, в течение которых мы изучим возможности языка и попробуем написать простой чат. Почему именно чат? Потому что там есть место и многопоточности, и GUI клиента, и БД сервера. Хотя я с удовольствием послушал бы и ваши предложения, так как мне самому интересно, насколько этот язык удобен для решения более сложных задач.

Компилятор и интерпретатор

03 Для начала необходимо скачать и установить Glasgow Haskell Compiler (GHC). На данный момент можно взять последнюю версию, но wxHaskell, к сожалению, предоставляет бинарники для каждой платформы под разные версии GHC. В добавок, какой-то он сырой (wxHaskell), так что у меня лично GHC стоит как 6.10.1 версии, так и 6.8.3.

04 В GHC есть три основные программы: ghc — компилятор, ghci — интерпретатор, и runghc — позволяет запускать программы как скрипты без предварительной компиляции. Для редактирования исходников я использую HippoEDIT, хотя подойдёт любой редактор, где есть подсветка и можно настроить вызов сторонней программы для файла.

05 По умолчанию приглашение в ghci содержит список загруженных модулей. Чтобы не загромождать, его можно изменить:

Prelude> :s prompt "ghci> "
ghci>

06 Хаскель является чистым и ленивым функциональным языком; это значит, что результат функции зависит только от аргументов, т. е. будучи вызванной с одним аргументом, функция всегда вернёт один и тот же результат. Поэтому здесь нет переменных — есть функции и значения — однако это никак не мешает. Ленивость означает, что значение будет вычислено только тогда, когда оно действительно понадобится, что позволяет работать с бесконечными списками и структурами данных.

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

Основные типы

08 Char — символьный тип;
Bool — True или False;
Int — целочисленное. Его размер может быть 32 бита или 64 на соответствующей архитектуре;
Integer — «бесконечное» целое;
Double — дробное (с плавающей точкой).

09 Можно проверить тип выражения при помощи команды :t.

ghci> :t ’x’
’x’ :: Char
gchi> :t True
True :: Bool
ghci> :t 5
5 :: (Num t) => t

10 Оказывается, 5 имеет тип не Int. Эта запись означает примерно «5 может иметь любой тип t, если он принадлежит классу Num». О классах я напишу позже, пока можно сделать вывод, что 5 может, в зависимости от ситуации, принимать разный тип (в том числе и пользовательский). Указать конкретный тип (не обязательно отдельного значения, можно и целого выражения) можно так:

ghci> :t 5::Int
5::Int :: Int
ghci> :t (5 + 6 * 3)::Int
(5 + 6 * 3)::Int :: Int

11 Разумеется, есть списки и кортежи. Список может содержать элементы одного типа и иметь произвольную длину, тогда как кортеж — разного, и количество элементов фиксировано в его типе.

ghci> :t (True, ’f’)
(True, ’f’) :: (Bool, Char)
ghci> :t (False, 5::Int, ’q’)
(False, 5, ’q’) :: (Bool, Int , Char)
ghci> :t [’h’,’e’,’l’,’l’,’o’]
[’h’,’e’,’l’,’l’,’o’] :: [Char]
ghci> :t "hello"
"hello" :: [Char]

12 Из последнего можно сделать вывод, что строка — это список символов, и над ней определены все те же операции, что и над списками.

Функции

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

ghci> odd 5
True
ghci> max 4 5
5
ghci> lines "first line\nsecond line"
["first line","second line"]
ghci> "left" ++ "right"
"leftright"

14 ++ — это оператор, но это также обычная функция, которую можно использовать и так:

ghci> (++) "left" "right"
"leftright"

15 Посмотрим тип функции:

gchi> :t lines
lines :: String -> [String]

16 Он записывается через стрелку и означает, что lines берёт строку, а возращает список строк.

ghci> :t max
max :: (Ord a) => a -> a -> a

17 Таким образом, max определён для любого a, принадлежащего к классу Ord, принимает два аргумента одного типа и возвращает результат того же типа. Но тип функции можно представить и так:

max :: (Ord a) => a -> (a -> a)

18 И тут мы встречаем currying. Получается, что max принимает один аргумент и возвращает функцию типа (a -> a). Любую функцию можно представить, как принимающую один аргумент и возвращающую другую функцию.

ghci> (max 2) 4
4

19 То же верно и для операторов:

ghci> ((++) "left")  "right"
"leftright"

20 Но в случае оператора можно записать и так:

ghci> ("left" ++) "right"
"leftright"
ghci> (++ "right") "left"
"leftright"

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

ghci> 2 `max` 4
4
ghci> (2 `max`) 4
4

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

ghci> let max2 = max 2

24 Несмотря на то, что язык строгий, зачастую аннотации типов можно опустить, так как Хаскель умеет выводить типы. Однако, если посмотреть тип max2, мы увидим нечто странное:

ghci> :t max2
max2 :: Integer -> Integer

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

ghci> let max2 x = max 2 x
ghci> :t max2
max2 :: (Ord t, Num t) -> t -> t
ghci> max2 3.6
3.6

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

ghci> let applyFunc f1 f2 x = f1 (f2 x)
ghci> applyFunc (*3) (/2) 5
7.5

27 В качестве первой функции мы передаём (*3), т. е. функцию, которая принимает число и умножает его на 3, в качестве второй — функцию, делящую на два. В результате применения их последовательно к 5, мы и получаем 7.5.

ghci> :t applyFunc
applyFunc :: (t1 -> t2) -> (t -> t1) -> t -> t2

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

ghci> (not.odd) 5
False
ghci> (not.odd.(+1)) 5
True

29 В первом случае сначала применяется функция odd, а затем not. Ну а во втором изначально добавляется единица. В данном случае это кажется ненужным, но вспомним, что функции могут принимать другие функции, и когда требуется «на лету» создать сложную функцию из примитивов, то такие композиционные операции очень пригождаются. Ещё одна такая полезная функция flip, меняет местами аргументы:

ghci> (-) 2 3
-1
ghci> (flip (-)) 3 2
-1

Операции над списками

30 Рассмотрим основные списочные операции. Список состоит из головы и хвоста и создаётся конструктором : (двуеточие).

ghci> 5:6:[]
[5,6]

head :: [a] -> a
tail :: [a] -> [a]

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

32 last :: [a] -> a
init :: [a] -> [a]

— Возвращают последний элемент и список без последнего элемента.

33 take :: Int -> [a] -> [a]

— Возвращает первые n элементов.

34 drop :: Int -> [a] -> [a]

— Отбрасывает первые n элементов и возвращает оставшиеся.

35 null :: [a] -> Bool -- проверяет список на наличие элементов
length :: [a] -> Int -- возвращает количество элементов
reverse :: [a] -> [a] -- переворачивает список
map :: (a -> b) -> [a] -> [b]

36 — map принимает функцию и применяет её к каждому элементу списка, на выходе мы получаем новый список:

ghci> map (*2) [1, 2, 3] [2,4,6]

37 Подключим модуль Data.Char: (там определена, в частности, функция toUpper)

ghci> :m + Data.Char
ghci> map toUpper "hello"
"HELLO"

38 filter :: (a -> Bool) -> [a] -> [a]

— Принимает предикат и оставляет только те элементы, которые ему удовлетворяют.

foldl :: (a -> b -> a) -> a -> [b] -> a
foldr :: (a -> b -> b) -> b -> [a] -> b

39 Свёртку проще показать на примере:

ghci> foldr (+) 0 [1, 2, 3, 4]
10

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

f (f (f (f 0 1) 2) 3) 4 -- foldl
f 4 (f 3 (f 2 (f 1 0))) -- foldr

41 В терминах этой функции можно определить множество остальных:

product :: Num a => [a] -> a
product = foldr (*) 1
maximum lst = foldr max (head lst) (tail lst)

42 Есть ещё множество полезных функций, полный их список можно посмотреть в документации.

43 В отношении функций термины «принимает» и «возвращает» не совсем точны, так как функция не вычисляется сразу из-за ленивости, но более подходящих слов я не нашёл.

44 Для списка определён удобный синтаксический сахар:

ghci> [1..10]
[1,2,3,4,5,6,7,8,9,10]
ghci> [1,3..10]
[1,3,5,7,9]
ghci> ['a'..'d']
"abcd"

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

Бесконечные списки

46 ghci> [1..]
[1,2,3,4Interrupted.

47 Чтобы это остановить, нажмите Ctrl-C. На самом деле, у меня успело вывести до 622, но я тут этого отражать не стал. С этим списком можно работать как обычно. Например, можно возвести каждый элемент в квадрат, взять только чётные.

ghci> let lst = [1..]
ghci> let filteredLst = filter even (map (^2) lst)
ghci> take 10 filteredLst
[4,16,36,64,100,144,196,256,324,400]

48 Конечно, вычислить длину такого списка или развернуть его (reverse) не получится, но это, как правило, и не нужно.

ghci> (last.reverse) lst

49 Здесь нам тоже не повезёт. Хотя мы-то с вами понимаем, что последний элемент перевёрнутого списка — это первый элемент изначального, компилятор до этого догадаться не может; а ленивость в данном случае не помогает. Бесконечный список можно определить и через корекурсию — операцию, подобную рекурсии, но не свёртывающую структуру данных (уменьшение значения аргумента тоже можно назвать свёртыванием), а «развёртывающую» результат (Total FP) на основе изначальных аргументов:

ghci> let ones = 1 : ones
ghci> take 5 ones
[1,1,1,1,1]

50 Благодаря ленивости, полученная бесконечная структура данных (в данном случае ones — это список, в голове которого находится 1, а в хвосте — сам ones, т. е. это бесконечный список единиц) не вычисляется без необходимости, и ей можно пользоваться как обычно. Где это может пригодиться на практике? Например, в строгих языках необходимо заранее знать количество элементов списка, что заставляет в месте создания списка знать лишнюю деталь реализации. Либо приходится создавать какой-нибудь генератор, который вызовут уже «наверху». Здесь же мы можем просто создать бесконечный список, а нужную часть из него возьмут тогда, когда она потребуется.

51 Ну а теперь зарядка для ума:

ghci> let substr from len str = take len (drop from str)
ghci> substr 2 3 "01234567"
"234"

52 Сделаем преобразования:

substr from len str = (take len . drop from) str

53 Опускаем str слева и справа:

substr from len = take len . drop from
substr from len = (.) (take len) (drop from)

54 Меняем местами (take len) и (drop from), чтобы len оказался справа:

substr from len = flip(.) (drop from) (take len)

55 Сначала к len применяется take, потом (flip(.) (drop from)). Запишем это с использованием (.):

substr from len = ((flip(.) (drop from)).take) len

56 Убираем len:

substr from = (flip(.) (drop from)).take

57 Точку перед take выносим в начало:

substr from = (.) (flip(.) (drop from)) take

58 Меняем местами аргументы, чтобы выражение, содержащее from, стояло справа:

substr from = flip(.) take (flip(.) (drop from))

59 К from применяются последовательно: drop, flip(.), (flip(.)take), так и запишем:

substr from = ((flip(.) take).flip(.).drop) from

60 Убираем from:

substr = (flip(.)take).flip(.).drop

61Проверим:

ghci> let substr = (flip(.)take).flip(.).drop
ghci> substr 2 3 "01234567"
"234"

Практического значения это, конечно, не имеет, но по-моему достаточно забавно :-)