Haskell. Типы данных, паттерн матчинг и функции

Файлы имеют расширение .hs или .lhs (для Literate Haskell, с обратным способом записи комментариев и кода). Чтобы загрузить их в интерпретатор, можно либо вызвать его ghci file.hs, либо уже при работе с ним использовать команды :cd и :l.

gchi> :cd c:/some/haskell
ghci> :l file.hs
[1 of 1] Compiling Main ( file.hs, interpreted )
Ok, modules loaded: Main.
ghci>

Наверняка есть удобное IDE, автоматом делающее релоад при изменениях, но я пользуюсь просто редактором с подсветкой.

Типы данных

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

data Color = Red | Green | Blue

03 Конструкторы могут содержать параметры:

import Data.Word (Word8) -- импортируем Word8 из модуля Data.Word
data Color = Red | Green | Blue | Custom Word8 Word8 Word8

04 Кроме того, сам тип может быть параметризован используемым типом. Например, список:

data List a = Null | Cons a (List a)

05 Т. е. список элементов a либо пуст, либо состоит из (головы) a и (хвоста) List a. В описании конструктора можно использовать такой сахар:

data List a = Null |  Cons { listHead :: a, listTail :: List a }

06 Что автоматически определяет две функции:

listHead :: List a -> a
listTail :: List a -> List a

Которые элементарно реализуются.

Определение функций и паттерн матчинг

07 Определим полезные функции над нашим списком:

length Null = 0
length  (Cons _ xs) = 1 + length xs

08 Здесь я использовал сопоставление с образцом. Параметры функции последовательно (порядок определения важен) сравниваются с образцами (Null и Cons _ xs) и выбирается подходящий вариант. _ означает любое значение, но нам неважное. Т. е. Cons _ xs проходит для любого непустого списка. Образец может быть сколь угодно сложным:

someFunc (Cons 5 (Cons _ (Cons 3 (Cons _ Null)))) = True
someFunc _ = False

09 Но в нём можно использовать только конструкторы (и встроенные литералы). Т. е. в данном примере:

x = 4
wrong x = True
wrong _ = False

10 Первый вариант всегда сработает, так как x — это свободное имя, а не то значение, которое определено, как 4. Если одновременно с «разобранным» по частям образцом нам нужен и сам параметр функции (чтобы не собирать всё обратно, если вдруг нам это понадобится), то можно записать так:

someFunc v@(Cons 5 (Cons _ (Cons 3 (Cons _ Null)))) = -- v — параметр функции, сопоставленный с образцом

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

someFunc2 n = case n of
  Null -> "Null"
  Cons _ Null -> "One"
  Cons _ (Cons x _)
     | x == 0 -> "0"
     | x == 1 -> "1"
     | otherwise -> "otherwise" -- otherwise определена как True

12 Последние три строки в примере выше — это так называемые pattern guards. Когда значение подпадает под последний образец (в данном случае, вообще, он не обязан быть последним и pattern guards можно написать для каждого образца), то далее выбирается тот из вариантов, который даёт True. Тот же механизм работает и для функций:

someFunc3 (x:xs)
   | isSomePredicate x = xs
   | x == 0 = []
   | otherwise = (x:xs)

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

someFunc4 (x:xs)
   | (2:ys) <- filter even xs = ys -- подсписок чётных начинается с 2 и непуст
   | (4:y:[]) <- xs = [y] -- xs состоит из 2-х элементов, первый — 4
   | otherwise = (x:xs)

14 Если образцы не способы покрыть все возможные значения, а оно таки там появится, то вылетит исключение. В частности, listHead (и стандартный head тоже) не способен обработать пустой список:

ghci> listHead Null
*** Exception: No match in record selector Main.listHead
ghci> head []
*** Exception: Prelude.head: empty list

15 Второй вариант даёт побольше информации, потому что на самом деле head для пустого списка определён, но он кидает исключение. Для таких случаев можно использовать стандартную функцию error:

listHead Null = error "listHead: empty list"
listHead (Cons x _) = x
ghci> listHead Null
*** Exception: listHead: empty list

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

listMap f Null = Null
listMap f (Cons x xs) = Cons (f x) (listMap f xs)

listFilter p Null = Null
listFilter p (Cons x xs)
   | p x = Cons x (listFilter p xs)
   | otherwise = listFilter p xs

listFoldr f v Null = v
listFoldr f v (Cons x xs) = f x $ listFoldr f v xs

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

foo (bar 3 (baz 56 "x"))

можно писать

foo $ bar 3 $ baz 56 "x"

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

Null @++ right = right
(@++) left Null = left
(Cons l ls) @++ right = Cons l (ls @++ right)

19 Дополнительно можно назначить оператору приоритет и левую или правую ассоциативность. С помощью ключевых слов infixl и infixr соответственно. Чтобы узнать приоритет оператора, в интерпретаторе можно воспользоваться командой :i

ghci> :i (++)
(++) :: [a] -> [a] -> [a] -- Defined in GHC.Base
infixr 5 ++

20 5 — это приоритет от 1 до 9, чем он больше, тем приоритет выше. Так как наш оператор аналогичен (++), то и приоритет ему поставим такой же.

infixr 5 @++

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

lst `atIndex` n = lst !! n

22 Определим вспомогательные функции для удобства

toList Null = []
toList (Cons x xs) = x:(toList xs)
fromList [] = Null
fromList (x:xs) = Cons x (fromList xs)

23 Напоследок напишем функцию, которая преобразует наш список в строку так же, как это работает и для обычного списка. Для этого сначала напишем функцию, которая вставляет дополнительный элемент между элементами списка, т. е. из [1,2,3] делает [1,5,2,5,3] (если вставляемый элемент 5):

listIntersperse with Null = Null
listIntersperse with (Cons x xs) = Cons x $ listFoldr (\x -> Cons with . Cons x) Null xs

24 Здесь в качестве функции свёртки используется лямбда. Лямбда — это анонимная функция, записывается как
\arg1 arg2 argN -> expr. В ней так же можно использовать сопоставление с образцом, но только с одним, т. е. записать несколько вариантов для нескольких образцов не получится, но если нужно, всегда можно воспользоваться case ... of.

25 Рассмотрим подробнее записанную здесь лямбду \x -> Cons with.Cons x, она принимает некое значение, а возвращает функцию, которая прицепляет к списку сам этот элемент, а затем элемент with, в результате мы получаем список Cons with (Cons x ...).

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

listShow lst = "[" ++ (listFoldr (++) "" $ listIntersperse "," $ listMap show lst) ++ "]"

listMap show lst

— Преобразует все элементы списка в строки;

27 listInterpserse ","

— Между элементами вставляет запятую;

28 listFoldr (++) ""

— Соединяет все строки в одну и с краёв мы добавляем скобки. Проверяем:

29 ghci> show [1,2,3] == listShow (fromList [1,2,3])
True

В следующий раз я расскажу про классы типов и про некоторые стандартные из них.