Основы функционального программирования/Haskell/Служебные слова и синтаксис: различия между версиями
Содержимое удалено Содержимое добавлено
Ramir (обсуждение | вклад) Нет описания правки |
Нет описания правки |
||
Строка 1:
__TOC__
{{ОФП Содержание}}
Синтаксис [[w:Haskell|
Здесь продолжается рассмотрение служебных слов, начатое в '''[[Основы функционального программирования/Основы языка Haskell|предыдущей лекции]]'''. Будут показаны различные нововведения в парадигму функционального программирования, реализованные в Хаскеле.▼
▲Синтаксис [[w:Haskell|Хаскеля]] очень похож на синтаксис абстрактного функционального языка. При разработке Haskell’а создатели попытались собрать всё лучшее из имеющихся к этому времени функциональных языков и отринуть всё худшее. Кажется, получилось…
▲Здесь продолжается рассмотрение служебных слов, начатое в [[Основы функционального программирования/Основы языка Haskell|предыдущей лекции]]. Будут показаны различные нововведения в парадигму функционального программирования, реализованные в Хаскеле.
== Охрана и локальные переменные ==
Охрана и локальные переменные используются в функциональном программировании лишь для простоты записи и понимания текстов программ.
<code>sign x | x > 0 = 1
Строка 17 ⟶ 16 :
Функция <code>sign</code> использует три охраняющие конструкции, каждая из которых отделена вертикальной чертой от предыдущего определения. В принципе, таких охраняющих конструкций может быть сколько угодно. Их разбор идёт, естественно, сверху вниз, и если существует непустое пересечение в определении охраны, то сработает конструкция, стоящая раньше (выше) в записи определения функции.
Для того, чтобы облегчить написание программ и сделать их читабельнее и проще для понимания, когда в определении функции записано большое много [[w:клоз|клозов]], в Хаскеле используется ключевое слово <code>case</code>. При помощи этого
<code>Function X1 X2 ... Xk = case (X1, X2, ..., Xk) of
Строка 24 ⟶ 23 :
(P1n, P2n, ..., Pkn) Expressionn</code>
Здесь жирным выделены служебные слова́ и символы языка.
Так функция, возвращающая список из первых <
<code>takeFirst n l = case (n, l) of (0, _)
И такая запись будет полностью эквивалентна обычному определению функции:
Строка 38 ⟶ 37 :
takeFirst n (x:xs) = (x) : (takeFirst (n – 1) xs)</code>
Пришло время объяснить понятие '''маски подстановки'''. В Хаскеле маску обозначают символом нижней черты <code>_</code> (так же, как в [[w:Пролог (язык программирования)|Прологе]]). Этот символ заменяет любой образец и является своего
Другой способ использования охраняющих конструкций
▲Другой способ использования охраняющих конструкций -- применение конструкции «<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>
Для использования локальных переменных (в смысле функциональной парадигмы программирования) в Хаскеле есть два вида записи. Первый полностью подобен математической нотации, введенной в '''[[Основы функционального программирования/Структуры данных и базисные операции — 2|третьей лекции]]''':
<code>let y = a * b
Строка 55 ⟶ 56 :
in f c + f d</code>
Другой способ
<code>f x y | y > z = y – z
| y == z = 0
Строка 61 ⟶ 63 :
where z = x * x</code>
Видно, что язык поддерживает два способа записи определения локальных переменных: префиксный (со словом <code>let</code>) и постфиксный (<code>where</code>). Они равнозначны, их употребление зависит только от предпочтений программиста. Однако обычно постфиксный способ используется в выражениях, где также есть охрана, а префиксный
== Полиморфизм ==
В первой лекции уже́ было показано, что функциональная парадигма программирования поддерживает чистый или параметрический [[w:полиморфизм|полиморфизм]]. Однако большинство современных языков не обходятся без так называемого полиморфизма «ad hoc», или перегрузки. Например, перегрузка практически повсеместно используется для следующих целей:
*Литералы 1, 2, 3 и
*Арифметические операции (например, сложение: <code>+</code>) используются для работы с данными различных типов (в том числе нечисловыми, например конкатенация для строк).
*Оператор сравнения (<code>==</code>) используется для сравнения данных различных типов.
Строка 73 ⟶ 75 :
Перегруженное поведение операций различно для каждого типа данных (зачастую такое поведение вообще может быть неопределено или определено ошибочно), в то время как в параметрическом полиморфизме тип данных, вообще говоря, не важен. В Хаскеле есть механизм для использования перегрузки.
Рассмотреть возможность использования полиморфизма «ad hoc» проще всего на примере операции сравнения. Есть много типов, для которых можно и целесообразно переопределить операцию сравнения, но для некоторых типов эта операция бесполезна. Например, сравнение функций бессмысленно; функции необходимо вычислять и сравнивать результаты этих вычислений. Но может возникнуть необходимость сравнивать списки. Конечно, здесь речь идет о сравнении значений, а не сравнении указателей (как, например, это сделано в языке [[w:Java|Java]]).
Рассмотрим функцию <code>element</code>, которая возвращает значение истины присутствия данного элемента в списке (для красоты эта функция описана в инфиксной форме):
Строка 80 ⟶ 82 :
x `element` (y:ys) = (x == y) || (x `element` ys)</code>
Здесь видно, что у функции <code>element</code> тип <code>(a
Классы типов решают эту проблему в Хаскеле. Чтобы рассмотреть этот механизм в действии, далее определяется класс типов, содержащий оператор равенства.
Строка 87 ⟶ 89 :
(==) :: a -> a -> Bool</code>
В этой конструкции использованы служебные слова <code>class</code> и <code>where</code>, а также переменная типов <
Ограничение того факта, что тип <code>a</code> должен быть экземпляром класса <code>Eq</code> записывается как <code>(Eq a)</code>. Поэтому выражение <code>(Eq a)</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
<code>element :: (Eq a) => a -> [a] -> Bool</code>
Строка 98 ⟶ 102 :
Теперь возникает проблема определения того, какие типы являются экземплярами класса <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>Tree</code> (см. '''[[Основы функционального программирования/Основы языка Haskell|лекцию 4]]''') определение будет выглядеть так:
<code>instance (Eq a) => Eq (Tree a) where
Строка 110 ⟶ 115 :
_ == _ = False</code>
Естественно, что если в языке определено понятие класса, должно быть определена и концепция наследования. Хотя в Хаскеле под классом понимается нечто более абстрактное, чем в обычных объектно-ориентированных языках, в нём также есть и наследование. В то же время понятие наследования определяется столь же
<code>class (Eq a) => Ord a where
(<), (>), (<=), (>=) :: a -> a -> Bool
Строка 125 ⟶ 131 :
*Хаскель разделяет определения классов и их методов, а такие языки, как [[w:C++|C++]] и [[w:Java|Java]] вместе определяют структуру данных и методы для её обработки.
*Определения методов в Хаскеле соответствуют виртуальным функциям C++. Каждый конкретный экземпляр класса должен переопределять методы класса.
*Больше всего
*
*Типы объектов в Хаскеле не могут быть выведены неявно. Не существует базового класса для всех классов (как, например, TObject в [[w:Delphi|Delphi]]).
*C++ и Java добавляют в [[w:компиляция|скомпилированный]] код идентифицирующую информацию (например, таблицы размещения виртуальных функций). В Хаскеле такого нет; во время интерпретации (компиляции) вся необходимая информация выводится логически.
Строка 133 ⟶ 139 :
== Упражнения ==
#*<code>getN</code> — функция вычленения <var>N</var>-ого элемента из заданного списка.
#*<code>listSumm</code> — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
#*<code>oddEven</code> — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
#*<code>reverse</code> — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
#*<code>map</code> — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
#*<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.
Все нижеприведённые описания на
1.
*<code>getN</code>:
<code>getN
getN n []
getN 1 (h:t)
getN n (h:t)
*<code>listSumm</code>:
<code>listSumm
listSumm [] l
listSumm l []
listSumm (h1:t1) (h2:t2)
*<code>oddEven</code>:
<code>oddEven
oddEven []
oddEven [x]
oddEven (h1:(h2:t))
*<code>reverse</code>:
<code>append
append [] l
append (h:t) l2
reverse
reverse []
reverse (h:t)
*<code>map</code>:
<code>map
map f []
map f (h:t)
2.
*<code>reverseAll</code>:
<code>atom
atom a
atom _
reverseAll
reverseAll l
reverseAll []
reverseAll (h:t)
*<code>position</code>:
<code>position
position a l
positionN
positionN a (a:t) n
positionN a (h:t) n
positionN a [] n
*<code>set</code>:
<code>set
set []
set (h:t)
include
include a []
include a (a:t)
include a (b:t)
*<code>frequency</code>:
<code>frequency
frequency l
f
f l []
f l (h:t)
corrector
corrector a []
corrector a (a:n):t
corrector a h:t
3.
*<code>Show</code>:
<code>class Show a where
*<code>Number</code>:
<code>class Number a where
*<code>String</code>:
<code>class String a where
4.
*<code>Integer</code>:
<code>instance Number Integer where
plusInteger
plusInteger x y
...</code>
*<code>Real</code>:
<code>instance Number Real where
*<code>Complex</code>:
<code>instance Number Complex where
*<code>WideString</code>:
<code>instance String WideString where
wideConcat x y
wideLength x
|