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

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

Предыдущие статьи:
Основы
Последующие статьи:
Классы типов, монады

Предисловие

Файлы имеют расширение .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, автоматом делающее релоад при изменениях, но я пользуюсь просто редактором с подсветкой.

Типы данных

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

data Color = Red | Green | Blue

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

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

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

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

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

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

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

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

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

Определение функций и паттерн матчинг (сопоставление с образцом)

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

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

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

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

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

x = 4
wrong x = True
wrong _ = False

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

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

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

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

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

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

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

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

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

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

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

listHead Null = error "listHead: empty list"
listHead (Cons x _) = x

ghci> listHead Null
*** Exception: listHead: empty list

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

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

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

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

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

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

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

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

infixr 5 @++

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

lst `atIndex` n = lst !! n

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

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

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

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

Здесь в качестве функции свёртки используется лямбда. Лямбда — это анонимная функции, записывается как \arg1 arg2 argN -> expr. В ней так же можно использовать сопоставление с образцом, но только с одним, т.е. записать несколько вариантов для нескольких образцов не получится, но если нужно, всегда можно воспользоваться case ... of.
Рассмотрим подробнее записанную здесь лямбду \x -> Cons with.Cons x, она принимает некое значение, а возвращает функцию, которая прицепляет к списку сам этот элемент, а затем элемент with, в результате мы получаем список Cons with (Cons x ...)
Т.е. каждый элемент, кроме первого, предваряется элементом with.
Ну а теперь уже просто определить функцию преобразования списка в строку:

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

listMap show lst
Преобразует все элементы списка в строки
listInterpserse ","
Между элементами вставляет запятую,
listFoldr (++) ""
соедниняет все строки в одну и с краёв мы добавляем скобки. Проверяем:

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

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