Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
м правки
Строка 1:
__TOC__
 
{{ОФП Содержание}}
 
Синтаксис [[w:Haskell|Хаскела]] очень похож на синтаксис абстрактного функционального языка. При разработке Хаскела создатели попытались собрать всё лучшее из имеющихся к этому времени функциональных языков и отринуть всё худшее. Кажется, получилось...получилось…
 
Здесь продолжается рассмотрение служебных слов, начатое в '''[[Основы функционального программирования/Основы языка Haskell|предыдущей лекции]]'''. Будут показаны различные нововведения в парадигму функционального программирования, реализованные в Хаскеле.
 
== Охрана и локальные переменные ==
Строка 18 ⟶ 19 :
Для того, чтобы облегчить написание программ и сделать их читабельнее и проще для понимания, когда в определении функции записано большое много [[w:клоз|клозов]], в Хаскеле используется ключевое слово <code>case</code>. При помощи этого слова можно не записывать клозы определения функций так, как это принято в «чистом» функциональном программировании, а несколько сократить запись. Вот общий вид определения функций со служебным словом <code>case</code>:
 
<code>Function X1 X2 ...… Xk = <strong>case</strong> (X1, X2, ...…, Xk) <strong>of</strong>
(P11, P21, ...…, Pk1) -> Expression1
...…
(P1n, P2n, ...…, Pkn) -> Expressionn</code>
 
Здесь жирным выделены служебные слова&#769;слова́ и символы языка.
 
Так функция, возвращающая список из первых <math>n</math> элементов заданного списка, может быть определена при помощи <code>case</code>:
 
<code>takeFirst n l = case (n, l) of
(0, _) -> []
(_, []) -> []
(n, (x:xs)) -> (x) : (takeFirst (n - 1) xs)</code>
 
И такая запись будет полностью эквивалентна обычному определению функции:
 
<code>takeFirst 0 _ = []
takeFirst _ [] = []
takeFirst n (x:xs) = (x) : (takeFirst (n – 1) xs)</code>
 
Пришло время объяснить понятие '''маски подстановки'''. В Хаскеле маску обозначают символом нижней черты <code>_</code> (так же, как в [[w:Пролог (язык программирования)|Прологе]]). Этот символ заменяет любой образец и является своего ро&#769;дарода безымянной переменной. Если в выражении клоза нет необходимости использования переменной образца, то её можно заменить маской подстановки. При этом, естественно, происходят отложенные вычисления: то выражение, которое может быть подставлено вместо маски, не вычисляется.
 
Другой способ использования охраняющих конструкций — применение конструкции «<code>if-then-else</code>», которая в Хаскеле тоже поддерживается. Формально, её легко можно превратить в выражение с <code>case</code>. Можно даже считать, что выражение
 
<code>if Exp1 then Exp2 else Exp3</code>
Строка 45 ⟶ 47 :
есть сокращение для
 
<code>case (Exp1) of
(True) -> Exp2
(False) -> Exp3</code>
 
Естественно, что тип <code>Exp1</code> должен быть булевым (<code>Bool</code>), а типы выражений <code>Exp2</code> и <code>Exp3</code> — совпадать (ведь именно значения этих выражений будет возвращено определяемой через конструкцию <code>if-then-else</code> функцией).
 
Для использования локальных переменных (в смысле функциональной парадигмы программирования) в Хаскеле есть два вида записи. Первый полностью подобен математической нотации, введеннойвведённой в '''[[Основы функционального программирования/Структуры данных и базисные операции — 2|третьей лекции]]''':
 
<code>let y = a * b
f x = (x + y) / y
in f c + f d</code>
 
Строка 61 ⟶ 64 :
| y == z = 0
| y < z = z – y
where z = x * x</code>
 
Видно, что язык поддерживает два способа записи определения локальных переменных: префиксный (со словом <code>let</code>) и постфиксный (со словом <code>where</code>). Они равнозначны, их употребление зависит только от предпочтений программиста. Однако обычно постфиксный способ используется в выражениях, где также есть охрана, а префиксный — в остальных случаях.
 
== [[w:Полиморфизм в языках программирования|Полиморфизм] ==
 
В первой лекции уже&#769;уже́ было показано, что функциональная парадигма программирования поддерживает чистый или параметрический [[w:полиморфизм|полиморфизм]]. Однако большинство современных языков не обходятся без так называемого полиморфизма «ad hoc», или [[Перегрузка операций|перегрузки]]. Например, перегрузка практически повсеместно используется для следующих целей:
 
* Литералы 1, 2, 3 и&nbsp;т.&nbsp;д. так далее (т.&nbsp;е.то есть цифры) используются для записи и целых чисел, и чисел произвольной точности.
* Арифметические операции (например, сложение: <code>+</code>) используются для работы с данными различных типов (в том числе нечисловыми, например конкатенация для строк).
* Оператор сравнения (<code>==</code>) используется для сравнения данных различных типов.
 
Перегруженное поведение операций различно для каждого типа данных (зачастую такое поведение вообще может быть неопределено или определено ошибочно), в то время как в параметрическом полиморфизме тип данных, вообще говоря, не важен. В Хаскеле есть механизм для использования перегрузки.
Строка 79 ⟶ 82 :
Рассмотрим функцию <code>element</code>, которая возвращает значение истины присутствия данного элемента в списке (для красоты эта функция описана в инфиксной форме):
 
<code>x `element` [] = False
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> для работы с любым типом данных.
 
[[w:Класс (программирование)|Классы]] типов решают эту проблему в Хаскеле. Чтобы рассмотреть этот механизм в действии, далее определяется класс типов, содержащий оператор равенства.
 
<code>class Eq a where
(==) :: a -> a -> Bool</code>
 
В этой конструкции использованы служебные слова <code>class</code> и <code>where</code>, а также переменная типов <code>a</code>. Символ <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> не является описанием типа, но описывает ограничение, накладываемое на тип <code>a</code>, и это ограничение называется '''контекстом'''. Контексты располагаются перед определением типов и отделяются от них символами <code>=></code>:
Строка 95 ⟶ 98 :
<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>
Строка 106 ⟶ 109 :
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
Строка 115 ⟶ 118 :
_ == _ = False</code>
 
Естественно, что если в языке определено понятие класса, должно быть определена и концепция [[w:Наследование (программирование)|наследования]]. Хотя в Хаскеле под классом понимается нечто более абстрактное, чем в обычных объектно-ориентированных языках, в нём также есть и наследование. В то же время понятие наследования определяется столь же изощрённо, что и понятие класса. Например, от определённого выше класса <code>Eq</code> можно унаследовать класс <code>Ord</code>, который будет представлять сравнимые типы данных. Его определение будет таким:
 
<code>
class (Eq a) => Ord a where
(<), (>), (<=), (>=) :: a -> a -> Bool
min, max :: a -> a -> a</code>
Строка 129 ⟶ 133 :
Хотя классы существуют во многих других языках программирования, понятие класса в Хаскеле довольно особенно.
 
* Хаскель разделяет определения классов и их методов, а такие языки, как [[w:C++|C++]] и [[w:Java|Java]] вместе определяют структуру данных и методы для её обработки.
* Определения методов в Хаскеле соответствуют [[w:Виртуальный метод|виртуальным функциям]] C++. Каждый конкретный экземпляр класса должен переопределять методы класса.
* Больше всего классы Хаскела похожи на [[Интерфейс (объектно-ориентированное программирование)|интерфейсы]] Java. Как и определение интерфейса, классы в Хаскеле предоставляют протокол использования объекта, вместо определения самих объектов.
* Хаскел не поддерживает стиль перегрузки функции, используемый в C++, когда функции с одним и тем же именем получают данные различных типов для обработки.
* Типы объектов в Хаскеле не могут быть выведены неявно. Не существует базового класса для всех классов (как, например, <code>TObject</code> в [[w:Delphi|Delphi]]).
* C++ и Java добавляют в [[w:компиляция|скомпилированный]] код идентифицирующую информацию (например, таблицы размещения виртуальных функций). В Хаскеле такого нет; во время интерпретации (компиляции) вся необходимая информация выводится логически.
* Не существует понятия контроля за доступом: нет публичных и защищенныхзащищённых методов. Вместо этого язык предоставляет механизм модуляризации программ.
 
== Упражнения ==
 
# Записать функции, работающие со списками (из упражнений '''[[Основы функционального программирования/Структуры данных и базисные операции|лекции 2]]'''). По возможности воспользоваться формализмами охраны и локальными переменными.
#* <code>getN</code> — функция вычленения <var>N</var>-ого элемента из заданного списка.
#* <code>listSumm</code> — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
#* <code>oddEven</code> — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
#* <code>reverse</code> — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
#* <code>map</code> — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
# Записать более сложные функции, работающие со списками (из упражнений '''[[Основы функционального программирования/Структуры данных и базисные операции — 2|лекции 3]]'''). При необходимости воспользоваться дополнительными функциями и определёнными в предыдущем упражнении. По возможности воспользоваться формализмами охраны и локальными переменными.
#* <code>reverseAll</code> — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.
#* <code>position</code> — функция, возвращающая номер первого вхождения заданного атома в список.
#* <code>set</code> — функция, возвращающая список, содержащий единичные вхождения атомов заданного списка.
#* <code>frequency</code> — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.
# Описать следующие классы типов. При необходимости воспользоваться механизмом наследования классов.
#* <code>Show</code> — класс, объекты экземпляров которого могут быть выведены на экран.
#* <code>Number</code> — класс, описывающий числа различной природы.
#* <code>String</code> — класс, описывающий строки (списки символов).
# Определить типы-экземпляры классов, описанных в предыдущем задании. По возможности для каждого экземпляра класса определить методы, работающие с объектами этого класса.
#* <code>Integer</code> — тип целых чисел.
#* <code>Real</code> — тип действительных чисел.
#* <code>Complex</code> — тип комплексных чисел.
#* <code>WideString</code> — тип строк, в виде последовательности двухбайтовых символов в кодировке UNICODE[[w:Юникод|Юникод]].
 
== Ответы ==
Строка 165 ⟶ 169 :
 
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
Строка 188 ⟶ 192 :
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
Строка 202 ⟶ 206 :
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
Строка 210 ⟶ 214 :
positionN a (h:t) n = positionN a t (n + 1)
positionN a [] n = 0</code>
* <code>set</code>:
<code>set :: [a] -> [a]
set [] = []
Строка 219 ⟶ 223 :
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
Строка 232 ⟶ 236 :
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
Строка 241 ⟶ 245 :
(*) :: 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
Источник — https://ru.wikibooks.org/wiki/Основы_функционального_программирования/Haskell/Служебные_слова_и_синтаксис