Основы функционального программирования/Основы языка Haskell

Лекции по функциональному программированию

1. Вводная лекция 2. Структуры данных и базисные операции 3. Структуры данных и базисные операции — 2 4. Основы языка Haskell 5. Служебные слова и синтаксис Haskell'а 6. Модули и монады в Haskell'е 7. Операции ввода/вывода в Haskell'е 8. Конструирование функций 9. Доказательство свойств функций 10. Формализация ФП на основе λ-исчисления 11. Трансформация программ

Настоящая лекция будет полностью посвящена синтаксису языка Haskell (далее, для удобства, «Хаскел»). Будут рассмотрены все важнейшие понятия языка, их соотношение с уже́ изученными понятиями (на основе абстрактного функционального языка). Также по возможности будут приводиться примеры на Лиспе, чтобы не отрываться от основ и традиции.

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

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

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

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

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

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

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 : numberFrom (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

Здесь видно, что нотация Хаскела наиболее сильно приближена к нотации абстрактного математического языка. Однако он пошел ещё дальше Лиспа в этом вопросе, и в нём есть нотация для описания некаррированных функций, т. е. тип которых нельзя представить в виде $A_{1} \rightarrow (A_{2} \rightarrow \ldots (A_{n} \rightarrow B) \ldots )$. И эта нотация, как и в императивных языках программирования, использует круглые скобки:

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

Остаётся отметить, что тип λ-абстракции определяется точно так же, как и тип функций. Тип λ-выражения вида $\lambda x.expr$ будет выглядеть как $T_{1} \rightarrow T_{2}$, где $T_{1}$ — это тип переменной $x$, а $T_{2}$ — тип выражения $expr$.

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

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

Пример 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 ++) = \x -> (x ++ y)
(++ y) = \y -> (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.

Упражнения

1. Сконструировать следующие конечные списки (N — количество элементов в конструируемом списке). Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
   • Список натуральных чисел. N = 20.
   • Список нечётных натуральных чисел. N = 20.
   • Список чётных натуральных чисел. N = 20.
   • Список степеней двойки. N = 25.
   • Список степеней тройки. N = 25.
   • Список треугольных чисел Ферма. N = 50.
   • Список пирамидальных чисел Ферма. N = 50.
2. Сконструировать следующие бесконечные списки. Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
   • Список факториалов.
   • Список квадратов натуральных чисел.
   • Список кубов натуральных чисел.
   • Список степеней пятёрки.
   • Список вторых суперстепеней натуральных чисел.

Ответы

1. Конечные списки конструируются либо при помощи ограничений, вставляемых в генератор списка, либо при помощи дополнительных ограничивающих параметров.
   • [1 .. 20]
   • [1, 3 .. 40] или [1, 3 .. 39]
   • [2, 4 .. 40]
   • Список степеней двойки проще всего сконструировать при помощи функции (здесь reverse — функция обращения списка):

powerTwo 0 = []
powerTwo n = (2 ^ n) : powerTwo (n – 1)
reverse (powerTwo 25)

1. • Список степеней тройки проще всего сконструировать при помощи функции (здесь reverse — функция обращения списка):

powerThree 0 = []
powerThree n = (3 ^ n) : powerThree (n – 1)
reverse (powerThree 25)

1. • В отличие от предыдущих двух упражнений, здесь можно воспользоваться функцией map, применяющей заданную функцию ко всем элементам списка:

t_Fermat 1 = 1
t_Fermat n = n + t_Fermat (n – 1)
map t_Fermat [1 .. 50]

1. • Конструирование списка из 50 пирамидальных чисел Ферма также основывается на использовании функции map:

p_Fermat 1 = 1
p_Fermat n = t_Fermat n + p_Fermat (n – 1)
map p_Fermat [1 .. 50]

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

numbersFrom n = n : numbersFrom (n + 1)

factorial n = f_a n 1

f_a 1 m = m
f_a n m = f_a (n – 1) (n * m)

map factorial (numbersFrom 1)

1. • Бесконечный список квадратов натуральных чисел:

square n = n * n

map square (numbersFrom 1)

1. • Бесконечный список кубов натуральных чисел:

cube n = n ^ 3

map cube (numbersFrom 1)

1. • Бесконечный список степеней пятёрки:

powerFive n = 5 ^ n

map powerFive (numbersFrom 1)

1. • Бесконечный список вторых суперстепеней натуральных чисел:

superPower n 0 = n
superPower n p = (superPower n (p – 1)) ^ n

secondSuperPower n = superPower n 2
map secondSuperPower (numbersFrom 1)