Структуры данных и их типы

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

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

Список — ещё одно понятие функционального программирования. В абстрактной математической записи использовались квадратные скобки [], которые также используются в Хаскеле. Но в Лиспе используются обычные, круглые скобки (). Элементы списка в Лиспе разделяются пробелами, что не очень наглядно, поэтому в Хаскеле ввели запятую для разделения. Список [a, b, c] будет правильно записан в синтаксисе Хаскела, а в нотацию Лиспа его необходимо перевести как (a b c). Создатели Лиспа пошли ещё дальше в своей изощрённости: допускается использовать точечную запись для организации пары, поэтому приведённый выше список можно записать как (a.(b.(c.NIL))) (в Хаскел это будет выглядеть как a:b:c:[] или (a:(b:(c:[])))).

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

Как говорилось во вводной лекции, типы данных в функциональных языках определяются автоматически. Механизм автоматического определения встроен и в Хаскел, но в некоторых случаях нужно явно указывать тип, иначе интерпретатор может запутаться в неоднозначности. В Хаскеле используется специальный символ :: (два двоеточия), котрый читается как «имеет тип». То есть если написать:

5 :: Integer

Это будет читаться как «Числовая константа 5 имеет тип Целое число».

Ещё Хаскел поддерживает полиморфные типы, или шаблоны типов. Если, например, записать [a], то это будет обозначать тип «список из атомов любого типа», причём тип атомов должен быть один во всём списке. Списки [1, 2, 3] и ['a', 'b', 'c'] будут иметь тип [a], а список [1, 'a'] будет другого типа. В этом случае в записи [a] символ a имеет значение типовой переменной.

Соглашения по именованию

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

Определители списков и математические последовательности

Пожалуй, Хаскел — единственный язык программирования, позволяющий просто и быстро конструировать списки, основанные на какой-нибудь простой математической формуле. Этот подход уже́ был использован при построении функции быстрой сортировки списка методом Хоара (см. пример 3 в лекции 1). Наиболее общий вид определителей списков выглядит так:

[ x | x <- xs ]

Это можно прочесть как «Список из всех таких x, взятых из xs». Структура «x <- xs» называется генератором. Генератор должен быть один и стоять первым в записи определителя списка. После него может стоять несколько выражений охраны, разделённых запятыми. При этом выбираются все такие x, значения всех выражений охраны на которых истинно. Запись

[ x | x <- xs, x > m, x < n ]

можно прочесть «Список из всех таких x, взятых из xs, что x больше m И x меньше n».

В Хаскеле можно формировать бесконечные списки и структуры данных. Бесконечные списки можно формировать на основе определителей списков или c помощью специальной нотации. Вот, например, бесконечный список, состоящий из последовательности натуральных чисел: [1, 2 ..]. Бесконечная последовательность нечётных натуральных чисел: [1, 3 ..].

При помощи двух точек можно также определять любую арифметическую прогрессию, конечную или бесконечную. Для конечной задаются первый и последний элементы. Разность арифметической прогрессии вычисляется на основе первого и второго заданного элементов — в приведённых выше примерах разность в первой прогресси равна 1, а во второй — 2. Чтобы определить список всех нечётных натуральных чисел вплоть до 10, надо записать: [1, 3 .. 10]. Результатом будет список [1, 3, 5, 7, 9].

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

Пример 11. Определение типа для представления двоичных деревьев

data Tree a = Leaf a

            | Branch (Tree a) (Tree a)

Branch :: Tree a -> Tree a -> Tree a

Leaf   :: a -> Tree a

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

ones          = 1 : ones

numbersFrom n = n : numbersFrom (n + 1)

squares       = map (^2) (numbersFrom 0)

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

Вызовы функций

Математическая нотация вызова функции традиционно полагала заключение параметров вызова в скобки. Эту традицию впоследствии переняли практически все императивные языки. В функциональных языках принята иная нотация: имя функции отделяется от её параметров просто пробелом. В Лиспе вызов функции length с неким параметром L записывается в виде списка: (length L). Такая нотация объясняется тем, что большинство функций в функциональных языках каррированны.

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

add     :: Integer -> Integer -> Integer

add x y = x + y

То её вызов с конкретными параметрами (например, 5 и 7) будет выглядеть как:

add 5 7

Здесь видно, что нотация Хаскела наиболее сильно приближена к нотации абстрактного математического языка. Однако он пошел ещё дальше Лиспа в этом вопросе, и в нём есть нотация для описания некаррированных функций, то есть тип которых нельзя представить в виде . И эта нотация, как и в императивных языках программирования, использует круглые скобки:

add (x, y) = x + y

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

inc :: Integer -> Integer

inc = add 1

То есть в этом случае вызов функции inc с одним параметром просто приведёт к вызову функции add с двумя, первый из которых — 1. Это интуитивное понимание понятия частичного применения. Для закрепления понимания можно рассмотреть классический пример: функция map (её определение на абстрактном функциональном языке приведено во второй лекции). Вот определение map на Хаскеле:

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

map f []     = []

map f (x:xs) = (f x) : (map f xs)

Как видно, здесь использована инфиксная запись операции prefix — двоеточие, только такая запись используется в нотации Хаскела для обозначения или конструирования пары. После приведённого выше определения можно произвести вызов

map (add 1) [1, 2, 3, 4]

который даст список [2, 3, 4, 5].

Использование λ-исчисления

Функциональная парадигма программирования основана на λ-исчислении, поэтому вполне закономерно, что все функциональные языки поддерживают нотацию для описания λ-абстракций. Хаскел не обошёл стороной этот аспект, если есть необходимость в определении какой-либо функции через λ-абстракцию. Ещё через λ-абстракции можно определять анонимные функции (например, для единичного вызова). Ниже показан пример определения функций add и inc именно при помощи λ-исчисления.

Пример 12. Функции add и inc, определённые через λ-абстракции

add = \x y -> x + y

inc = \x -> x + 1

Пример 13. Вызов анонимной функции

cubes = map (\x -> x * x * x) [0 ..]

Пример 13 показывает вызов анонимной функции, возводящей в куб переданный параметр. Результатом выполнения этой инструкции будет бесконечный список кубов целых чисел, начиная с нуля. Необходимо отметить, что в Хаскеле используется упрощённый способ записи λ-выражений; в точной нотации функцию add правильней было бы написать как:

add = \x -> \y -> x + y

Остаётся отметить, что тип λ-абстракции определяется точно так же, как и тип функций. Тип λ-выражения вида  будет выглядеть как , где  — это тип переменной , а  — тип выражения .

Инфиксный способ записи функций

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

Пример 14. Инфиксная операция конкатенации списков

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

[] ++ ys     = ys

(x:xs) ++ ys = x : (xs ++ ys)

Пример 15. Инфиксная операция композиции функций

(.) :: (b -> c) -> (a -> b) -> (a -> c)

f . g = \x -> f (g x)

Покуда инфиксные операции всё-таки являются функциями в смысле Хаскела, то есть они каррированы, то имеет смысл обеспечить возможность частичного применения таких функций. Для того имеется специальная запись, которая в Хаскеле называется «секция»:

(x ++) = \y -> (x ++ y)

(++ y) = \x -> (x ++ y)

(++)   = \x y -> (x ++ y)

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

Если функция принимает два параметра, то её также можно записывать в инфиксной форме. Однако если просто записать между параметрами имя функции, это будет ошибкой, ибо в строгой нотации Хаскела это будет просто двойным применением, причём в одном применении не будет хватать одного операнда. Чтобы записать функцию в инфиксной форме, её имя необходимо заключить в символы обратного апострофа — `.

Для вновь определённых инфиксных операций возможно определение порядка вычисления. Для этого в Хаскеле есть зарезервированное слово infixr, которое назначает операции приоритет выполения в интервале от 0 до 9: 9 объявляется самой сильной степенью значимости. 10 также входит в этот интервал, и именно эту степень имеет операция применения). Вот так определяются степени для определенных в примерах 14 и 15 операций:

infixr 5 ++

infixr 9 .

В Хаскеле все функции являются нестрогими, что значит: все они поддерживают отложенные вычисления. Если какая-то функция определена как bot = bot, то её вызов даст ошибку, и такие ошибки обычно сложно отслеживать. Но если есть некая константная функция, которая определена как constant_1 x = 1, то при вызове конструкции (constant_1 bot)никакой ошибки не произойдёт, так как значение функции bot в этом случае не вычислялось бы (вычисления отложенные, значение вычисляется только тогда, когда оно действительно требуется). Результатом вычисления, естественно, будет 1.