Основы

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

Последующие статьи:
Типы данных, паттерн матчинг и функции
Классы типов, монады

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

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

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

Prelude> :s prompt "ghci> "
ghci>


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

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

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

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

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


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

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


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

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]


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

Функции

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

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


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

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


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

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


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

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


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

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


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

ghci> (max 2) 4
4


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

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


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

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


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

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


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

ghci> let max2 = max 2


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

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


Куда-то подевалось 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


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

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


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

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


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

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


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

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


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

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

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


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


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

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


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

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


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

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


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

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


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

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


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

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


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


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

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


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

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


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

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


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

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


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

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

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

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"


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

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

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


Чтобы это остановить, нажмите 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]


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

ghci> (last.reverse) lst


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

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


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

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

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

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


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

substr from len str = (take len . drop from) str
-- Опускаем str слева и справа
substr from len = take len . drop from
substr from len = (.) (take len) (drop from)
-- Меняем местами (take len) и (drop from), чтобы len оказался справа
substr from len = flip(.) (drop from) (take len)
-- Сначала к len применяется take, потом (flip(.) (drop from))
-- запишем это с использованием (.)
substr from len = ((flip(.) (drop from)).take) len
-- Убираем len
substr from = (flip(.) (drop from)).take
-- Точку перед take выносим в начало
substr from = (.) (flip(.) (drop from)) take
-- Меняем местами аргументы, чтобы выражение,
-- содержащее from стояло справа
substr from = flip(.) take (flip(.) (drop from))
-- К from применяются последовательно: drop, flip(.), (flip(.)take),
-- так и запишем
substr from = ((flip(.) take).flip(.).drop) from
-- Убираем from
substr = (flip(.)take).flip(.).drop


Проверим:

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


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

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