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

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

• Вводная лекция
  
• Структуры данных и базисные операции:
  • Первая часть
    
  • Вторая часть
    

• Основы языка Haskell
  
  • Служебные слова и синтаксис
    
  • Модули и монады
    
  • Ввод-вывод
    
  • Другие статьи и учебники по Haskell →

• Конструирование функций
  
• Доказательство свойств функций
  
• Формализация функционального программирования на основе λ-исчисления
  
• Трансформация программ

• Категория «Функциональное программирование» →

Синтаксис Хаскела очень похож на синтаксис абстрактного функционального языка. При разработке Хаскела создатели попытались собрать всё лучшее из имеющихся к этому времени функциональных языков и отринуть всё худшее. Кажется, получилось…

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

Охрана и локальные переменные

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

sign x | x > 0  = 1
       | x == 0 = 0
       | x < 0  = -1

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

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

Function X1 X2 … Xk = case (X1, X2, …, Xk) of
(P11, P21, …, Pk1) -> Expression1
…
(P1n, P2n, …, Pkn) -> Expressionn

Здесь жирным выделены служебные слова́ и символы языка.

Так функция, возвращающая список из первых $n$ элементов заданного списка, может быть определена при помощи case:

takeFirst n l = case (n, l) of
  (0, _)      -> []
  (_, [])     -> []
  (n, (x:xs)) -> (x) : (takeFirst (n - 1) xs)

И такая запись будет полностью эквивалентна обычному определению функции:

takeFirst 0 _      = []
takeFirst _ []     = []
takeFirst n (x:xs) = (x) : (takeFirst (n – 1) xs)

Пришло время объяснить понятие маски подстановки. В Хаскеле маску обозначают символом нижней черты _ (так же, как в Прологе). Этот символ заменяет любой образец и является своего рода безымянной переменной. Если в выражении клоза нет необходимости использования переменной образца, то её можно заменить маской подстановки. При этом, естественно, происходят отложенные вычисления: то выражение, которое может быть подставлено вместо маски, не вычисляется.

Другой способ использования охраняющих конструкций — применение конструкции if-then-else, которая в Хаскеле тоже поддерживается. Формально, её легко можно превратить в выражение с case. Можно даже считать, что выражение

if Exp1 then Exp2 else Exp3

есть сокращение для

case (Exp1) of
  (True)  -> Exp2
  (False) -> Exp3

Естественно, что тип Exp1 должен быть булевым (Bool), а типы выражений Exp2 и Exp3 — совпадать (ведь именно значения этих выражений будет возвращено определяемой через конструкцию if-then-else функцией).

Для использования локальных переменных (в смысле функциональной парадигмы программирования) в Хаскеле есть два вида записи. Первый полностью подобен математической нотации, введённой в третьей лекции:

let y   = a * b
  f x = (x + y) / y
in f c + f d

Другой способ — описание локальной переменной после использования. При этом используется служебное слово where, которое ставится в конце выражения:

f x y | y > z  = y – z
      | y == z = 0
      | y < z  = z – y
      where z = x * x

Видно, что язык поддерживает два способа записи определения локальных переменных: префиксный (со словом let) и постфиксный (со словом where). Они равнозначны, их употребление зависит только от предпочтений программиста. Однако обычно постфиксный способ используется в выражениях, где также есть охрана, а префиксный — в остальных случаях.

Полиморфизм

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

• Литералы 1, 2, 3 и так далее (то есть цифры) используются для записи и целых чисел, и чисел произвольной точности.
• Арифметические операции (например, сложение: +) используются для работы с данными различных типов (в том числе нечисловыми, например конкатенация для строк).
• Оператор сравнения (==) используется для сравнения данных различных типов.

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

Рассмотреть возможность использования полиморфизма «ad hoc» проще всего на примере операции сравнения. Есть много типов, для которых можно и целесообразно переопределить операцию сравнения, но для некоторых типов эта операция бесполезна. Например, сравнение функций бессмысленно; функции необходимо вычислять и сравнивать результаты этих вычислений. Но может возникнуть необходимость сравнивать списки. Конечно, здесь речь идет о сравнении значений, а не сравнении указателей (как, например, это сделано в языке Java).

Рассмотрим функцию element, которая возвращает значение истины присутствия данного элемента в списке (для красоты эта функция описана в инфиксной форме):

x `element` []     = False
x `element` (y:ys) = (x == y) || (x `element` ys)

Здесь видно, что у функции element тип (a -> [a] -> Bool), но при этом тип операции == должен быть (a -> a -> Bool). Раз переменная типа a может обозначать любой тип (в том числе и список), целесообразно переопределить операцию == для работы с любым типом данных.

Классы типов решают эту проблему в Хаскеле. Чтобы рассмотреть этот механизм в действии, далее определяется класс типов, содержащий оператор равенства.

class Eq a where
  (==) :: a -> a -> Bool

В этой конструкции использованы служебные слова class и where, а также переменная типов a. Символ Eq является именем определяемого класса. Эта запись может быть прочитана как: «Тип a является экземпляром класса Eq если для этого типа перегружена операция сравнения == соответствующего типа». Операция сравнения должна быть определена на паре объектов одного и того же типа.

Ограничение того факта, что тип a должен быть экземпляром класса Eq записывается как (Eq a). Поэтому выражение (Eq a) не является описанием типа, но описывает ограничение, накладываемое на тип a, и это ограничение называется контекстом. Контексты располагаются перед определением типов и отделяются от них символами =>:

(==) :: (Eq a) => a -> a -> Bool

Это читается как: «Для каждого типа a, являющегося экземпляром класса Eq, определена операция ==, которая имеет тип (a -> a -> Bool)». Эта операция должна быть использована в функции element, поэтому ограничение распространяется и на неё. В этом случае необходимо явно указывать тип функции:

element :: (Eq a) => a -> [a] -> Bool

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

Теперь возникает проблема определения того, какие типы являются экземплярами класса Eq. Для этого есть служебное слово instance. Например, чтобы предписать, что тип Integer является экземпляром Eq, надо написать:

instance Eq Integer where
  x == y = x `integerEq` y

В этом выражении определение операции == называется определением метода, как в объектно-ориентированной парадигме. Функция integerEq может быть любой (и не обязательно инфиксной), лишь бы у неё был тип (a -> a -> Bool). В этом случае скорее всего подойдет примитивная функция сравнения двух натуральных чисел. Прочитать написанное выражение можно следующим образом: «Тип Integer является экземпляром класса Eq, и далее приводится определение метода, который производит сравнение двух объектов типа Integer».

Таким же образом можно определить операцию сравнения и для бесконечных рекурсивных типов. Например, для типа Tree (см. лекцию 4) определение будет выглядеть так:

instance (Eq a) => Eq (Tree a) where
  Leaf a == Leaf b                 = a == b
  (Branch l1 r1) == (Branch l2 r2) = (l1 == l2) && (r1 == r2)
  _ == _                           = False

Естественно, что если в языке определено понятие класса, должно быть определена и концепция наследования. Хотя в Хаскеле под классом понимается нечто более абстрактное, чем в обычных объектно-ориентированных языках, в нём также есть и наследование. В то же время понятие наследования определяется столь же изощрённо, что и понятие класса. Например, от определённого выше класса Eq можно унаследовать класс Ord, который будет представлять сравнимые типы данных. Его определение будет таким:

class (Eq a) => Ord a where
  (<), (>), (<=), (>=) :: a -> a -> Bool
  min, max             :: a -> a -> a

Все экземпляры класса Ord должны определять кроме операций «меньше», «больше», «меньше или равно», «больше или равно», «минимум» и «максимум» ещё и операцию сравнения ==, ибо её класс Ord наследует от класса Eq.

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

Сравнение с другими языками

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

• Хаскел разделяет определения классов и их методов, а такие языки, как C++ и Java вместе определяют структуру данных и методы для её обработки.
• Определения методов в Хаскеле соответствуют абстрактным (чисто виртуальным ) методам C++. Каждый конкретный экземпляр класса должен переопределять методы класса.
• Больше всего классы Хаскела похожи на интерфейсы Java. Как и определение интерфейса, классы в Хаскеле предоставляют протокол использования объекта, вместо определения самих объектов.
• Хаскел не поддерживает стиль перегрузки функции, используемый в C++, когда функции с одним и тем же именем получают данные различных типов для обработки.
• Типы объектов в Хаскеле не могут быть выведены неявно. Не существует базового класса для всех классов (как, например, TObject в Delphi).
• C++ и Java добавляют в скомпилированный код идентифицирующую информацию (например, таблицы размещения виртуальных функций). В Хаскеле такого нет; во время интерпретации (компиляции) вся необходимая информация выводится логически.
• Не существует понятия контроля за доступом: нет публичных и защищённых методов. Вместо этого язык предоставляет механизм модуляризации программ.

Упражнения

1. Записать функции, работающие со списками (из упражнений лекции 2). По возможности воспользоваться формализмами охраны и локальными переменными.
   • getN — функция вычленения N-ого элемента из заданного списка.
   • listSumm — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
   • oddEven — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
   • reverse — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
   • map — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
2. Записать более сложные функции, работающие со списками (из упражнений лекции 3). При необходимости воспользоваться дополнительными функциями и определёнными в предыдущем упражнении. По возможности воспользоваться формализмами охраны и локальными переменными.
   • reverseAll — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.
   • position — функция, возвращающая номер первого вхождения заданного атома в список.
   • set — функция, возвращающая список, содержащий единичные вхождения атомов заданного списка.
   • frequency — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.
3. Описать следующие классы типов. При необходимости воспользоваться механизмом наследования классов.
   • Show — класс, объекты экземпляров которого могут быть выведены на экран.
   • Number — класс, описывающий числа различной природы.
   • String — класс, описывающий строки (списки символов).
4. Определить типы-экземпляры классов, описанных в предыдущем задании. По возможности для каждого экземпляра класса определить методы, работающие с объектами этого класса.
   • Integer — тип целых чисел.
   • Real — тип действительных чисел.
   • Complex — тип комплексных чисел.
   • WideString — тип строк, в виде последовательности двухбайтовых символов в кодировке Юникод.

Ответы

Все нижеприведённые описания на Хаскеле являются лишь одними из большого ряда возможных:

1.

• getN:

getN :: Integer -> [a] -> a
getN 1 (h:t) = h
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)

2.

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

3.

• Show:

class Show a where
  show :: a -> String

• Number:

class Number a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  (/) :: a -> a -> a

• String:

class String a where
  (++)   :: a -> a -> a
  length :: a -> Integer

4.

• 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

…

• Real:

instance Number Real where
  x + y = plusReal x y
  …

• Complex:

instance Number Complex where
  x + y = plusComplex x y
  …

• WideString:

instance String WideString where
  x ++ y   = wideConcat x y
  length x = wideLength x

wideConcat x y = append x y
wideLength x   = length x