Основы функционального программирования/Основы языка Haskell
Основы функционального программирования
- Вводная лекция
- Структуры данных и базисные операции:
Настоящая лекция будет полностью посвящена синтаксису языка Haskell (далее, для удобства, «Хаскел»). Будут рассмотрены все важнейшие понятия языка, их соотношение с уже́ изученными понятиями (на основе абстрактного функционального языка). Также по возможности будут приводиться примеры на Лиспе, чтобы не отрываться от основ и традиции.
Структуры данных и их типы
[править]Одна из основных единиц любого языка программирования — это символ. Символом традиционно называется последовательность букв, цифр и специальных знаков ограниченной или неограниченной длины. В некоторых языках строчные и прописные буквы различаются (к ним относится Хаскел), в некоторых нет (Лисп).
Символы чаще всего являются идентификаторами — именами констант, переменных, функций. Значениями же констант, переменных и функций являются типизированные последовательности знаков. Пример: значением числовой константы не может быть строка из букв. В функциональных языках есть понятие атом. В реализациях атомами называются символы и чи́сла, причём чи́сла могут быть трёх видов: целые, с фиксированной и с плавающей точкой.
Список — ещё одно понятие функционального программирования. В абстрактной математической записи использовались квадратные скобки []
, которые также используются в Хаскеле. Но в Лиспе используются обычные, круглые скобки ()
. Элементы списка в Лиспе разделяются пробелами, что не очень наглядно, поэтому в Хаскеле ввели запятую для разделения. Список [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
.
Упражнения
[править]- Сконструировать следующие конечные списки (N — количество элементов в конструируемом списке). Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
- Список натуральных чисел. N = 20.
- Список нечётных натуральных чисел. N = 20.
- Список чётных натуральных чисел. N = 20.
- Список степеней двойки. N = 25.
- Список степеней тройки. N = 25.
- Список треугольных чисел Ферма. N = 50.
- Список пирамидальных чисел Ферма. N = 50.
- Сконструировать следующие бесконечные списки. Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
- Список факториалов.
- Список квадратов натуральных чисел.
- Список кубов натуральных чисел.
- Список степеней пятёрки.
- Список вторых суперстепеней натуральных чисел.
Ответы
[править]- Конечные списки конструируются либо при помощи ограничений, вставляемых в генератор списка, либо при помощи дополнительных ограничивающих параметров.
[1 .. 20]
[1, 3 .. 40]
или[1, 3 .. 39]
[2, 4 .. 40]
- Список степеней двойки проще всего сконструировать при помощи функции (здесь
reverse
— функция обращения списка):
powerTwo 0 = []
powerTwo n = (2 ^ n) : powerTwo (n – 1)
reverse (powerTwo 25)
- Список степеней тройки проще всего сконструировать при помощи функции (здесь
reverse
— функция обращения списка):
- Список степеней тройки проще всего сконструировать при помощи функции (здесь
powerThree 0 = []
powerThree n = (3 ^ n) : powerThree (n – 1)
reverse (powerThree 25)
- В отличие от предыдущих двух упражнений, здесь можно воспользоваться функцией
map
, применяющей заданную функцию ко всем элементам списка:
- В отличие от предыдущих двух упражнений, здесь можно воспользоваться функцией
t_Fermat 1 = 1
t_Fermat n = n + t_Fermat (n – 1)
map t_Fermat [1 .. 50]
- Конструирование списка из 50 пирамидальных чисел Ферма также основывается на использовании функции
map
:
- Конструирование списка из 50 пирамидальных чисел Ферма также основывается на использовании функции
p_Fermat 1 = 1
p_Fermat n = t_Fermat n + p_Fermat (n – 1)
map p_Fermat [1 .. 50]
- Бесконечные списки конструируются либо при помощи неограниченных генераторов, либо при помощи конструирующих функций без ограничивающих параметров.
- Бесконечный список факториалов:
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)
- Бесконечный список квадратов натуральных чисел:
square n = n * n
map square (numbersFrom 1)
- Бесконечный список кубов натуральных чисел:
cube n = n ^ 3
map cube (numbersFrom 1)
- Бесконечный список степеней пятёрки:
powerFive n = 5 ^ n
map powerFive (numbersFrom 1)
- Бесконечный список вторых суперстепеней натуральных чисел:
superPower n 0 = n
superPower n p = (superPower n (p – 1)) ^ n
secondSuperPower n = superPower n 2
map secondSuperPower (numbersFrom 1)