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

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

Одна из базовых единиц любого языка программирования — символ. Символом традиционно называется последовательность букв, цифр и специальных знаков ограниченной или неограниченной длины. В некоторых языках строчные и прописные буквы различаются, в некоторых нет. Так в Lisp’е различия между строчными и заглавными буквами нет, а в Haskell’е есть.

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

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

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

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

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

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

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

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

Эта запись может быть прочитана как «Список из всех таких x, взятых из xs». Структура «x  xs» называется генератором. После такого генератора (он должен быть один и стоять первым в записи определителя списка) может стоять некоторое число выражений охраны, разделённых запятыми. В этом случае выбираются все такие x, значения всех выражений охраны на которых истинно. Т.е. запись:

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

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

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

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

 

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

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

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

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

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

Здесь видно, что нотация Haskell’а наиболее сильно приближена к нотации абстрактного математического языка. Однако Haskell пошел еще дальше Lisp’а в этом вопросе, и в нем есть нотация для описания некаррированных функций, т.е. тип которых нельзя представить в виде A1  (A2  ... (An  B) ... ). И эта нотация, как и в императивных языках программирования, использует круглые скобки:

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

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

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

Результатом которого будет список [2, 3, 4, 5].

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

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

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

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

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

Остается отметить, что в Haskell’е все функции являются нестрогими, т.е. все они поддерживают отложенные вычисления. Например, если какая-то функция определена как:

При вызове такой функции произойдет ошибка, и обычно такие ошибки сложно отслеживать. Но если есть некая константная функция, которая определена как:

То при вызове конструкции (constant_1 bot) никакой ошибки не произойдёт, т.к. значение функции bot в этом случае не вычислялось бы (вычисления отложенные, значение вычисляется только тогда, когда оно действительно требуется). Результатом вычисления естественно будет число 1.