Язык Haskell, введение

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

Статическая типизация означает, что в процессе сборки программы все выражения проверяются на корректность путём сопоставления каждому выражению его “типа” по некоторому естественному набору правил. Программы, в которых присутствуют выражения, которым нельзя сопоставить никакой тип, отвергаются во время сборки. Строгая типизация означает отсутствие неявных преобразований типов (например, в языке Си величины типа int можно подставить туда, где ожидается величина типа double; в Хаскелле такое запрещено).

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

Где взять Haskell?

По ссылке. Нужно нечто под названием Haskell Platform.

Что ещё почитать?

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

Как пользоваться?

В состав Haskell Platform входит компилятор GHC и некоторый набор полезных библиотек. Компилятор GHC состоит из двух приложений: ghc и ghci. Первое – преобразователь файлов с текстом программы в исполняемый файл. Второй – интерактивный режим (далее будем называть его словом “интерпретатор”).

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

module Foo where

square x = x*x

после чего файл открывается в интерпретаторе. Интерпретатор позволяет вычислять значения выражений. Например, если загрузить в интерпретатор файл с вышеприведённым содержимым, то можно набрать square (2+3*4) и получить ответ 196.

При изменении содержимого файла Foo.hs можно его перезагрузить в интерпретатор командой :r.

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

Программа на языке Haskell состоит из одного или нескольких файлов. Каждый файл содержит строчку вида

module название_модуля where

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

module Main where

В программе

module Foo where

square x = x*x

определена ровно одна функция с названием square, возводящая поданное на вход число в квадрат. Это – простейший вид определения функции, имеющий вид

название_функции вход_1 вход_2 ... вход_n = значение

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

Более сложное определение может выглядеть так:

square :: Integer -> Integer
square x = x*x

Здесь явно указано, что square преобразует целое число в целое число. Попытка подставить в такую функцию square нецелое число приведёт к ошибке типизации.

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

:t square

то интерпретатор напечатает

square :: Num a => a -> a

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

Для второго определения функции square будет напечатано

square :: Integer -> Integer

Основные типы данных

Полезно знать про следующие типы данных:

Integer – целое число произвольной величины
Int – целое число, величина которого определяется разрядностью процессора (обычно соответствует типу long языка Си)
Double – дробное число двойной точности (тип double в языке Си)
Bool – True или False
Char – один текстовый символ (не является числом, в отличие от Си)

Функции, преобразующие величину типа a в величину типа b, имеют тип a -> b. Функции с несколькими входами в Хаскелле принято моделировать как функции с одним входом. Например, функция сложения целых чисел будет иметь тип

Integer -> (Integer -> Integer)

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

Для удобства скобки в подобных типах можно опускать, записывая просто

Integer -> Integer -> Integer

Множественные правые части

Посмотрим на следующую реализацию абсолютной величины:

абсолютнаяВеличина x
  | x < 0 = -x
  | True  = x

В процессе вычисления условия x < 0 и True проверяются по очереди сверху вниз. Используется правая часть, соответствующая первому из истинных условий. Отсутствие истинных условий приводит к ошибке.

По большей части Haskell нечувствителен к отступам. Но есть слова do, let, of, where, начинающие “блок”. Все элементы блока обязаны начинаться в одной и той же колонке; те из них, которые не помещаются в одну строчку, могут быть продолжены на следующих строчках в колонках строго правее начальной.

В частности, строчка module Foo where начинает блок, элементами которого являются все определения. Поэтому, если хотя бы одно определение было начато с первой колонки, все остальные тоже должны начинаться с первой колонки, а их составные части должны находиться строго правее первой колонки.

Множественные уравнения

Все “операции” в Хаскелле делятся на функции и конструкторы данных. На первых порах мы будем рассматривать только два конструктора, соответствующих типу данных “последовательность”. Эти конструкторы: [] и (:) (второй может быть использован как инфиксный оператор :).

Типы этих конструкторов такие:

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

Обозначение [a] используется для типа “последовательность объектов типа a”. Сами последовательности, как нетрудно догадаться по типам этих “операций”, имеют вид

x_1:(x_2: ... :(x_n:[])..)

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

x_1:x_2:... :x_n:[]

Различие между конструкторами и функциями – способ их вычисления. Вычисление функции происходит заменой левой части определения на правую (обычный ленивый порядок, почти как в лямбда-исчислении). Конструкторы не вычисляются. Зато их можно использовать в левых частях определений. Например, функция, вычисляющая длину последовательности, может быть реализована так:

длина []     = 0
длина (x:xs) = 1 + длина xs

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

длина (6:1:2:2:[])
1 + длина (1:2:2:[])
1 + (1 + длина (2:2:[]))
1 + (1 + (1 + длина (2:[]))))
1 + (1 + (1 + (1 + длина [])))
1 + (1 + (1 + (1 + 0)))
1 + (1 + (1 + 1))
1 + (1 + 2)
1 + 3
4

Более хитрое определение: конкатенация (слияние) последовательностей.

конкатенация []     y = y
конкатенация (x:xs) y = x : конкатенация xs y

Вычисляется это так:

конкатенация (1:2:3:[]) (4:5:6:[])
1 : конкатенация (2:3:[]) (4:5:6:[])

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

сумма [] = 0
сумма (x:xs) = x + сумма xs

Следите внимательно:

сумма (конкатенация (1:2:3:[]) (4:5:6:[]))
сумма (1 : конкатенация (2:3:[]) (4:5:6:[]))
1 + сумма (конкатенация (2:3:[]) (4:5:6:[]))
1 + сумма (2 : конкатенация (3:[]) (4:5:6:[]))
1 + (2 + сумма (конкатенация (3:[]) (4:5:6:[])))
1 + (2 + сумма (3 : конкатенация [] (4:5:6:[])))
1 + (2 + (3 + сумма (конкатенация [] (4:5:6:[]))))
1 + (2 + (3 + сумма (4:5:6:[])))
1 + (2 + (3 + (4 + сумма (5:6:[]))))
1 + (2 + (3 + (4 + (5 + сумма (6:[])))))
1 + (2 + (3 + (4 + (5 + (6 + сумма [])))))
1 + (2 + (3 + (4 + (5 + (6 + 0)))))
1 + (2 + (3 + (4 + (5 + 6))))
1 + (2 + (3 + (4 + 11)))
1 + (2 + (3 + 15))
1 + (2 + 18)
1 + 20
21

Некоторые обозначения и прочее

Для последовательностей вида x_1:x_2:... :x_n:[] есть краткая запись [x_1,x_2,...,x_n]. Если x_i – символы типа Char, то используется запись "x_1x_2...x_n". Например:

'В' : 'а' : 'с' : 'я' : []
то же самое, что
['В', 'а', 'с', 'я']
что то же самое, что
"Вася"

Для арифметических прогрессий есть специальные сокращения:

[5..]   -- [5,6,7,8,  и т.д.]
[5,7..] -- [5,7,9,11, и т.д.]
[5..9]  -- [5,6,7,8,9]

Комментарии в тексте программы выделяются так:

-- комментарий до конца строчки

{- Многострочный
   комментарий -}

Отрицательные числа приходится иногда заключать в скобки:

square -5   -- воспринимается как (square - 5)
square (-5) -- правильный способ записи

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

square square square 4  -- читается как ((square square) square) 4 и 
                        -- отвергается при проверке типов
square (square (square 4)) -- правильно, но много скобок

по этой причине есть правоассоциативный оператор применения $:

square $ square $ square 4  -- так гораздо лучше

Лямбда-выражения имеют следующий вид:

\x -> x*x  -- это аналог square

\x -> \y -> x + y  -- сумма 

\x y -> x + y  -- в точности то же самое, но запись короче

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

Арифметика

плюс, минус, умножить, поделить: +, -, *, /;
целая степень: ^
сравнение: ==, /= (sic!), <, >, <=, >=
целочисленное деление: div, mod (не инфиксные!)

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

11 `mod` 5  -- одиннадцать по модулю пяти

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

(+) 3 4  -- три плюс четыре

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

x ++ y – конкатенация последовательностей
repeat x – последовательность x:x:x:x:...
iterate f x – последовательность x:f x:f (f x):f (f (f x)):...
take n x – первые n элементов последовательности x
drop n x – элементы последовательности x, кроме первых n
f <$> x – последовательность, полученная из x применением f к каждому её элементу
fmap f x – то же самое
filter p x – последовательность таких элементов последовательности x, для которых выполнено свойство p

Упражнения (задание на каникулы)

Реализуйте функцию, вычисляющую факториал поданного на вход числа;

factorial n
  | n > 0 = n * factorial (n-1)
  | True  = 1

Реализуйте функцию, реализующую проверку числа на простоту;

isPrime n 
  | n < 2 = False
  | True  = isPrimeLoop 2 n

isPrimeLoop k n
  | k*k > n        = True
  | n `mod` k == 0 = False
  | True           = isPrimeLoop (k+1) n

Попробуйте каждую из вышеупомянутых функций из раздела “Последовательности”;
Реализуйте каждую из них самостоятельно, не используя никаких вспомогательных функций.

[] ++ y     = y
(x:xs) ++ y = x : (xs ++ y)

repeat x = x : repeat x

iterate f x = x : iterate f (f x)

take n [] = []
take n (x:xs)
  | n > 0 = x : take (n-1) xs
  | True  = []

drop n [] = []
drop n a@(x:xs) -- а вот так можно вводить обозначение для части шаблона
  | n > 0 = drop (n-1) xs
  | True  = a  


f <$> []     = []
f <$> (x:xs) = f x : (f <$> xs)

filter p [] = []
filter p (x:xs)
  | p x  = x : filter p xs
  | True = filter p xs