Изучай Haskell ради Добра! Синтаксис функций

Синтаксис функций

Сопоставление с образцом

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

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

lucky :: (Integral a) => a -> String

lucky 7 = "LUCKY NUMBER SEVEN!"

lucky x = "Sorry, you're out of luck, pal!"

Когда вы вызываете функцию lucky, происходит проверка параметра на совпадение с заданными шаблонами, в том порядке как они были заданы. Когда проверка даст положительный результат - используется соответствующее тело функции. Единственный случай, когда число переданное функции удовлетворяет первому шаблону - когда оно равно семи. Если нет, то происходит проверка на совпадение со следующим шаблоном. Следующий шаблон может быть успешно сопоставлен с любым числом, также он привязывает переданное число к переменной x.

Эта функция может быть реализована с использованием оператора if. Но что если нам потребуется написать функцию, которая называет цифры от 1 до 5, и выводит "Not between 1 and 5" для других чисел? Без сопоставления с образцом нам бы пришлось создать очень запутанное дерево выражений if then else. А вот что получится, если использовать сопоставление:

sayMe :: (Integral a) => a -> String

sayMe 1 = "One!"

sayMe 2 = "Two!"

sayMe 3 = "Three!"

sayMe 4 = "Four!"

sayMe 5 = "Five!"

sayMe x = "Not between 1 and 5"

Заметьте, что если бы мы переместили последний шаблон (который соответствует любому вводу) вверх, то функция всегда бы выводила "Not between 1 and 5", потому что этот шаблон подходит для любого числа, и невозможно было бы пройти дальше и сделать проверку на совпадение с другими шаблонами.

Помните реализованную нами функцию факториала? Мы определили факториал числа n как произведение чисел [1..n]. Мы можем определить данную функцию рекурсивно, точно так же, как факториал определяется в математике. Начнем с того, что объявим факториал нуля равным единице.

Затем определим факториал любого положительного числа как это число умноженное на факториал предыдущего числа. Вот как это транслируется в термины языка Haskell.

factorial :: (Integral a) => a -> a

factorial 0 = 1

factorial n = n * factorial (n - 1)

Это первый раз, когда мы задали функцию рекурсивно. Рекурсия очень важна в языке Haskell, и мы подробнее рассмотрим её позже. Но по сути, вот что происходит, когда мы пытаемся вычислить факториал числа 3: функция пробует вычислить 3 * factorial 2. factorial 2 - это 2 * factorial 1, таким образом, у нас получается 3 * (2 * factorial 1). factorial 1 - это 1 * factorial 0, и в итоге у нас 3 * (2 * (1 * (factorial 0))).

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

Финальный результат - 3 * (2 * (1 * 1)). Если бы мы написали второй шаблон выше первого, то он совпадал бы с любым числом, включая 0, и наше вычисление никогда бы не закончилось. Вот почему так важен порядок в котором вы задаете образцы, и всегда лучше задать сначала более частные случаи, а потом - более общие.

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

charName :: Char -> String

charName 'a' = "Albert"

charName 'b' = "Broseph"

charName 'c' = "Cecil"

а затем попытаемся вызвать её с параметром, который не ожидали, и вот что произойдет:

ghci> charName 'a'

"Albert"

ghci> charName 'b'

"Broseph"

ghci> charName 'h'

"*** Exception: tut.hs:(53,0)-(55,21): Non-exhaustive patterns in function charName

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

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

addVectors :: (Num a) => (a, a) -> (a, a) -> (a, a)

addVectors a b = (fst a + fst b, snd a + snd b)

Это, конечно, работает, но есть способ лучше. Давайте исправим функцию, чтобы она использовала сопоставление с образцом.

addVectors :: (Num a) => (a, a) -> (a, a) -> (a, a)

addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

Вот так то! Намного лучше. Заметьте, что у нас имеется общий образец. Тип функции addVectors (в обоих случаях) - (Num a) => (a, a) -> (a, a) -> (a, a), так что мы гарантировано получим две пары на входе.

Функции fst и snd извлекают компоненты пары. Но как насчет троек? Ну, стандартных функций для этой цели не существует, но мы можем создать свои.

first :: (a, b, c) -> a

first (x, _, _) = x

second :: (a, b, c) -> b

second (_, y, _) = y

third :: (a, b, c) -> c

third (_, _, z) = z

Символ _ имеет то же значение, что и в выражениях списков. Этот символ означает, что нам не интересно значение на этом месте, так что мы просто пишем _.

Это напомнило мне, что вы можете использовать сопоставление с образцом в списковых выражениях. Смотрите:

ghci> let xs = [(1,3), (4,3), (2,4), (5,3), (5,6), (3,1)]

ghci> [a+b | (a,b) <- xs]

[4,7,6,8,11,4]

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

Списки сами по себе (т.е. заданные прямо в тексте шаблона, списковые литералы) могут быть использованы при сопоставлении с образцом. Вы можете сравнивать с пустым списком или с любым шаблоном который включает : и пустой список. Так как [1,2,3] это просто синтактический сахар (упрощенная запись) для 1:2:3:[], вы можете использовать [1,2,3] как шаблон.

Образец вида x:xs связывает голову списка с x, а оставшуюся часть с xs, даже если в списке всего один элемент; в этом случае xs - пустой список.

Замечание: Образец x:xs используется очень часто, особенно с рекурсивными функциями. Образцы, у которых присутствует ":" в определении, могут быть использованы только для списков, длина которых равна единице или больше.

Если вы, скажем, хотите связать первые три элемента с переменными, а оставшиеся элементы списка с другой переменной, вы можете использовать что-то наподобие x:y:z:zs. Образец сработает только для списков, в которых три или более элементов.

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

head' :: [a] -> a

head' [] = error "Can't call head on an empty list, dummy!"

head' (x:_) = x

Проверяем, работает ли:

ghci> head' [4,5,6]

4

ghci> head' "Hello"

'H'

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

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

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

tell :: (Show a) => [a] -> String

tell [] = "The list is empty"

tell (x:[]) = "The list has one element: " ++ show x

tell (x:y:[]) = "The list has two elements: " ++ show x ++ " and " ++ show y

tell (x:y:_) = "This list is long. The first two elements are: " ++ show x ++ " and " ++ show y

Эта функция безопасна, потому что она обрабатывает случаи, когда входной список пуст, содержит один, два и более элементов. Обратите внимание, что (x:[]) и (x:y:[]) могут быть записаны как [x] и [x,y] (так как это облегченная запись, нам не нужны круглые скобки). Мы не можем записать (x:y:_) с помощью квадратных скобок, потому что такая запись соответствует любому списку длиной два или более.

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

length' :: (Num b) => [a] -> b

length' [] = 0

length' (_:xs) = 1 + length' xs

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

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

Посмотрим что произойдет если мы вызовем length' на "ham". Во-первых, произойдет проверка, пустой список или нет. Так как список не пустой, будет проверяться второй шаблон. Список соответствует второму шаблону, следовательно, он разбивается на голову и хвост, длина получается равна 1 + length' "am". Океюшки.

Длина "am", таким же образом, это 1 + length' "m". Длина "m" - это 1 + length' "" (также может быть записано как 1 + length' []). Мы определили length' [] как равную нулю. Таким образом, в конце получаем 1 + (1 + (1 + 0)).

Давайте реализуем sum. Мы знаем, что сумма элементов пустого списка равна нулю. Запишем это в виде шаблона. Также ясно, что сумма элементов списка - это значение из головы списка плюс сумма всех остальных элементов. Если все это записать, у нас получится так:

sum' :: (Num a) => [a] -> a

sum' [] = 0

sum' (x:xs) = x + sum' xs

Есть еще одна конструкция, которая называется as-образцом. Это удобный способ разбить что-нибудь в соответствии с шаблоном и связать результат разбиения с переменными, но в то же время сохранить ссылку на исходные данные. Это можно сделать если поместить имя и @ перед образцом. Например, шаблон xs@(x:y:ys).

Такой шаблон работает так же как x:y:ys, но вы легко можете получить исходный список по имени xs, вместо того, чтобы раз за разом печатать x:y:ys в теле функции. Вот пример на скорую руку:

capital :: String -> String

capital "" = "Empty string, whoops!"

capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]

ghci> capital "Dracula"