1. Нашёл ошибку?
2. Выдели её мышью.
3. Нажми Ctrl-Enter.

[ закрыть ]

Лекция 4. "Основы языка Haskell"

Понравились лекции? Используете их для обучения? Можете отблагодарить автора:

рублей Яндекс.Деньгами
на счет 4100137733052 (Лекции по Функциональному программированию)

Настоящая лекция будет полностью посвящена синтаксису языка 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

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

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

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

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

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

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

[ x | x <- xs ]

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

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

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

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

[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)

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

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

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

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

add	:: Integer -> Integer -> Integer
add x y	= x + y

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

add 5 7

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

add (x, y)	= x + y

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

inc	:: Integer -> Integer
inc	= add 1

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

map		:: (a -> b) -> [a] -> [b]
map f []		= []
map f (x:xs)	= (f x) : (map f xs)

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

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

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

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

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

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

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

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

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

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

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

Остаётся отметить, что тип l-абстракции определяется абсолютно так же, как и тип функций. Тип l-выражения вида lx.expr будет выглядеть как T1 -> T2, где T1 — это тип переменной x, а T2 — тип выражения 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)

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

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

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

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

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

infixr 5 ++
infixr 9 .

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

bot	= bot

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

constant_1 x	= 1

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

Упражнения

1. Сконструировать следующие конечные списки (N — количество элементов в конструируемом списке). Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.

a. Список натуральных чисел. N = 20.

b. Список нечётных натуральных чисел. N = 20.

c. Список чётных натуральных чисел. N = 20.

d. Список степеней двойки. N = 25.

e. Список степеней тройки. N = 25.

f. Список треугольных чисел Ферма. N = 50.

g. Список пирамидальных чисел Ферма. N = 50.

2. Сконструировать следующие бесконечные списки. Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.

a. Список факториалов.

b. Список квадратов натуральных чисел.

c. Список кубов натуральных чисел.

d. Список степеней пятёрки.

e. Список вторых суперстепеней натуральных чисел.

Ответы для самопроверки

1. Конечные списки конструируются либо при помощи ограничений, вставляемых в генератор списка, либо при помощи дополнительных ограничивающих параметров.

a. [1 .. 20]

b. [1, 3 .. 40] или [1, 3 .. 39]

c. [2, 4 .. 40]

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

powerTwo 0 = []
powerTwo n = (2 ^ n) : powerTwo (n - 1)

reverse (powerTwo 25)

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

powerThree 0 = []
powerThree n = (2 ^ n) : powerThree (n - 1)

reverse (powerThree 25)

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

t_Fermat 1 = 1
t_Fermat n = n + t_Fermat (n - 1)

map t_Fermat [1 .. 50]

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

p_Fermat 1 = 1
p_Fermat n = t_Fermat n + p_Fermat (n - 1)

map p_Fermat [1 .. 50]

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

a. Бесконечный список факториалов:

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)

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

square n = n * n

map square (numbersFrom 1)

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

cube n = n ^ 3

map cube (numbersFrom 1)

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

powerFive n = 5 ^ n

map powerFive (numbersFrom 1)

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

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

secondSuperPower n = superPower n 2

map secondSuperPower (numbersFrom 1)

Наверх | Содержание | Лекции | НАУКА ·]

Сайт управляется системой uCoz