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

Нет описания правки
__TOC__
{{ОФП Содержание}}
 
Синтаксис [[w:Haskell|ХаскеляХаскела]] очень похож на синтаксис абстрактного функционального языка. При разработке Haskell’аХаскела создатели попытались собрать всё лучшее из имеющихся к этому времени функциональных языков и отринуть всё худшее. Кажется, получилось…получилось...
= Лекция 5. Служебные слова и синтаксис Haskell’а =
 
Здесь продолжается рассмотрение служебных слов, начатое в '''[[Основы функционального программирования/Основы языка Haskell|предыдущей лекции]]'''. Будут показаны различные нововведения в парадигму функционального программирования, реализованные в Хаскеле.
Синтаксис [[w:Haskell|Хаскеля]] очень похож на синтаксис абстрактного функционального языка. При разработке Haskell’а создатели попытались собрать всё лучшее из имеющихся к этому времени функциональных языков и отринуть всё худшее. Кажется, получилось…
 
Здесь продолжается рассмотрение служебных слов, начатое в [[Основы функционального программирования/Основы языка Haskell|предыдущей лекции]]. Будут показаны различные нововведения в парадигму функционального программирования, реализованные в Хаскеле.
 
== Охрана и локальные переменные ==
 
Охрана и локальные переменные используются в функциональном программировании лишь для простоты записи и понимания текстов программ. ХаскельХаскел не обошёл своим вниманием и этот аспект, в его синтаксисе имеются средства, дающие организовать охрану и использовать локальные переменные. Если надо определить функцию с охраной, то надо использовать символ вертикальной черты <code>|</code>.
 
<code>sign x | x > 0 = 1
Функция <code>sign</code> использует три охраняющие конструкции, каждая из которых отделена вертикальной чертой от предыдущего определения. В принципе, таких охраняющих конструкций может быть сколько угодно. Их разбор идёт, естественно, сверху вниз, и если существует непустое пересечение в определении охраны, то сработает конструкция, стоящая раньше (выше) в записи определения функции.
 
Для того, чтобы облегчить написание программ и сделать их читабельнее и проще для понимания, когда в определении функции записано большое много [[w:клоз|клозов]], в Хаскеле используется ключевое слово <code>case</code>. При помощи этого словасло&$769;ва можно не записывать клозы определения функций так, как это принято в «чистом» функциональном программировании, а несколько сократить запись. Вот общий вид определения функций ссо служебным словом <code>case</code>'ом:
 
<code>Function X1 X2 ... Xk = case (X1, X2, ..., Xk) of
(P1n, P2n, ..., Pkn)  Expressionn</code>
 
Здесь жирным выделены служебные слова&#769; и символы языка.
 
Так функция, возвращающая список из первых <varmath>n</varmath> элементов заданного списка, может быть определена при помощи <code>case</code>:
 
<code>takeFirst n l = case (n, l) of (0, _) -> []
(_, []) -> []
(n, (x:xs)) -> (x) : (takeFirst (n - 1) xs)</code>
 
И такая запись будет полностью эквивалентна обычному определению функции:
takeFirst n (x:xs) = (x) : (takeFirst (n – 1) xs)</code>
 
Пришло время объяснить понятие '''маски подстановки'''. В Хаскеле маску обозначают символом нижней черты <code>_</code> (так же, как в [[w:Пролог (язык программирования)|Прологе]]). Этот символ заменяет любой образец и является своего родаро&#769;да безымянной переменной. Если в выражении клоза нет необходимости использования переменной образца, то её можно заменить маской подстановки. При этом, естественно, происходят отложенные вычисления: то выражение, которое может быть подставлено вместо маски, не вычисляется.
 
Другой способ использования охраняющих конструкций -- применение конструкции «<code>if</code>-<code>then</code>-<code>else</code>», которая в Хаскеле тоже поддерживается. Формально, её легко можно превратить в выражение с <code>case</code>. Можно даже считать, что выражение
 
Другой способ использования охраняющих конструкций -- применение конструкции «<code>if</code>-<code>then</code>-<code>else</code>», которая в Хаскеле тоже поддерживается. Формально, её легко можно превратить в выражение с <code>case</code>. Можно даже считать, что выражение
<code>if Exp1 then Exp2 else Exp3</code>
 
есть сокращение для
 
<code>case (Exp1) of (True) -> Exp2
(False) -> Exp3</code>
 
Естественно, что тип <code>Exp1</code> должен быть булевым (<code>Bool</code>), а типы выражений <code>Exp2</code> и <code>Exp3</code> -- совпадать (ведь именно значения этих выражений будет возвращено определяемой через конструкцию <code>if</code>-<code>then</code>-<code>else</code>- функцией).
 
Для использования локальных переменных (в смысле функциональной парадигмы программирования) в Хаскеле есть два вида записи. Первый полностью подобен математической нотации, введенной в '''[[Основы функционального программирования/Структуры данных и базисные операции — 2|третьей лекции]]''':
 
<code>let y = a * b
in f c + f d</code>
 
Другой способ -- описание локальной переменной после использования. При этом используется служебное слово <code>where</code>, которое ставится в конце выражения:
 
<code>f x y | y > z = y – z
| y == z = 0
where z = x * x</code>
 
Видно, что язык поддерживает два способа записи определения локальных переменных: префиксный (со словом <code>let</code>) и постфиксный (<code>where</code>). Они равнозначны, их употребление зависит только от предпочтений программиста. Однако обычно постфиксный способ используется в выражениях, где также есть охрана, а префиксный -- в остальных случаях.
 
== Полиморфизм ==
 
В первой лекции уже&#769; было показано, что функциональная парадигма программирования поддерживает чистый или параметрический [[w:полиморфизм|полиморфизм]]. Однако большинство современных языков не обходятся без так называемого полиморфизма «ad hoc», или перегрузки. Например, перегрузка практически повсеместно используется для следующих целей:
 
*Литералы 1, 2, 3 и &nbsp;т.&nbsp;д. (т.&nbsp;е. цифры) используются для записи и целых чисел, и чисел произвольной точности.
*Арифметические операции (например, сложение: <code>+</code>) используются для работы с данными различных типов (в том числе нечисловыми, например конкатенация для строк).
*Оператор сравнения (<code>==</code>) используется для сравнения данных различных типов.
Перегруженное поведение операций различно для каждого типа данных (зачастую такое поведение вообще может быть неопределено или определено ошибочно), в то время как в параметрическом полиморфизме тип данных, вообще говоря, не важен. В Хаскеле есть механизм для использования перегрузки.
 
Рассмотреть возможность использования полиморфизма «ad hoc» проще всего на примере операции сравнения. Есть много типов, для которых можно и целесообразно переопределить операцию сравнения, но для некоторых типов эта операция бесполезна. Например, сравнение функций бессмысленно; функции необходимо вычислять и сравнивать результаты этих вычислений. Но может возникнуть необходимость сравнивать списки. Конечно, здесь речь идет о сравнении значений, а не сравнении указателей (как, например, это сделано в языке [[w:Java|Java]]).
 
Рассмотрим функцию <code>element</code>, которая возвращает значение истины присутствия данного элемента в списке (для красоты эта функция описана в инфиксной форме):
x `element` (y:ys) = (x == y) || (x `element` ys)</code>
 
Здесь видно, что у функции <code>element</code> тип <code>(a -> [a] -> Bool)</code>, но при этом тип операции <code>==</code> должен быть <code>(a -> a -> Bool)</code>. Раз переменная типа <code>a</code> может обозначать любой тип (в том числе и список), целесообразно переопределить операцию <code>==</code> для работы с любым типом данных.
 
Классы типов решают эту проблему в Хаскеле. Чтобы рассмотреть этот механизм в действии, далее определяется класс типов, содержащий оператор равенства.
(==) :: a -> a -> Bool</code>
 
В этой конструкции использованы служебные слова <code>class</code> и <code>where</code>, а также переменная типов <varcode>a</varcode>. Символ <code>Eq</code> является именем определяемого класса. Эта запись может быть прочитана как «Тип <code>a</code> является экземпляром класса <code>Eq</code> если для этого типа перегружена операция сравнения <code>==</code> соответствующего типа». Операция сравнения должна быть определена на паре объектов одного и того же типа.
 
Ограничение того факта, что тип <code>a</code> должен быть экземпляром класса <code>Eq</code> записывается как <code>(Eq a)</code>. Поэтому выражение <code>(Eq a)</code> не является описанием типа, но описывает ограничение, накладываемое на тип <varcode>a</varcode>, и это ограничение называется '''контекстом'''. Контексты располагаются перед определением типов и отделяются от них символами <code>=></code>:
 
Ограничение того факта, что тип a должен быть экземпляром класса <code>Eq</code> записывается как <code>(Eq a)</code>. Поэтому выражение <code>(Eq a)</code> не является описанием типа, но описывает ограничение, накладываемое на тип <var>a</var>, и это ограничение называется '''контекстом'''. Контексты располагаются перед определением типов и отделяются от них символами <code>=></code>:
<code>(==) :: (Eq a) => a -> a -> Bool</code>
 
Это читается «Для каждого типа <code>a</code>, являющегося экземпляром класса <code>Eq</code>, определена операция <code>==</code>, которая имеет тип <code>(a -> a -> Bool)</code>». Эта операция должна быть использована в функции <code>element</code>, поэтому ограничение распространяется и на неё. В этом случае необходимо явно указывать тип функции:
 
<code>element :: (Eq a) => a -> [a] -> Bool</code>
 
 
Теперь возникает проблема определения того, какие типы являются экземплярами класса <code>Eq</code>. Для этого есть служебное слово <code>instance</code>. Например, чтобы предписать, что тип <code>Integer</code> является экземпляром <code>Eq</code>, надо написать:
 
<code>instance Eq Integer where
x == y = x `integerEq` y</code>
 
В этом выражении определение операции <code>==</code> называется определением метода, как в [[w:объектно-ориентированное программирование|объектно-ориентированной парадигме]]. Функция <code>integerEq</code> может быть любой (и не обязательно инфиксной), лишь бы у неенеё был тип <code>(a -> a -> Bool)</code>. В этом случае скорее всего подойдет примитивная функция сравнения двух натуральных чисел. Прочитать написанное выражение можно следующим образом: «Тип <code>Integer</code> является экземпляром класса <code>Eq</code>, и далее приводится определение метода, который производит сравнение двух объектов типа <code>Integer</code>».
 
Таким же образом можно определить операцию сравнения и для бесконечных рекурсивных типов. Например, для типа <code>Tree</code> (см. '''[[Основы функционального программирования/Основы языка Haskell|лекцию 4]]''') определение будет выглядеть так:
 
<code>instance (Eq a) => Eq (Tree a) where
_ == _ = False</code>
 
Естественно, что если в языке определено понятие класса, должно быть определена и концепция наследования. Хотя в Хаскеле под классом понимается нечто более абстрактное, чем в обычных объектно-ориентированных языках, в нём также есть и наследование. В то же время понятие наследования определяется столь же изощренноизощрённо, что и понятие класса. Например, от определённого выше класса <code>Eq</code> можно унаследовать класс <code>Ord</code>, который будет представлять сравнимые типы данных. Его определение будет таким:
 
<code>class (Eq a) => Ord a where
(<), (>), (<=), (>=) :: a -> a -> Bool
*Хаскель разделяет определения классов и их методов, а такие языки, как [[w:C++|C++]] и [[w:Java|Java]] вместе определяют структуру данных и методы для её обработки.
*Определения методов в Хаскеле соответствуют виртуальным функциям C++. Каждый конкретный экземпляр класса должен переопределять методы класса.
*Больше всего хаскельские классы Хаскела похожи на интерфейсы Java. Как и определение интерфейса, классы в Хаскеле предоставляют протокол использования объекта, вместо определения самих объектов.
*HaskellХаскел не поддерживает стиль перегрузки функции, используемый в C++, когда функции с одним и тем же именем получают данные различных типов для обработки.
*Типы объектов в Хаскеле не могут быть выведены неявно. Не существует базового класса для всех классов (как, например, TObject в [[w:Delphi|Delphi]]).
*C++ и Java добавляют в [[w:компиляция|скомпилированный]] код идентифицирующую информацию (например, таблицы размещения виртуальных функций). В Хаскеле такого нет; во время интерпретации (компиляции) вся необходимая информация выводится логически.
== Упражнения ==
 
1. #Записать функции, работающие со списками (из упражнений '''[[Основы функционального программирования/Структуры данных и базисные операции|лекции 2]]'''). По возможности воспользоваться формализмами охраны и локальными переменными.
#*<code>getN</code> — функция вычленения <var>N</var>-ого элемента из заданного списка.
#*<code>listSumm</code> — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
#*<code>oddEven</code> — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
#*<code>reverse</code> — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
#*<code>map</code> — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
2. #Записать более сложные функции, работающие со списками (из упражнений '''[[Основы функционального программирования/Структуры данных и базисные операции — 2|лекции 3]]'''). При необходимости воспользоваться дополнительными функциями и определёнными в предыдущем упражнении. По возможности воспользоваться формализмами охраны и локальными переменными.
#*<code>reverseAll</code> — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.
#*<code>position</code> — функция, возвращающая номер первого вхождения заданного атома в список.
#*<code>set</code> — функция, возвращающая список, содержащий единичные вхождения атомов заданного списка.
#*<code>frequency</code> — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.
3. #Описать следующие классы типов. При необходимости воспользоваться механизмом наследования классов.
#*<code>Show</code> — класс, объекты экземпляров которого могут быть выведены на экран.
#*<code>Number</code> — класс, описывающий числа различной природы.
#*<code>String</code> — класс, описывающий строки (списки символов).
4. #Определить типы-экземпляры классов, описанных в предыдущем задании. По возможности для каждого экземпляра класса определить методы, работающие с объектами этого класса.
#*<code>Integer</code> — тип целых чисел.
#*<code>Real</code> — тип действительных чисел.
#*<code>Complex</code> — тип комплексных чисел.
#*<code>WideString</code> — тип строк, в виде последовательности двухбайтовых символов в кодировке UNICODE.
 
=== Ответы ===
 
Все нижеприведённые описания на Haskell’еХаскеле являются лишь одними из большого ряда возможных:
 
1.
*<code>getN</code>:
<code>getN :: [a] -> a
getN n [] = _
getN 1 (h:t) = h
getN n (h:t) = getN (n – 1) t</code>
*<code>listSumm</code>:
<code>listSumm :: Ord (a) => [a] -> [a]
listSumm [] l = l
listSumm l [] = l
listSumm (h1:t1) (h2:t2) = (h1 + h2) : (listSumm t1 t2)</code>
*<code>oddEven</code>:
<code>oddEven :: [a] -> [a]
oddEven [] = []
oddEven [x] = [x]
oddEven (h1:(h2:t)) = (h2:h1) : (oddEven t)</code>
*<code>reverse</code>:
<code>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])</code>
*<code>map</code>:
<code>map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (h:t) = (f h) : (map f t)</code>
2.
*<code>reverseAll</code>:
<code>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)</code>
*<code>position</code>:
<code>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</code>
*<code>set</code>:
<code>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)</code>
*<code>frequency</code>:
<code>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)</code>
3.
*<code>Show</code>:
<code>class Show a where
show :: a -> a</code>
*<code>Number</code>:
<code>class Number a where
(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
(/) :: a -> a -> a</code>
*<code>String</code>:
<code>class String a where
(++) :: a -> a -> a
length :: a -> Integer</code>
4.
*<code>Integer</code>:
<code>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
...</code>
*<code>Real</code>:
<code>instance Number Real where
x + y = plusReal x y
...</code>
*<code>Complex</code>:
<code>instance Number Complex where
x + y = plusComplex x y
...</code>
*<code>WideString</code>:
<code>instance String WideString where
x ++ y = wideConcat x y
length x = wideLength x
wideConcat x y = append x y
wideLength x = length x</code>
271

правка