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

Содержимое удалено Содержимое добавлено
Пока лишь копия текста из MS Word - необходима стилизация
 
Первоначальная викификация
Строка 1:
= Лекция 5. «Служебные слова и синтаксис Haskell’а» =
 
Уже неоднократно подчёркивалось, что синтаксис языка Haskell чрезвычайно похож на синтаксис абстрактного функционального языка. При разработке Haskell’а создатели попытались собрать всё лучшее из имеющихся к этому времени функциональных языков, а также отринуть всё самое плохое. В принципе, это получилось...
 
Ниже рассматриваются оставшиеся служебные слова, которые ещё не были рассмотрены в предыдущей лекции. Кроме того, по возможности будут показаны различные нововведения в парадигму функционального программирования, которые были реализованы в Haskell’е.
 
Охрана и локальные переменные
== Охрана и локальные переменные ==
 
Как было показано в третьей лекции, охрана и локальные переменные используются в функциональном программировании исключительно для простоты записи и понимания текстов программ. Haskell не обошёл своим вниманием и этот аспект, в его синтаксисе имеются специальные средства, которые позволяют организовывать охрану и использовать локальные переменные.
Если возникла необходимость определить какую-либо функцию с использованием механизма охраны, то для этой цели необходимо использовать символ вертикальной черты « | » :
 
sign x | x > 0 = 1
sign x | x ==> 0 = 01
| x <== 0 = -10
| x < 0 = -1
 
Функция sign в предыдущем примере использует три охраняющие конструкции, каждая из которых отделена вертикальной чертой от предыдущего определения. В принципе, таких охраняющих конструкций может быть неограниченное количество. Их разбор идёт, естественно, сверху вниз, и если существует непустое пересечение в определении охраны, то сработает та конструкция, которая находится раньше (выше) в записи определения функции.
 
Для того, чтобы облегчить написание программ, сделать их более читабельными и простыми для понимания в том случае, когда в каком-либо определении функции записано большое количество клозов, в Haskell’е существует ключевое слово «case». При помощи этого слова можно не записывать клозы определения функций так, как это принято в «чистом» функциональном программировании, а несколько сократить запись. Вот общий вид определения функций с ключевым словом «case»:
 
Function X1 X2 ... Xk = case (X1, X2, ..., Xk) of
Function X1 X2 ... Xk = case (X1, X2, ..., Xk) of
(P11, P21, ..., Pk1)  Expression1
(P11, P21, ..., Pk1)  Expression1
...
...
(P1n, P2n, ..., Pkn)  Expressionn
(P1n, P2n, ..., Pkn)  Expressionn
 
В приведенном выше описании жирным шрифтом выделены служебные слова и символы языка.
 
Так функция, которая возвращает список из первых n элементов заданного списка, может быть определена следующим образом при помощи служебного слова «case»:
 
takeFirst n l = case (n, l) of
takeFirst n l = case (n, l) of (0, _) -> []
(_, []) -> []
(n, (x:xs)) -> (x) : (takeFirst (n – 1) xs)
 
И такая запись будет полностью эквивалентна обычному определению функции:
 
takeFirst 0 _ = []
takeFirst _0 []_ = []
takeFirst _ [] = []
takeFirst n (x:xs) = (x) : (takeFirst (n – 1) xs)
 
Пришло время объяснить понятие маски подстановки. В Haskell’е маску обозначают символом нижней черты « _ » (абсолютно также, как и в Prolog’е). Этот символ заменяет любой образец и является своего рода анонимной переменной. Если в выражении клоза нет необходимости использования переменной образца, то её можно заменить маской подстановки. При этом, естественно, происходят отложенные вычисления — то выражение, которое может быть подставлено вместо маски, не вычисляется.
 
Другим способом использования охраняющих конструкций является использование конструкции «if-then-else». В Haskell’е реализована и эта возможность. Формально, эта конструкция может быть лекго трансформирована в выражение с использованием служебного слова «case». Можно даже считать, что выражение:
 
if Exp1 then Exp2 else Exp3
if Exp1 then Exp2 else Exp3
 
Является сокращением выражения:
 
case (Exp1) of
case (Exp1) of (True) -> Exp2
(False) -> Exp3
 
Естественно, что тип Exp1 должен быть Boolean (Bool в Haskell’е), а типы выражений Exp2 и Exp3 совпадать (ведь именно значения этих выражений будет возвращено определяемой через конструкцию «if-then-else» функцией).
 
Для использования локальных переменных (в смысле функциональной парадигмы программирования) в Haskell’е существует два типа записи. Первый тип полностью соответствует математической нотации, введенной в третьей лекции:
 
let y = a * b
flet xy = (xa +* y) / yb
in f cx = (x + fy) / dy
in f c + f d
 
Другим способом определения локальной переменной является её описание после использования. В этом случае используется служебное слово «where», которое ставится в конце выражения:
 
f x y | y > z = y – z
f x y | y ==> z = 0y – z
| y < z == z = y0
where | y < z = xz * xy
where z = x * x
 
Таким образом видно, что Haskell поддерживает два способа записи определения локальных переменных — префиксный (при помощи служебного слова «let») и постфиксный (при помощи служебного слова «where»). Оба способа являются равнозначными, их употребление зависит только от наклонностей программиста. Однако обычно постфиксный способ записи используется в выражениях, где также есть охрана, в то время как префиксный способ записи используется в остальных случаях.
 
Полиморфизм
== Полиморфизм ==
 
В первой лекции уже было показано, что функциональная парадигма программирования поддерживает чистый или параметрический полиморфизм. Однако большинство современных языков программирования не обходятся без так называемого полиморфизма ad hoc, или перегрузки. Например, перегрузка практически повсеместно используется для следующих целей:
 
• Литералы 1, 2, 3 и т.д. (т.е. цифры) используются как для записи целых чисел, так и для записи чисел произвольной точности.
*Литералы 1, 2, 3 и т.д. (т.е. цифры) используются как для записи целых чисел, так и для записи чисел произвольной точности.
*Арифметические операции (например, сложение — знак « + ») используются для работы с данными различных типов (в том числе и с нечисловыми данными, например — конкатенация для строк).
*Оператор сравнения (в Haskell’е знак двойного равенства — « == ») используется для сравнения данных различных типов.
 
Перегруженное поведение операций различное для каждого типа данных (зачастую такое поведение вообще может быть неопределено или определено ошибочно), в то время, как в параметрическом полиморфизме тип данных, вообще говоря, не важен. Однако в Haskell’е есть механизм для использования перегрузки.
 
Рассмотреть возможность использования полиморфизма ad hoc проще всего на примере операции сравнения. Существует большое множество типов, для которых можно и целесообразно переопределить операцию сравнения, но для некоторых типов эта операция бесполезна. Например, сравнение функций бессмысленно, функции необходимо вычислять и сравнивать результаты этих вычислений. Однако, например, может возникнуть необходимость сравнивать списки. Конечно, здесь речь идет о сравнении значений, а не сравнении указателей (как, например, это сделано в Java).
 
Рассмотрим функцию element, которая возвращает значение истины в зависимости от того, присутствует заданный элемент в заданном списке, или нет (в целях стиля данная функция описана в инфиксной форме):
 
x `element` [] = False
x `element` [] = False
x `element` (y:ys) = (x == y) || (x `element` ys)
 
Здесь видно, что у функции element тип (a  [a]  Bool), но при этом тип операции « == » должен быть (a  a  Bool). Т.к. переменная типа a может обозначать любой тип (в том числе и список), целесообразно переопределить операцию « == » для работы с любым типом данных.
 
Классы типов являются решением этой проблемы в Haskell’е. Для того, чтобы рассмотреть этот механизм в действии далее определяется класс типов, содержащий оператор равенства.
 
class Eq a where
(==) ::class a ->Eq a -> Boolwhere
(==) :: a -> a -> Bool
 
В этой конструкции использованы служебные слова «class» и «where», а также переменная типов a. Символ «Eq» является именем определяемого класса. Эта запись может быть прочитана следующим образом: «Тип a является экземпляром класса Eq, если для этого типа перегружена операция сравнения « == » соответствующего типа». Необходимо отметить, что операция сравнения должна быть определена на паре объектов одного и того же типа.
 
Ограничение того факта, что тип a должен быть экземпляром класса Eq записывается как (Eq a). Поэтому выражение (Eq a) не является описанием типа, но оно описывает ограничение, накладываемое на тип a, и это ограничение в Haskell’е называется контекстом. Контексты располагаются перед определением типов и отделяются от них символами « => »:
 
(==) :: (Eq a) => a -> a -> Bool
(==) :: (Eq a) => a -> a -> Bool
 
Эта запись может быть прочитана как «Для каждого типа a, который является экземпляром класса Eq, определена операция « == », которая имеет тип (a  a  Bool)». Эта операция должна быть использована в функции element, поэтому ограничение распространяется и на неё. В этом случае необходимо явно указывать тип функции:
 
element :: (Eq a) => a -> [a] -> Bool
element :: (Eq a) => a -> [a] -> Bool
 
Этой записью декларируется тот необходимый факт, что функция element определена не для всех типов данных, но только для тех, для которых определена соответствующая операция сравнения.
 
Однако теперь возникает проблема определения того, какие типы являются экземплярами класса Eq. Для этого в Haskell’е есть служебное слово «instance». Например, для того, чтобы предписать, что тип Integer является экземпляром класса Eq, необходимо написать:
 
instance Eq Integer where
instance Eq Integer where
x == y = x `integerEq` y
x == y = x `integerEq` y
 
В этом выражении определение операции « == » называется определением метода (как в объектно-ориентированной парадигме). Функция integerEq может быть любой (и не обязательно инфиксной), главное, чтобы у нее был тип (a  a  Bool). В этом случае скорее всего подойдет примитивная функция сравнения двух натуральных чисел. В свою очередь прочитать написанное выражение можно следующим образом: «Тип Integer является экземпляром класса Eq, и далее приводится определение метода, который производит сравнение двух объектов типа Integer».
 
Таким же образом можно определить операцию сравнения и для бесконечных рекурсивных типов. Например, для типа Tree (см. лекцию 4) определение будет выглядеть следующим образом:
 
instance (Eq a) => Eq (Tree a) where
Leafinstance (Eq a) ==> LeafEq b =(Tree a) == bwhere
(Branch l1 r1) Leaf a == (BranchLeaf l2b r2) = (l1 == l2) && (r1 = a == r2)b
(Branch l1 r1) == (Branch l2 r2) = (l1 == l2) && (r1 == r2)
_ == _ = False
_ == _ = False
 
Естественно, что если в языке определено понятие класса, должно быть определена и концепция наследования. Хотя в Haskell’е под классом понимается нечто более абстрактное, чем в обычных объектно-ориентированных языках, в Haskell’е также есть и наследование. Но в то же время концепция наследования определяется столь же изощренно, что и понятие класса. Например, от определённого выше класса Eq можно унаследовать класс Ord, который будет представлять сравнимые типы данных. Его определение будет выглядеть следующим образом:
 
class (Eq a) => Ord a where
class (<),Eq (>a), (<=), (>=) :: a ->Ord a -> Boolwhere
min (<), max (>), (<=), (>=) :: a -> a -> aBool
min, max :: a -> a -> a
 
Все экземпляры класса Ord должны определять кроме операций «меньше», «больше», «меньше или равно», «больше или равно», «минимум» и «максимум» ещё и операцию сравнения « == », т.к. её класс Ord наследует от класса Eq.
 
Самое удивительно заключается в том, что Haskell поддерживает множественное наследование. В случае использования нескольких базовых классов, всех их просто надо перечислить через запятую в соответствующей секции. При этом экземпляры классов, унаследованных от нескольких базовых классов, должны, естественно, поддерживать и все методы базовых классов.
Сравнение с другими языками
Хотя классы существуют во многих других языках программирования, понятие класса в Haskell’е несколько отличается.
• Haskell разделяет определения классов и их методов, в то время как такие языки, как C++ и Java вместе определяют структуру данных и методы для её обработки.
• Определения методов в Haskell’е соответствуют виртуальным функциям C++. Каждый конкретный экземпляр класса должен переопределять методы класса.
• Больше всего классы в Haskell’е похожи на интерфейсы Java. Как и определение интерфейса, классы в Haskell’е предоставляют протокол использования объекта, вместо определения самих объектов.
• Haskell не поддерживает стиль перегрузки функции, используемый в C++, когда функции с одним и тем же именем получают данные различных типов для обработки.
• Типы объектов в Haskell’е не могут быть выведены неявно. В Haskell’е не существует базового класса для всех классов (как, например, TObject в Object Pascal’е).
• C++ и Java добавляют в скомпилированный код идентифицирующую информацию (например, таблицы размещения виртуальных функций). В Haskell’е такого нет. Во время интерпретации (компиляции) вся необходимая информация выводится логически.
• Не существует понятия контроля за доступом — нет публичных и защищенных методов. Вместо этого Haskell предоставляет механизм модуляризации программ.
Упражнения
1. В нотации Haskell’а записать функции, работающие со списками (из упражнений лекции 2). По возможности воспользоваться формализмами охраны и локальными переменными.
a. getN — функция вычленения N-ого элемента из заданного списка.
b. listSumm — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
c. oddEven — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
d. reverse — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
e. map — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
2. В нотации Haskell’а записать более сложные функции, работающие со списками (из упражнений лекции 3). При необходимости воспользоваться дополнительными функциями и определёнными в предыдущем упражнении. По возможности воспользоваться формализмами охраны и локальными переменными.
a. reverseAll — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.
b. position — функция, возвращающая номер первого вхождения заданного атома в список.
c. set — функция, возвращающая список, содержащий единичные вхождения атомов заданного списка.
d. frequency — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.
3. Описать следующие классы типов. При необходимости воспользоваться механизмом наследования классов.
a. Show — класс, объекты экземпляров которого могут быть выведены на экран.
b. Number — класс, описывающий числа различной природы.
c. String — класс, описывающий строки (списки символов).
4. Определить типы-экземпляры классов, описанных в предыдущем задании. По возможности для каждого экземпляра класса определить методы, работающие с объектами этого класса.
a. Integer — тип целых чисел.
b. Real — тип действительных чисел.
c. Complex — тип комплексных чисел.
d. WideString — тип строк, в виде последовательности двухбайтовых символов в кодировке UNICODE.
Ответы для самопроверки
1. Все нижеприведённые описания на Haskell’е являются лишь одними из большого ряда возможных:
a. getN:
getN :: [a] -> a
getN n [] = _
getN 1 (h:t) = h
getN n (h:t) = getN (n – 1) t
b. listSumm:
listSumm :: Ord (a) => [a] -> [a]
listSumm [] l = l
listSumm l [] = l
listSumm (h1:t1) (h2:t2) = (h1 + h2) : (listSumm t1 t2)
c. oddEven:
oddEven :: [a] -> [a]
oddEven [] = []
oddEven [x] = [x]
oddEven (h1:(h2:t)) = (h2:h1) : (oddEven t)
d. reverse:
append :: [a] -> [a] -> [a]
append [] l = l
append (h:t) l2 = h : (append t l2)
 
== Сравнение с другими языками ==
reverse :: [a] -> [a]
reverse [] = []
reverse (h:t) = append (reverse t [h])
e. map:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (h:t) = (f h) : (map f t)
2. Все нижеприведённые описания на Haskell’е являются лишь одними из большого ряда возможных:
a. reverseAll:
atom :: ListStr (a) -> Bool
atom a = True
atom _ = False
 
Хотя классы существуют во многих других языках программирования, понятие класса в Haskell’е несколько отличается.
reverseAll :: ListStr (a) -> ListStr (a)
reverseAll l = l
reverseAll [] = []
reverseAll (h:t) = append (reverseAll t) (reverseAll h)
b. position:
position :: a -> [a] -> Integer
position a l = positionN a l 0
 
*Haskell разделяет определения классов и их методов, в то время как такие языки, как C++ и Java вместе определяют структуру данных и методы для её обработки.
positionN :: a -> [a] -> Integer -> Integer
*Определения методов в Haskell’е соответствуют виртуальным функциям C++. Каждый конкретный экземпляр класса должен переопределять методы класса.
positionN a (a:t) n = (n + 1)
*Больше всего классы в Haskell’е похожи на интерфейсы Java. Как и определение интерфейса, классы в Haskell’е предоставляют протокол использования объекта, вместо определения самих объектов.
positionN a (h:t) n = positionN a t (n + 1)
*Haskell не поддерживает стиль перегрузки функции, используемый в C++, когда функции с одним и тем же именем получают данные различных типов для обработки.
positionN a [] n = 0
*Типы объектов в Haskell’е не могут быть выведены неявно. В Haskell’е не существует базового класса для всех классов (как, например, TObject в Object Pascal’е).
c. set:
*C++ и Java добавляют в скомпилированный код идентифицирующую информацию (например, таблицы размещения виртуальных функций). В Haskell’е такого нет. Во время интерпретации (компиляции) вся необходимая информация выводится логически.
set :: [a] -> [a]
*Не существует понятия контроля за доступом — нет публичных и защищенных методов. Вместо этого Haskell предоставляет механизм модуляризации программ.
set [] = []
set (h:t) = include h (set t)
 
== Упражнения ==
include :: a -> [a] -> [a]
include a [] = [a]
include a (a:t) = a : t
include a (b:t) = b : (include a t)
d. frequency:
frequency :: [a] -> [(a : Integer)]
frequency l = f [] l
 
#В нотации Haskell’а записать функции, работающие со списками (из упражнений лекции 2). По возможности воспользоваться формализмами охраны и локальными переменными.
f :: [a] -> [a] -> [(a : Integer)]
#*getN — функция вычленения N-ого элемента из заданного списка.
f l [] = l
#*listSumm — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
f l (h:t) = f (corrector h l) t
#*oddEven — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
#*reverse — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
#*map — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
#В нотации Haskell’а записать более сложные функции, работающие со списками (из упражнений лекции 3). При необходимости воспользоваться дополнительными функциями и определёнными в предыдущем упражнении. По возможности воспользоваться формализмами охраны и локальными переменными.
#*reverseAll — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.
#*position — функция, возвращающая номер первого вхождения заданного атома в список.
#*set — функция, возвращающая список, содержащий единичные вхождения атомов заданного списка.
#*frequency — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.
#Описать следующие классы типов. При необходимости воспользоваться механизмом наследования классов.
#*Show — класс, объекты экземпляров которого могут быть выведены на экран.
#*Number — класс, описывающий числа различной природы.
#*String — класс, описывающий строки (списки символов).
#Определить типы-экземпляры классов, описанных в предыдущем задании. По возможности для каждого экземпляра класса определить методы, работающие с объектами этого класса.
#*Integer — тип целых чисел.
#*Real — тип действительных чисел.
#*Complex — тип комплексных чисел.
#*WideString — тип строк, в виде последовательности двухбайтовых символов в кодировке UNICODE.
 
== Ответы для самопроверки ==
corrector :: a -> [a] -> [(a : Integer)]
 
corrector a [] = [(a : 1)]
#Все нижеприведённые описания на Haskell’е являются лишь одними из большого ряда возможных:
corrector a (a:n):t = (a : (n + 1)) : t
#*getN:
corrector a h:t = h : (corrector a t)
getN :: [a] -> a
3. Все нижеприведённые описания на Haskell’е являются лишь одними из большого ряда возможных:
getN n [] = _
a. Show:
getN 1 (h:t) = h
class Show a where
getN n (h:t) = getN (n – 1) t
#*listSumm:
listSumm :: Ord (a) => [a] -> [a]
listSumm [] l = l
listSumm l [] = l
listSumm (h1:t1) (h2:t2) = (h1 + h2) : (listSumm t1 t2)
#*oddEven:
oddEven :: [a] -> [a]
oddEven [] = []
oddEven [x] = [x]
oddEven (h1:(h2:t)) = (h2:h1) : (oddEven t)
#*reverse:
append :: [a] -> [a] -> [a]
append [] l = l
append (h:t) l2 = h : (append t l2)
reverse :: [a] -> [a]
reverse [] = []
reverse (h:t) = append (reverse t [h])
#*map:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (h:t) = (f h) : (map f t)
#Все нижеприведённые описания на Haskell’е являются лишь одними из большого ряда возможных:
#*reverseAll:
atom :: ListStr (a) -> Bool
atom a = True
atom _ = False
reverseAll :: ListStr (a) -> ListStr (a)
reverseAll l = l
reverseAll [] = []
reverseAll (h:t) = append (reverseAll t) (reverseAll h)
#*position:
position :: a -> [a] -> Integer
position a l = positionN a l 0
positionN :: a -> [a] -> Integer -> Integer
positionN a (a:t) n = (n + 1)
positionN a (h:t) n = positionN a t (n + 1)
positionN a [] n = 0
#*set:
set :: [a] -> [a]
set [] = []
set (h:t) = include h (set t)
include :: a -> [a] -> [a]
include a [] = [a]
include a (a:t) = a : t
include a (b:t) = b : (include a t)
#*frequency:
frequency :: [a] -> [(a : Integer)]
frequency l = f [] l
f :: [a] -> [a] -> [(a : Integer)]
f l [] = l
f l (h:t) = f (corrector h l) t
corrector :: a -> [a] -> [(a : Integer)]
corrector a [] = [(a : 1)]
corrector a (a:n):t = (a : (n + 1)) : t
corrector a h:t = h : (corrector a t)
#Все нижеприведённые описания на Haskell’е являются лишь одними из большого ряда возможных:
#*Show:
class Show a where
show :: a -> a
b. #*Number:
class Number a where
(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
(/) :: a -> a -> a
c. #*String:
class String a where
(++) :: a -> a -> a
length :: a -> Integer
4. #Все нижеприведённые описания на Haskell’е являются лишь одними из большого ряда возможных:
a. #*Integer:
instance Number Integer where
x + y = plusInteger x y
x – y = minusInteger x y
x * y = multInteger x y
x / y = divInteger x y
 
plusInteger :: Integer -> Integer -> Integer
plusInteger x y = x + y
 
...
b. #*Real:
instance Number Real where
x + y = plusReal x y
...
c. #*Complex:
instance Number Complex where
x + y = plusComplex x y
...
d. #*WideString:
instance String WideString where
x ++ y = wideConcat x y
length x = wideLength x
 
wideConcat x y = append x y
wideLength x = length x