BookBody.tex

\documentclass[10pt,a4paper]{article}

\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{multirow}
%\usepackage{graphicx}
\usepackage{theorem}

\ifx\pdfoutput\undefined
\usepackage{graphicx}
\else
\usepackage[pdftex]{graphics}
\fi

%for multirow:
\newcommand{\minitab}[2][l]{\begin{tabular}{#1}#2\end{tabular}}
\newcommand{\GrT}[1]{{\tt #1}}
\newcommand{\HSp}{\hspace{0.5in}}
\newcommand{\DHSp}{\hspace{1.0in}}
%\renewcommand{\labelitemi}{$\box$}
\renewcommand{\epsilon}{\varepsilon}

\newcommand{\sss}[1]{\setcounter{secnumdepth}{4} \subsubsection{#1} \setcounter{secnumdepth}{2}}

\newcommand{\has}{Haskell\ }
\newcommand{\hasrep}{"`Haskell Report"'}
\newcommand{\trans}{Прим.пер.}

\newcommand{\code}[1]{\texttt{#1}}
% theorems:
%\newtheorem{theorem}{Теорема}d
\newtheorem{definition}{Определение}

\oddsidemargin=5mm
\evensidemargin=5mm
\textwidth=15cm

\title{Введение в Haskell 98}
\author{Paul Hudak \and John Peterson \and Joseph H.Fasel\thanks{Translation from english by Anthony Akentiev (перевод с английского выполнен Федором Дрябкиным}}
\begin{document}
\maketitle
%\tableofcontents

\section{Введение}
Цель данного руководства не в обучении программированию, ни тем более обучению функциональному программированию. Оно служит в качестве дополнения к \hasrep, которое является  отнюдь не компактным. Наша задача состоит в том, чтобы "`открыть дверь"' в \has человеку, который работал до этого с, по крайней мере, одним языком программирования (желательно функциональным или "`практически-функциональным"' вроде ML или Scheme). Если читатель желает лучше изучить функциональное программирование, то мы очень рекомендуем ему текст Бёрда (Bird) под названием "`Введение в функциональное программирование"' (\textit{Introduction to Functional Programming}) или "`Введение в функциональное программирование на \has"' (\textit{An introduction to Functional Programming Systems Using Haskell}) написанное Дэйви. Ещё одним полезным источником принципов, на которых основан \has, может служить .\\

	Язык \has претерпел существенные изменения с момента его появления в 1987 году. Настоящая статья подразумевает использование версии 98 года. Более ранние версии языка теперь считаются устаревшими (obsolete); пользователи \has вынуждены иметь дело лишь с \has 98. Существует множество расширений этого языка, которые достаточно широко используются. Они не являются темой для рассмотрения данной статьи. \\
	
	В данном руководстве используется наш главный принцип: необходимо мотивировать идею, привести примеры, а затем сослаться на \hasrep. Тем не менее, мы рекомендуем читателю не вникать в детали до тех пор, пока он не дочитает данное творение до конца. Стандартная \textit{прелюдия}\footnote{Позволю себе такой перевод названия модуля 'Prelude' - \trans} \has (см. Дополнение А \hasrep и стандартные библиотеки (описаны в "`Library Report"') содержит огромное количество полезных примеров. После прочтения настоящего руководства можно переходить к вдумчивому чтению текста этого модуля. Это не только поможет читателю разобраться, что же прдествляет из себя настоящий код \has, но и поможет в изучении встроенных (заранее написанных) функций и типов.\\
	
	На последок, не забывайте про веб-сайт \has - \textbf{http://haskell.org}, который содержит множество информации о языке и его различным реализациям.\\
	
	[Конечно же, мы не хотели перегруать текст излишне строгими синтаксическими правилами, а скорее пожелали вводить их постепенно по мере необходимости. Обратите внимание, что мы будем заключать их в такие квадратные скобки, как и этот абзац. Этим данное руководство сильно отличается от \hasrep, но именно последний является полноценным источником деталей, так что указатели (например, "`\verb|§| 2.1"') будут указывать на главы \hasrep.]\\
%дефиз???
	\has является строго-типизированным языком\footnote{Luca Cardelli предложил использовать термин \textit{typeful}}: на типах основано всё, и часто новички пугаются такому обилию возможностей. Для тех, кто имел дело лишь с "`нетипизированными"' языками вроде Perl,Tcl,Scheme это покажется вдвойне сложным. Для тех же, кто работал с Java,C,Modula,ML это не будет чем-то особенно новым, но в любом случае учиться придётся многому, так как сстема типов \has чуть другая и, как правило, выглядит богаче. В конце концов, "`строгая типизация"' \has является той неизбежностью, которой не избежать.
	
\section{Значения,Типы и так далее}

Так как \has является т.н. "`чистым"' функциональным языком программирования, все вычисления организованны с помощью \textit{выражений} (синтаксический терм), которые вычисляют \textit{значения} (абстрактные сущности, которые очень походят на ответы). Каждое значение имеет определённый \textit{тип}. (Можно считать, что типы являются множествами, содержащими значения). Примерами выражений являются атомарные величины, вроде \textbf{5}, символа \textbf{'a'}, функции \verb|\x -> x+1|, а также структурированные величины, например список \textbf{[1,2,3]} или т.н. пара \textbf{('b',4)}.\\

	Так же как выражения обозначают сами значения, типовыражения\footnote{Позволю себе несколлько вольный перевод - \trans} (type expressions) являются синтаксическими термами, которые "`отображают"' типы значений (или просто \textit{типы}). Примерами типовыражений являются атомарные типы вроде \textbf{Integer} (целые бесконечной точности), \textbf{Char} (символы), \textbf{Integer $\rightarrow$ Integer} (фукния, оторажающая \textbf{Integer} в другой \textbf{Integer}), а также структурированные типы, например \textbf{[Integer]} (однородный список из целых чисел) или \textbf{(Char,Integer)} (пара символ/целое).\\
	
	Все значения в \has являются "`первоклассными"' (first-class values), что означает, что они могут быть передаваться фцнкциям в качестве аргументов, возвращаться в качестве результатов, могут быть помещены в различные структуры, и т.д. с другой стороны, типы \has не являются первоклассными. Типы описывают значения, а ассоциацию значения с типом называют \textit{типизацией}. Можно описать типы вышеприведённых значений так:
\begin{figure}[ht]
\DHSp
\label{fig_types1}
\begin{tabular}{llr}
\GrT{$5$} & $::$ & $Integer$\\
\GrT{$'a'$} & $::$ & $Char$\\
\GrT{$inc$} & $::$ & $Integer \rightarrow Integer$\\
\GrT{$[1,2,3]$} & $::$ & $[Integer]$\\
\GrT{$('b',4)$} & $::$ & $(Char,Integer)$\\
\end{tabular}
\end{figure}

Двойное двоеточие ($::$) означает "`имеет тип"'.\\

Функции в \has обычно определяются серией \textit{уравнений} (eqauation). Для примера, функция $inc$ может быть описана следующим единственным уравнением:\\
$$inc n = n + 1$$
Уравнение является примером \textit{объявления} (declaration). Другим типом объявления является \textit{объявление сигнатуры типа} (type signature declaration) (\verb|§| 4.4.1), с помощью которого можно явно указать тип функции \textbf{inc}:
$$inc\ :: Integer\ \rightarrow Integer$$

Более подробно объявления функций будут рассмотрены в главе 3.\\

Когда мы хотим указать, что выражение $e_1$ вычисляется (evaluates) или "`редуцируется"' (reduces) в выражение $e_2$, мы записываем это следующим образом:
$$e_1\  \Rightarrow e_2$$

Например:
$$inc\ (inc\ 3)\ \Rightarrow 5$$
	Система статических типов \has устанавливает формальную связь между типами и значениями (\verb|§| 4.1.3). Она гарантирует, что программы, написанные на \has являются \textit{типобезопасными}, т.е. что программист нигде не ошибся (касемо типов). Например, мы не сможем просто сложить два символа: выражение $'a' + 'b'$ не согласовано с типом (ill-typed). Главное преимущество статически типизированных языков хорошо известно: все ошибки, связанные с типами, обнаруживаются во время компиляции. Конечно, не все ошибки могут быть обнаружены системой типизации (системой типов): выражения, такие как $1/0$ являются валидными, но их вычисление приведёт к ошибке времени выполнения. Тем не менее, система типов помогает находить многие ошибки программиста во время компиляции, а также помогает компилятору генерировать более эффективный код (не требуется никаких проверок или тэгов во время исполнения).\\
	
	Система типов гарантирует, что указанные пользователем (программистом) сигнатуры типов корректны. Вообще, система типов \has позволяет вообще не указывать сигнатур типов\footnote{С некоторыми исключениями, описанными далее}; мы говорим, что система типов автоматически \textit{выводит} (infers) корректные типы. Тем не менее, наличие в программе явно указанных типов считается "`хорошим тоном"', помогающим докумментировать программы и легче находить ошибки.\\
	
	[Надеемся, читатель обратил внимание на то, что идентификаторы типов записаны с прописной буквы ($Integer, Char$), а идентификаторы, означающие значения - со строчной буквы ($inc$). Это не простая условность: \has требует, чтобы это было так. В \has $foo, fOo, fOO$ являются различными идентификаторами.]
	
\subsection{Полиморфные типы}
Система типов \has включает и \textit{полиморфные} типы - типы, которые стоят "`над обычными типами"'. Полиморфные типы описывают семейства (families) типов. Для примера, $(\forall a)[a]$ является семейством типов, которое состоит, для любого $a$, из списка, в котором элементами являются $a$. Список целых чисел (например, $[1,2,3]$), список символов (например, $['a','b','c']$), список списков целых чисел (и т.д.) - всё это члены такого семейства. (Обратите внимание на то, что $[2,'b']$ \textit{не является} членом, так как не существет одного типа для $2$ и $'b'$\footnote{Другими словами - такой список не является гомогенным - \trans})
	[Идентификаторы, такие как $a$ называют \textit{переменными типов} (type variables) и записываются с прописной буквы,  чтобы отличать их непосредственно от конкретных типов (например, $Int$). Так как в \has имеются только типы, стоящие под кватором $\forall$, нет нужды явно указывать его. Это означает, что мы можем просто использовать, допустим, $[a]$. Другими словами, все переменные типов стоят под квантором $\forall$.]
	
	Списки являются наиболее часто используемыми структурами данных в функциональных языках. Очень удобно показать основы полиморфизма с их помощью. Список $[1,2,3]$ является сокращением для $1:(2:(3:[]))$, где $[]$ является пустым списком, а $:$ является инфиксным оператором, который добавляет его первый аргумент в голову своего второго аргумента (списка). Так как $:$ является правоассоциативным, можно написать тоже самое так: $1:2:3:[]$.\\
	
	В качестве примера определения функции, которая работает со списков, приведём функцию, которая подсчитывает количество элементов списка:
\begin{figure}[ht]
\DHSp
\label{fig_fun1}
\begin{tabular}{lcl}
\GrT{$length$} & $::$ & $[a]\ -> Integer$\\
\GrT{$length\ []$} & $=$ & $0$\\
\GrT{$length\ (x:xs)$} & $=$ & $1\ +\ length\ xs$\\
\end{tabular}
\end{figure}	
Это определние говорит само за себя. Можно просто прочитать эти уравнения так: "`Длина пустого списка равна нулю; длина списка, у которго первым элементом является $x$, а вторым $xs$, равна еденице плюс длине остатка $xs$."' (Обратите внимание, что $xs$ является множественным числом $x$.)\\

Этот пример открывает нам важную особенность \has: \textit{сопоставление с образцом} (pattern matching). Левосторонние части уравнений содержат образец (например $[]$ или $s:xs$). При вызове функции эти образцы сопоставляются с параметрами функции ($[]$ подходит к пустому списку, $x:xs$ подойдёт к списку из хотя бы одного элемента). При этом параметры "`привязываются"' (binding to) к образцам, т.е. $x$ привязывается к первому элементу, а $xs$ к остальной части списка. Если сопоставление прошло успешно, то вычисляется текущая правая часть и возвращается результат. Если сопоставление не прошло успешно, то проверяется следующее уравнение. Если же ни одна левая часть не подошла к аргументу, то это приводит к ошибочной ситуации.\\

Определение функций с использованием сопоставления с образцом часто применяется в \has, так что программист должен изучить различные варианты. Мы вернёмся к этому в главе 4.\\

Функция $length$ является примером полиморфной функции. Она может быть применена к любому гомогенному списку, например $[Integer],[Char],[[Integer]]$:
\begin{figure}[ht]
\DHSp
\label{fig_fun2}
\begin{tabular}{lcl}
\GrT{$length\ [1,2,3]$} & $\Rightarrow$ & $3$\\
\GrT{$length\ ['a','b','c']$} & $\Rightarrow$ & $3$\\
\GrT{$length\ [[1],[2],[3]]$} & $\Rightarrow$ & $3$\\
\end{tabular}
\end{figure}

Приведём пример двух часто используемых функций, работающих со списками: $head$ возвращает первый элемент списка (голову), а $tail$ - всё остальное (хвост).\\
\begin{figure}[ht]
\DHSp
\label{fig_fun3}
\begin{tabular}{lcl}
\GrT{$head$} & $::$ & $[a] -> a$\\
\GrT{$head\ (x:xs)$} & $=$ & $x$\\
\\
\GrT{$tail$} & $::$ & $[a] -> a$\\
\GrT{$tail\ (x:xs)$} & $=$ & $xs$\\
\end{tabular}
\end{figure}

В отличии от функции $length$, эти функции не определены для всех возможных аргументов. При вызове функции с пустым списком происходит ошибка (времени выполнения).\\

В случае с полиморфными типами, некоторые типы более "`универсальны"', чем другие: тип $[a]$ определён для большего числа типов, чем, допустим, $[Char]$. Другими словами, первый тип может быть производныи, с помощью подставновки, от первого. В \has система типов имеет два основных свойства: во-первых, любое правильно типизированное выражение гарантированно имеет основной тип (principal type)\footnote{Объяснение даётся далее}; во-вторых, основной тип может быть выведен (be inferred) автоматически (\verb|§| 4.1.3). В сравнении с мономорфнно типизированными языками (такими как С) полиморфизм повышает т.н. "`описательную легкость"' (expressiveness), а выведение типов облегчает работу программиста.\\

	Основной тип выражения или функции это наименее общий (least general) тип, который "`отвечает всем экземплярам выражения"'. Например, основным тип для $head$ является $[a]->a;\ [b]->a,a->a$, и даже $a$ является корректным типом, но он очень универсален. А $[Integer]->Integer$ является слишком специфичным. Существование основоного типа является отличительной чертой \textit{системы типов Хиндли-Милнера} (Hindley-Milner type system), которая образует базовую систему типов \has, ML, Miranda\footnote{"`Miranda"' является торговой маркой Research Softwate, Ltd}, и некоторых других (главным образом, функциональных) языков.\\

\subsection{Пользовательские типы}
В \has мы можем определять свои собственные типы используя объявления \code{data}. Приведём несколько примеров (\verb|§|4.2.1).

Важным преопределённым типом \has является \code{Bool}:
\begin{center}
\code{data\ Bool\ =\ False\ |\ True}
\end{center}

Тип, определённый здесь имеет два значения: \code{True} и \code{False}. Тип \code{Bool} является примером пустого (nullary) \textit{конструктора типов} (type constructor), а \code{True} и \code{False} являются примерами двух пустых \textit{конструкторов данных} (data constructors). Последние называют просто \textit{конструкторами} (constructors).\\

Точно так же, мы можем определить тип \code{Color}:
\begin{center}
\code{data\ Color\ = Red\ |\ Green\ |\ Blue\ |\ Indigo\ |\ Violet}
\end{center}

И \code{Bool}, и \code{Color} являются примерами перечисляемых типов, так как состоят из пустых конструкторов данных.\\

Приведём пример типа с одним конструктором данных:
\begin{center}
\code{data\ Point\ a\ =\ Pt\ a\ a}
\end{center}

Из-за наличия одного конструктора, такой тип часто называют \textit{тип-кортеж}\footnote{Кортежи являются чем-то вроде структур из других языков программирования} (tuple type), так как это, по сути, Декартово произведение (в данном случае - двух аргументов) других типов. В противоположность этому, типы с многочисленными конструкторами, такие как \code{Bool} и \code{Color} называют (неперекрывающимися) объеденениями или суммами типов.\\

Более интересно то, что \code{Point} является примером полиморфного типа: для любого типа $t$ оно определяет точку на Декартовой плоскости, которая использует $t$ в качестве типа координат. Тип \code{Point} имеет унарный конструктор типа, так как для любого $t$ он конструирует новый тип \code{Point t}. (Таким образом, \code{[]} является конструктором типа. Для любого типа $t$ он конструирует новый тип $[t]$. Синтаксис \has позволяет записать \code{[] t} как $[t]$. Точно так же, $->$ является конструктором типа: для любых типов $t$ и $u$ конструируется тип $t->u$ - тип функции отображающей аргумент типа $t$ в $u$.)

Обратите внимание, что типом бинарного конструктора данных \code{Pt} является \code{a->a->Point\ a}, а значит следующие типы валидны:

\begin{figure}[ht]
\DHSp
\label{fig_fun4}
\begin{tabular}{lcl}
\GrT{\code{Pt\ 2.0\ 3.0}} & $::$ & \code{Point\ Float}\\
\GrT{\code{Pt\ 'a'\ 'b'}} & $::$ & \code{Point\ Char}\\
\GrT{\code{Pt\ True\ False}} & $::$ & \code{Point\ Bool}\\
\end{tabular}
\end{figure}
Выражения, такие как \code{Pt\ 'a'\ 1} не являются верными, так как \code{'a'} и \code{1} имеют разные типы.\\

Очень важно отличать \textit{конструктор данных}, который создаёт \textit{значение} от \textit{конструктора тип}, который создаёт \textit{тип}. Первые работают во время выполнения, когда мы вычисляем что-либо, в то время, как последние работают во время компиляции для обеспечения типобезопасности.\\

[Конструкторы типов, такие как \code{Point}, а конструкторы данных, такие как \code{Pt} находятся в различных пространствах имён (namespaces). Это означает, что можно давать им  одинаковые имена:
\begin{center}
\code{data\ Point\ a\ =\ Point\ a\ a}
\end{center}
На первый взгляд это мешает, но это служит для того, чтобы связь между типом и его конструктором данных чувствовалась лучше.
]

\subsection{Рекурсивные типы}
Типы могут быть рекурсивными, например в случае бинарных деревьев:
\code{data\ Tree\ a\ =\ Leaf\ a\ |\ Branch\ (Tree\ a)\ (Tree\ a)}
Мы определили полиморфный тип бинарного дерева, элементами которого являются либо листья, т.е. узлы содержащие значения типа $a$, либо внутренние узлы (ветви), содержащие (рекурсивно) два поддерева.\\

Когда вы видите объявления данных такого вида, вспомните, что \code{Tree} является конструктором типа, в то время как \code{Branch} и \code{Leaf} являются конструкторами данных. Помимо создания связи между этими конструкторами, вышеприведённое определение создают следующие типы для \code{Branch} и \code{Leaf}: 
\begin{center}
\code{Branch\ ::\ Tree\ a\ ->\ Tree\ a\ ->\ Tree\ a}\\
\code{Leaf\ ::\ a\ ->\ Tree\ a}\\
\end{center}
В этом примере мы создали достаточно сложный тип, который позволяет нам написать рекурсивные функции, использующие его. Например, представьте, что нам необходимо создать функцию \code{fringe}\footnote{Граница или кайма - \trans}, которая вернёт список листьев (слева на право). Обычно сначала полезно  описать тип функции. Видно, что типом является \code{Tree\ a\ ->\ [a]}, т.е. \code{fringe} - есть полиморфная функция, которая для любого типа $a$ отображает деревья из $a$ в список из $a$. Сразу же следует естественное объявление:

\begin{figure}[ht]
\DHSp
\label{fig_fringe}
\begin{tabular}{lcl}
\GrT{\code{fringe}} & $::$ & \code{Tree\ a\ a-> [a]}\\
\GrT{\code{fringe\ (Leaf\ x)}} & $=$ & \code{[x]}\\
\GrT{\code{fringe\ (Branch\ left\ right)}} & $=$ & \code{fringe\ left\ ++\ fringe\ right}\\
\end{tabular}
\end{figure}

Здесь $++$ является инфиксным оператором, который соединяет два списка (его полноценное описание будет дано в разделе 9.1). Как и в примере с \code{length}, функция \code{fringe} определена с использованием сопоставления с образцом. Единственная разница заключается в том, что здесь используется сопоставление с образцом определённых пользователем конструкторов: \code{Leaf} и \code{Branch}.

[Формальные параметры легко отличить, так как они записаны со строчной буквы]

\subsection{Синонимы типа}
Для удобства \has имеет способ определения \textit{синонимов типа}, т.е. имён, которые используются в качестве идентификаторов типа. Они создаются с помощью декларации \code{type} (\verb|§|4.2.2). Вот несколько примеров:

\begin{figure}[ht]
\DHSp
\label{fig_typesin}
\begin{tabular}{lcl}
\GrT{\code{type\ String}} & $=$ & \code{[Char]}\\
\GrT{\code{type\ Person}} & $=$ & \code{(Name,Address)}\\
\GrT{\code{type\ Name}} & $=$ & \code{String}\\
\GrT{\code{type\ Address}} & $=$ & \code{None\ |\ Addr\ String}\\
\end{tabular}
\end{figure}

Синонимы типа не определяют (создают) новые типы, они просто задают новые имена для уже имеющихся. Например, тип \code{Person\ ->\ Name} является точным эквивалентом \code{(String,Address)\ ->\ String}. Обычно новые имена короче исходных, но это не единственное предназначение синонимов - они могут повысить "`читабельность"' программ. Вышеприведённые примеры хорошо показывают это. Мы можем дать новые имена даже полиморфным типам:
\begin{center}
\code{type\ AssocList\ a\ b\ =\ [(a,b)]}
\end{center}

Это тип "`ассоциативного списка"', который "`соединяет"' значения типа $a$ со значениями типа $b$.

% название???
\subsection{Встроенные типы - не исключение}
Выше мы рассмотрели несколько "`встроенных"' типов: списки, кортежи, целые, символы. Мы рассмотрели, как можно создать новые типы. Можно задать вопрос: являются ли "`встроенные"' типы чем-то особенным или специальным? Ответом будет \textit{нет}. Специальный синтаксис, используемый в некоторых примерах, был введён для удобства и для согласования с историческими  конвенциями, но не имеет каких-либо семантических следствий.\\

Интересно, как бы выглядели объявления типов для этих встроенных типов, если бы мы имели возможность использовать специальный синтаксис для их определения. Например, тип \code{Char} мог бы быть записан так:
\begin{figure}[ht]
\DHSp
\label{fig_typechar}
\begin{tabular}{lll}
\GrT{\code{data\ Char}} & $=\ 'a'\ |\ 'b'\ |\ 'c'\ |\ \ldots$ & Это не верный\\
\GrT{} & $\ |\ 'A'\ |\ 'B'\ |\ 'C'\ |\ \ldots$ & код Haskell\\
\GrT{} & $\ |\ '1'\ |\ '2'\ |\ '3'\ |\ \ldots$ & --\\
\GrT{} & $\ldots$ & --\\
\end{tabular}
\end{figure}

Эти имена конструкторов синтаксически неверны; для того, чтобы преодолеть это, необходимо записать что-то вроде этого:
\begin{figure}[ht]
\DHSp
\label{fig_typechar2}
\begin{tabular}{lll}
\GrT{\code{data\ Char}} & $=\ Ca\ |\ Cb\ |\ Cc\ |\ \ldots$\\
\GrT{} & $\ |\ CA\ |\ CB\ |\ CC\ |\ \ldots$\\
\GrT{} & $\ |\ C1\ |\ C2\ |\ C3\ |\ \ldots$\\
\GrT{} & $\ldots$ & --\\
\end{tabular}
\end{figure}

Такие конструкторы не подходят для описания символов.\\
В любом случае, написание "`псевдо-\has "' кода таким образом помогает нам изучить специальный синтаксис. Видно, что \code{Char} является простым перечисляемым типом, содержащим большое количество пустых конструкторов. Если представлять  \code{Char} таким образом, то становится понятно, что мы можем сопоставлять их с символами (которые являются образцом) точно так же, как и с любым другим конструктором типа.\\

[В этом примере используются \textit{комментарии}. Символы \verb|--| и всё остальное до конца строки игнорируется. В \has имеются \textit{вложенные} (nested) коммнтарии, которые имеют следующий вид: \verb|{-...-}| (\verb|§| 2.2).

Можно определить тип \code{Int} (целые фиксированной точности) и \code{Integer} (целые бесконечной точности) следующим образом (с использованием псевдокода\footnote{Псевдокод не является верным исходным кодом \has! - \trans}):
\begin{center}
\code{data\ Int\ =\ -65532\ |\ \ldots\ |\ -1\ |\ 0\ |\ 1\ |\ \ldots\ |\ 65532}\\
\code{data\ Integer\ =\ \ldots\ -2\ |\ -1\ |\ 0\ |\ 1\ |\ 2\ \ldots}
\end{center}
, где -65532 и 65532 являются нижней и верхней границами для целых с фиксированной точностью в данной реализации. \code{Int} гораздо более объемное объявление, нежели \code{Char}, но оно тоже конечно! В противоположность этому, \code{Integer} записанный псевдокодом призван описать \textit{бесконечное} перечисиление.\\

Кортежи тоже легко определить таким обазом (псевдокод):

\begin{center}
\code{data\ (a,b)\ = (a,b)}\\
\code{data\ (a,b,c)\ = (a,b,c)}\\
\code{data\ (a,b,c,d)\ = (a,b,c,d)}\\
\code{$\ldots$}
\end{center}

Каждое из приведённых объявлений определяет кортеж определённой длины, в которых скобки ($\ldots$) играют роль выражения и выражения типа одновременно (контсруктора типа). Стоит отметить, что такое определение является бесконечным, что означает, что в \has можно использовать кортежи любой длины.\\

Можно легко определить и списки, которые являются рекурсивными типами (псевдокод):
\begin{center}
\code{data\ [a]\ = \ []\ |\ a\ :\ [a]}
\end{center}

Хорошо видно то, о чём мы говорили раньше: \code{[]} является пустым списком, а $:$ является инфиксным конструктором. $[1,2,3]$ должно являться эквивалентным для $1:2:3:[]$. (так как $:$ правоассоциативен.) Типом $[]$ является \code{[a]}, а типом $:$ является \code{a->[a]->[a]}.\\

[На самом деле, определение "`:"' является валидным синтаксисом - инфиксные конструкторы разрешены в объявлениях \code{data} и отличаются от инфиксных операторов (для сопоставления с образцом) тем, что они начинаются с "`:"' (достаточно и одного "`:"').]\\

К этому моменту читатель должен понимать различия между кортежами и списками. Обратите внимание на рекурсивную натуру типа списка. Он содержит любое число элементов одинакового типа. Обычный кортеж имеет нерекурсивный тип и содержит фиксированное количество элементов (возможно) различных типов. Правила типизации для списков и кортежей должны быть понятны:
\begin{itemize}
	\item Для $(e_1,e_2,\ldots ,e_n),\ n \geq 2$ типом кортежа является $(t_1,t_2,\ldots ,t_n)$, где $t_i$ является типом $e_i$
	
	\item Для $[e_1,e_2,\ldots ,e_n],\ n \geq 0$ типом списка является $[t]$, где все $e_i$ имеют одинаковый тип $t$
\end{itemize}

% list comprehensions???
% 01.07.06
\subsubsection{Составление списков и арифметические последовательности}
Как и в Lisp, списки являются одним из главных средств в \has. Специально для удобства работы с ними было добавлено достаточно "`синтаксического сахара"'. Помимо конструкторов списков, существуют так называемые "`"' (list comprehensions):
\begin{center}
\code{[\ f\ x\ |\ x\ <-\ xs\ ]}
\end{center}

Это выражение можно прочитать как "`список из всех \code{f\ x}, таких, что \code{x} берётся\footnote{Извлекается, вытягивается - \trans}(is drawn) из \code{xs}"'. Выражения типа \code{x\ <-\ xs} называют \textit{генераторами} (generators). Их может быть несколько:
\begin{center}
\code{[\ (x,y) |\ x\ <-\ xs ,\ y\ <-\ ys]}
\end{center}
Здесь мы указываем, что создаётся список из Декартова произведения двух других списков - \code{xs} и \code{ys}. Элементы выбираются так, как будто конструкторы были вложены слева направо (самый правый генератор извлекает элементы "`быстрее"'). Это означает что для \code{xs} равного $[1,2]$ и \code{ys} равного $[3,4]$ результат будет выглядеть так: \code{[(1,3),(1,4),(2,3),(2,4)]}.\\

Помимо генераторов, существуют особые выражения, названные ??? (guards). ??? накладывают ограничения на генерируемые элементы. Для примера, вот определение наиболее используемого метода сортировки:
\begin{figure}[ht]
\DHSp
\label{fig_quicksort}
\begin{tabular}{ll}
\GrT{\code{quicksort\ []}} & \code{=\ []}\\
\GrT{\code{quicksort\ (x:xs)}} & \code{= quicksort\ [y\ |\ y\ <-\ xs,\ y<x}\\
\GrT{} & \code{++\ [x]}\\
\GrT{} & \code{++\ quicksort\ [y\ |\ y\ <-\ xs,\ y>=x}\\
\end{tabular}
\end{figure}
 
Помимо этого, для поддержки списков \has имеет специальный синтаксис для \textit{арифметических последовательностей} (arithmetic sequences), который лучше всего усвоить из примера:
\begin{figure}[ht]
\DHSp
\label{fig_arithm}
\begin{tabular}{lcl}
\GrT{[1..10]} & $\Rightarrow$ & $[1,2,3,4,5,6,7,8,9,10]$\\
\GrT{[1,3..10]} & $\Rightarrow$ & $[1,3,5,7,9]$\\
\GrT{[1,3..]} & $\Rightarrow$ & $[1,3,5,7,9, \ldots\ (infinite\ sequence)$\\
\end{tabular}
\end{figure}

Арифметические последовательности будут более подробно изучены в разделе 8.2, а "`бесконечные списки"' в разделе 3.4.

\subsubsection{Строки}
Другим примером синтаксического сахара для встроенных типов являются строки: строка \code{"`hello"'} является сокращением от \code{['h','e','l','l','o']}. Конечно же, типом \code{"`hello"'} является \code{String}, где  \code{String} есть предопределённый синоним (синонимы были рассмотрены ранее):

\begin{center}
\code{type\ String\ =\ [Char]}
\end{center}

Это означает, что мы вправе использовать функции, работающие с полиморфными списками, для обработки строк. Например:
 
\begin{figure}[ht]
\DHSp
\label{fig_exam2}
\begin{tabular}{lcl}
\GrT{\code{"hello"\ ++\ "\ world"}} & $\Rightarrow$ & \code{"hello\ world"}
\end{tabular}
\end{figure}

\section{Функции}
Так как \has является функциональным языком, можно ожидать, что функции играют основную роль. В этом разделе мы рассмотрим некоторые аспекты функций в \has.\\

Во-первых, представьте себе такое определение функции, которая складывает два аргумента:
\begin{figure}[ht]
\DHSp
\label{fig_exam3}
\begin{tabular}{lcl}
\GrT{\code{add}} & $::$ & \code{Integer\ ->\ Integer\ ->\ Integer}\\
\GrT{\code{add\ x\ y}} & $=$ & \code{x\ +\ y}
\end{tabular}
\end{figure}

Это пример \textit{функции Карри}\footnote{Человека, который распространил идею таких функций звали Haskell Curry. Для того, чтобы получить не-Карри функцию, необходимо использовать кортеж:	
\begin{center}
\code{add\ (x,y)\ =\ x\ +\ y}
\end{center}
Теперь видно, что \code{add} на самом деле является функцией всего одного аргумента!
} (curried function). Вызов (application) \code{add} имеет вид \code{add\ $e_1$\ $e_2$} и эквивалентен \code{(add\ $e_1$)\ $e_2$}, так как вызовы функций левоассоциативны. Другими словами, вызов \code{add} с одним аргументом "`создаёт"' функцию\footnote{Не забывайте, что функции в \has являются "`первоклассными"' - \trans}, которая затем вызывается со вторым аргументом. Это прекрасно согласуется с типом \code{add}: \code{Integer\ ->\ Integer\ -> \ Integer}, который эквивалентен \code{Integer\ ->\ (Integer\ -> \ Integer)}\footnote{Функция принимает один \code{Integer} и возвращает функцию, принимающую один \code{Integer} и возвращающую один \code{Integer} - \trans}, т.е. $->$ правоассоциативен. Т.е. можно объявить \code{inc} с помощью использования \code{add} в таком виде:

\begin{center}
\code{inc\ =\ add\ 1}
\end{center}

Это пример \textit{частичного применения} функции Карри (partial application), и это один из способов, которым функция может быть возвращена как значение. Давайте расммотрим пример того, когда полезно передавать функция в качестве аргумента. Функция \code{map} является хорошим вариантом:
\begin{figure}[ht]
\DHSp
\label{fig_map}
\begin{tabular}{lcl}
\GrT{\code{map}} & $::$ & \code{(a->b)\ ->\ [a]\ ->\ [b]}\\
\GrT{\code{map\ f\ []}} & $=$ & \code{[]}\\
\GrT{\code{map\ f\ (x:xs)}} & $=$ & \code{f\ x\ :\ map\ f\ xs}
\end{tabular}
\end{figure}

[Аппликация функции имеет больший приоритет, чем имеет любой инфиксный оператор, а значит второе уравнение будет разобрано как \code{(f\ x)\ :\ (map\ f\ xs)}]
Функция \code{map} является полиморфной, а её тип явно отображет тот факт, что её первый аргумент является функцией. Обратите внимание на то, как сявзаны одинаковые типы $a$ и одинаковые типы $b$ (в выражении типа два вхождения каждого из них). В качестве  примера использования \code{map} увеличим все элементы списка:

\begin{center}
\code{map\ (add\ 1) [1,2,3] $\Rightarrow$ [2,3,4]}
\end{center}

Рассмотренные примеры показывают первоклассную сущность функций, которые при использовании обычно называют \textit{функциями высокого порядка}.

\subsection{Ламбда-функции}
Вместо того, чтобы использовать для определения функции уравнения, можно определить "`анонимные"' функции, которые называют "`лямбда-функциями"'. Например, функция, эквивалентная \code{inc}, может быть записана в виде \code{$\backslash$x\ ->\ x+1}. Функция, эквивалентная \code{add} записывается как \code{$\backslash$ x\ ->\ $\backslash$ y\ ->\ x+y}. Вложенные лямбда-функции можно записать и другим образом: \code{$\backslash$x\ y\ ->\ x+y}. Вообще, уравнения:


\begin{center}
\code{inc\ x\ =\ x+1}\\
\code{add\ x\ y\ =\ x+y}
\end{center}

на самом деле являются сокращенными вариантами
\begin{center}
\code{inc\ x\ =\ $\backslash$ x\ ->\ x+1}\\
\code{add\ x\ y\ =\ $\backslash$x\ y\ ->\ x+y}
\end{center}

Мы вернёмся к этому чуть позже.\\

В общем случае, если \code{x} имеет тип \code{$t_1$}, а \code{exp} имеет тип \code{$t_2$}, тогда \code{$\backslash$x->exp} имеет тип \code{$t_1->t_2$}.

\subsection{Инфиксные операторы}
Инфиксные операторы являются обычными функциями, которые можно определить с помощью уравнений. Вот пример оператора конкатенации списка:

\begin{figure}[ht]
\DHSp
\label{fig_infix}
\begin{tabular}{lcl}
\GrT{\code{(++)}} & $::$ & \code{[a]\ ->\ [a]\ ->\ [a]}\\
\GrT{\code{[]\ ++\ ys}} & $=$ & \code{ys}\\
\GrT{\code{(x:xs)\ ++\ ys}} & $=$ & \code{x\ :\ (xs++ys)}
\end{tabular}
\end{figure}
[Лексически, инфиксные операторы состоят только из "`символов"', в противоположность обычным идентификаторам, которые могут состоять из букв и цифр (\verb|§| 2.4). В \has нет префиксных операторов, кроме минуса (-), который является одновременно и инфиксным, и префиксным]

В качестве ещё одного примера инфиксного оператора, приведём оператор, используемый для \textit{композиции функций} (function composition):

\begin{figure}[ht]
\DHSp
\label{fig_infix}
\begin{tabular}{lcl}
\GrT{\code{(.)}} & $::$ & \code{(b->c)\ -> (a->b)\ ->\ (a->c)}\\
\GrT{\code{f\ .\ g}} & $=$ & \code{$\backslash$\ x\ ->\ f\ (g\ x)}
\end{tabular}
\end{figure}

\subsubsection{Секции}
Так как инфиксные операторы являются обычными функциями, необходимо иметь возможность частично применять их. В \has частичная аппликация инфиксных операторов называется \textit{секцией} (section). Например:

\begin{figure}[ht]
\DHSp
\label{fig_section}
\begin{tabular}{lcl}
\GrT{\code{(x+)}} & $\equiv$ & \code{$\backslash$y\ ->\ x+y}\\
\GrT{\code{(+y)}} & $\equiv$ & \code{$\backslash$x\ ->\ x+y}\\
\GrT{\code{(+)}} & $\equiv$ & \code{$\backslash$x\ y\ ->\ x+y}
\end{tabular}
\end{figure}

[Скобки обязательны]\\

Последний вид секции приводит инфиксный оператор к эквивалентному функциональному виду, и удобен при передачи инфиксного оператора в функцию, например так: \code{map\ (+)\ [1,2,3]} (читатель должен проверить, что это возвращает список функций!). Такая секция применяется и когда необходимо определить для функции сигнатуру типа, что было показано ранее в примерах с $(++)$ и $(.)$.\\

Теперь видно, что \code{add} определённый ранее является простым \code{(+)}, а \code{inc} это просто \code{(+1)}! Вот такие определения отлично сработают: 
\begin{center}
\code{inc\ =\ (+\ 1)}\\
\code{add\ =\ (+)}
\end{center}

Теперь у нас есть возможность привести инфиксный оператор к функциональному значению, но можно ли сделать наоборот? Да - простым заключением идентификатора в одинарные кавычки (backquots). Например, \code{x\ `add`\ y} это тоже самое, что и \code{add\ x\ y}\footnote{Обратите внимание, что \code{add} заключена не в \textit{апострофы}, т.е. \code{'f'} это символ, а \code{`f`} это инфиксный оператор. К счастью, большинство терминалов отображают различие лучше, чем данный текст.}. Некоторые функции удобнее записывать таким обазом. Допустим, предикат, определяющий, принадлежит ли элемент списку \code{elem} можно использовать так \code{x\ `elem`\ xs}. Попробуйте прочитать это вслух: "`x является элементов xs"'.\\

[Существуют особые правила, касаемо секций с префиксным/инфиксным оператором -; см. (\verb|§|3.5,\verb|§|3.4).]\\

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

\subsubsection{Объявления устойчивости}
\textit{Объявление устойчивости} (fixity declaration) может быть дано для любого инфиксного оператора или конструктора (включая и те, которые образованы из обыкновенных идентификаторов, например, \code{`elem`}). Такое объявление указывает уровень предшествования (precedence level): от 0 до 9, где 9 - наибольший возможный уровень; подразумевается, то обычная аппликация имеет 10 уровень. Существует неассоциативные и лево-, право-ассоциативные уровни. Например, Объявление устойчивости для \code{++} и \code{.} могут быть заданы так:

\begin{center}
\code{infixr\ 5\ ++}\\
\code{infixr\ 9\ .}
\end{center}

Оба объявления определяют правоассоциативность с уровнем в 5 и 9 соответсвенно. Левоассоциативность задаётся с помощью \code{infixl}, а задать неассоциативность можно с помощью \code{infix}. Имеется возможность задавать устойчивость сразу нескольких операторов/конструкторов. По умолчанию, задётся 9 уровень устойчивости. (см. \verb|§|5.9)

\subsection{Нестрогие функции}
Представьте, что функция \code{bot} определна следующим образом:
\begin{center}
\code{bot\ =\ bot}
\end{center}

Другими словами, \code{bot} является незавершающимся выражением (non-terminating expression). Мы обозначаем \textit{значение} незавершающегося выражения как $\bot$ (произносится "`основание"' (bottom)). Выражения, которые приводят к ошибке времени выполнения (например, \code{1/0}) имеют это значение. Такая ошибка является невосстановимой (non-recoverable): программа не может продолжить выполнение. Ошибки системы ввода-вывода, такие как EOF, явлются восстановимыми и обрабатываются другим образом (Вообще-то, такая ошибка I/O не является "`ошибкой"', а скорее исключение. Более подробно об этом - в разделе 7.)\\

Функция \code{f} называется \textit{строгой}, если при аппликации к незавершающемуся выражению, она тоже не завершается. Другими словами, $f$ является строгой, если значением \code{f\ bot} является $bot$. В большинстве языков программирования, \textit{все} функции являются строгими. Но это не так в \has. Вот пример константной функции:

\begin{center}
\code{const1\ x\ =\ 1}
\end{center}

Значением \code{const1\ bot} в \has является 1. Так как \code{const1} не нуждается в аргументе, она и не пытается вычислить его, т.е. никогда не вовлекается в незавершающиеся вычисления. По этой причине, нестрогие функции часто называют "`ленивыми функциями"' (lazy functions), так как вычисляют свои аргументы "`лениво"' или "`по необходимости"'.\\

Так как ошибки и незавершающиеся значения в \has семантически равнозначны, значение \code{const1\ (1/0)} выдаёт верный ответ - 1.\\

Нестрогие функции очень полезны в различных контекстах. Главное преимущество состоит в том, что они освобождают программиста от многих проблем, связанных с порядоком вычислений. Вычислимо дорогие значения могут быть передаваться в функции без опаски: если они не потребуются, то никогда не будут вычислены. Представьте себе \textit{бесконечную} структуру данных.\\

Можно объясненить нестрогие функции так, что \has производит вычисления с помощью \textit{определений} (definitions), а не \textit{присваиваний} (assignments), как в традиционных языках программирования. Произносите объявление 

\begin{center}
\code{v\ =\ 1/0}
\end{center}
как "`объявить \code{v} как 1/0"', а не как "`вычислить 1/0 и записать результат в \code{v}"'. Только если потребуется значение \code{1/0}, возникнет ошибка деления на нуль. Само по себе, определение не влечёт за собой никаких вычислений. Программирование с помощью присваиваний требует внимательного отношения к порядку присваиваний: смысл программы сильно меняется от порядка, в котором выполняются присваивания. Работать с объявлениями, в противоположность, проще: порядок не имеет никакого значения.

\subsection{"`Бесконечные"' структуры данных}
Одно из преимуществ \has кроется в том, что конструкторы данных тоже являются нестрогими. Это не должно шокировать, так как конструкторы являются по сути просто специальным видом функций (отличительная особенность которых заключается в том, что они участвуют в сопоставлении с образцом). Например, конструктор списков (:) является нестрогим.\\

Нестрогие конструкторы разрешают определять (концептуально) \textit{бесконечные} (infinite) структур данных. Вот бесконечный список целых едениц:
%рис стр 14.

\begin{center}
\code{ones\ =\ 1\ :\ ones}
\end{center}

Более интересный пример:

\begin{center}
\code{numsFrom\ n\ =\ n\ :\ numsFrom (n+1)}
\end{center}

Т.е. \code{numFrom\ n} является бесконечным списком, начинающимся с \code{n}. Можем построить бесконечный список квадратов:

\begin{center}
\code{squares\ =\ map} ($\verb|^|2$)\ (numsfrom\ 0)
\end{center}

(Обратите внимание на использование секции; ($\verb|^|$) является инфиксным оператором возведения в степень.)\\

В конечном счете, мы извлекаем лишь конечные части списка для вычислений. В \has существует огромное количество функций, которые делают это: \code{take}, \code{takeWhile}, \code{filetr}, и т.д. \has содержит множество встроенных типов и функций - это назыают "`Стандартной Прелюдией"' (Standart Prelude). Полностью прелюдия включена в дополнение А \hasrep. Посмотрите на \code{PreludeList} - там содержится множество функция, использующих списки. Например, \code{take} удаляет первые \code{n} элементов из списка:


\begin{figure}[ht]
\DHSp
\label{fig_squares}
\begin{tabular}{lcl}
\code{take\ 5\ squares} & $\Rightarrow$ & [0,1,4,9,16]
\end{tabular}
\end{figure}

Объявление \code{ones} являет собой пример \textit{цикличного списка} (circular list). Обычно ленивые вычисления сиьно влияют на производительность, да и список может быть реализован как настоящая цикличная структура, сохраняющая память.\\

Другим примером цикличности служит функция, возвращающая последовательность чисел Фибоначчи:
\begin{center}
\code{fib\ =\ 1\ :\ 1\ :\ [a+b\ |\ (a,b)\ <-\ zip\ fib\ (tail fib)]}
\end{center}

в которой \code{zip} это стандартная функция из прелюдии, возвращающая парами элементы её двух аргументов (списков):

\begin{flushleft}
\code{zip\ (x:xs)(y:ys)\ =\ (x,y)\ :\ zip\ xs\ ys}\\
\code{zip\ xs\ ys\ =\ []}
\end{flushleft}

Обратите внимание на то, как \code{fib}, т.е. бесконечный список, определён через самого себя, как будто бы он "`гонется за своим хвостом"'. Можно представить это таким образом: см. рис. 1.\\

Другой пример применения бесконечных списков см. в разделе 4.4.\\

% название???
\subsection{Обработка ошибок}
\has имеет встроенную функцию \code{error}, которая имеет тип \code{String->a}. Это довольно странная функция: из её сигнатуры типа можно сказать, что она возвращает значения полиморфного типа, о котором ничего не известно. Более того, она не принимает аргумента с таким типом!\\

Вообще, \textit{существует} значение, которое имеют любые типы: $\bot$. Поэтому, семантически это и есть то самое значение, которое возвращает функция \code{error} (ведь все ошибки имеют $\bot$ значение). Тем не менее, можно ожидать, что нормальная реализация должна выводит сообщение об ошибке на экран. Эта функция используется, если что-то пошло не так. Например, настоящее определение \code{head} выглядит так:

\begin{figure}[ht]
\DHSp
\label{fig_squares}
\begin{tabular}{ll}
\code{head\ (x:xs)\ = \ x}\\
\GrT{\code{head\ []\ = \ error}} & $"head \verb|{| PreludeList \verb|}| :\ head\ []"$
\end{tabular}
\end{figure}

%название???
\section{Case-выражения и Сопоставление с образцом}
Ранее мы привели несколько примеров сопоставления с образцом в определении функций - например \code{length} и \code{fringe}. В этом разделе мы рассмотрим процесс сопоставления более детально (\verb|§| 3.17)\footnote{Сопоставление с образцом в \has отличается от того, что применяется в логическом программировании (Prolog); его можно рассматривать как "одностороннее сопоставление"' (one-way matching), в то время как Prolog имеет и "`двустороннее сопоставление"' (two-way matching) (через унификацию), а также бэктреккинг (backtracking)}.\\

Образцы (шаблоны) не являются "`первоклассными"' сущностями; существует лишь конечное количество их различных видов. Мы уже встречали примеры шаблонов \textit{конструкторов данных}; и \code{length}, и \code{fringe} использовали такие шаблоны: первая - в конструкторе "`встроенного"' типа (списка), вторая - в пользовательском типе (\code{Tree}). Сопоставление разрешено в конструкторах любых типов(пользовательских, или нет): кортежи, строки, числа, символы и т.д. могут быть использованы. Вот пример функции \code{contrived}\footnote{Её название переводится как "`сложная"' или "`хитрая"' и говорит само за себя - \trans}, которая сопоставляется с кортежом констант:

\begin{center}
\code{contrived\ ::\ ([a],\ Char,\ (Int,\ Float),\ String,\ Bool)\ ->\ Bool}\\
\code{contrived\ ([],\ 'b',\ (1,\ 2.0),\ "hi",\ True)\ =\ False}
\end{center}

В этом примере встречается \textit{вложенные} (nested patterns) шаблоны (разрешены любой глубины вложенности).\\

Говоря техническим языком, \textit{формальные параметры}\footnote{\hasrep называет их "`переменными"'} тоже являются шаблонами - просто они \textit{всегда сопоставляются со значением} (never fail to match a value). В качестве "`побочного эффекта"' успешной подстановки, формальные параметры привязываются к значениям. По этой причине, шаблоны в любом уравнении не должны иметь более одного вхождения одинакового формального параметра (свойство, называемой \textit{линейностью} (linearity) \verb|§|3.17, \verb|§|3.3, \verb|§|4.4.2).\\

Шаблоны, формальные параметры которых всегда сопоставляются, называются \textit{неопровержимыми} (irrefutable), в противоположность \textit{опровержимым} (refutable). Шаблон из \code{contrived} является опровержимым. Существует 3 типа неопровержимых шаблонов, два из которых мы рассмотрим сейчас (остальной подождёт до раздела 4.4).\\

%02.07.06
\textbf{As-Шаблоны.} Иногда удобно дать имя шаблону для того, чтобы использоавть его справа от знака равенства. Например, можно написать функцию, которая дублирует первый элемент списка так:
\begin{center}
\code{f(x:xs)\ =\ x:x:xs}
\end{center}

(Вспомните, что "`:"' правоассоциативен.)Обратите внимание на то, что \code{x:xs} присутсвует с двух сторон. Можно написать \code{x:xs} всего один раз для улучшения кода: \footnote{Помимо этого, некоторые реализации \has могут работать эффективнее}.

\begin{center}
\code{f\ s@(x:xs)\ =\ x:s}
\end{center}

Такой шаблон всегда приводит к успешному сопоставлению, а его "`под-шаблон"' (в нашем случае это \code{x:xs}), конечно же, может и не приводить.\\

\textbf{Подчеркивания.} Часто случается, что мы проводим сопоставление для значения, которое нас на самом деле не интересует. Для примера: функции \code{head} и \code{tail} из раздела 2.1 можно записать следующим образом:\\

\code{head\ (x:} $\verb|_|$ \code{)\ =\ x}\\
\code{tail} $(\verb|_|$ \code{:xs)\ =\ xs} 

в котором мы "`указываем"', что нас не волнуют определённые части. Каждое подчеркивание отдельно сопоставляется хоть с чем, но в отличии от формального параметра, оно ни с чем не связывается. По этому, их может быть несколько в одном уравнении.

\subsection{Семантика сопоставления с образцом}
Мы обсудили то, как происходит сопоставление, что такое опровержимые шаблоны, что такое неопровержимые... Но мы до сих пор не знаем, \textit{как} происходит сопоставление. В каком порядке происходит связь? Что происходит, если процесс не завершился успешно? Этот раздел призван объяснить всё это.\\

Сопоставление с образцом может произойти \textit{успешно} (succeed) , \textit{неуспешно} (fail) или \textit{дивергировать} (diverge). Успешное сопоставление связывает формальные параметры. Дивергенция возникает, если значение, требуемое образцу, содержит ошибку ($\bot$). Сам процесс сопоставления проходит "`сверху вниз, слева направо"'. Неуспешное сопоставление в любой части шаблона приводит к неуспешному сопоставлению всего шаблона, а значит проверяется следующее выражение. Если все уравнения прошли процесс сопоставления неуспешно, то значение пааликации функции равно $\bot$, что приводит к ошибке времени выполнения.\\

Например, $[1,2]$ проходит сопоставление с $[0,bot]$: еденица не может быть сопоставлена с нулём, а значит результат - неуспешное сопоставление. (Вспомните, что $bot$, определённая ранее, является переменной, связанной с $\bot$.) Но если $[1,2]$ сопоставляется с $[bot,0]$, то сравнение 1 с $bot$ приводит к дивергенции (т.е. $\bot$).\\

Шаблоны высшего уровня (top-level) могут иметь \textit{гарды} ???, как в этом определении функции, которая возвращает знак числа:

\begin{figure}[ht]
\DHSp
\label{fig_signum}
\begin{tabular}{ll}
\GrT{\code{sign\ x }} & \code{|\ x\ >\ 0\ =\ 1}\\
\GrT{\code{}} & \code{|\ x\ ==\ 0\ =\ 0}\\
\GrT{\code{}} & \code{|\ x\ <\ 0\ =\ -1}\\
\end{tabular}
\end{figure}

Обратите внимание, что для одного шаблона может быть приведено несколько гардов ???. Как и с шаблонами, они сканируются сверху вниз, слева направо.

\subsection{Пример}
Сопоставление с образцом порой может являться подводным камнем для функций. Например, представьте себе функцию \code{take}:
\begin{figure}[ht]
\DHSp
\label{fig_take}
\begin{tabular}{llcl}
\GrT{\code{take0}} & $0\ \verb|_|\ $ & $=$ & \code{\ []}\\
\GrT{\code{take0}} & $\verb|_|\ []$ & $=$ & \code{\ []}\\
\GrT{\code{take0}} & $\ n\ (x:xs)$ & $=$ & \code{x\ : \ take\ (n-1)\ xs}
\end{tabular}
\end{figure}

а вот её немного изменённая версия:
\begin{figure}[ht]
\DHSp
\label{fig_take2}
\begin{tabular}{llcl}
\GrT{\code{take1}} & $\verb|_|\ []$ & $=$ & \code{\ []}\\
\GrT{\code{take1}} & $0\ \verb|_|\ $ & $=$ & \code{\ []}\\
\GrT{\code{take1}} & $\ n\ (x:xs)$ & $=$ & \code{x\ : \ take\ (n-1)\ xs}
\end{tabular}
\end{figure}

А теперь посмотрите на это:
\begin{center}
\code{take0\ 0\ bot} $\Rightarrow\ []$\\
\code{take1\ 0\ bot} $\Rightarrow\ \bot$\\
\end{center}

\begin{center}
\code{take0\ bot\ []} $\Rightarrow\ \bot$\\
\code{take1\ bot\ []} $\Rightarrow\ []$\\
\end{center}

Видно, что \code{take0} объявлена "`лучше"' по отношению к своему второму аргументу, а \code{take1} - наоборот. Трудно сказать, какое определение лучше. Просто помните, что это так. (Стандартная Прелюдия включает \code{take}.)

\subsection{Case-выражения}
Сопоставление с образцом является т.н. "`диспетчеризацией"' основанной на структурных свойствах значений. Обычно мы не хотим определять \textit{функцию} каждый раз, когда нам необходимо ветвление. Тем не менее, мы привели лишь этот способ. В \has существуют case-выражения, способные решить эту проблему. На самом деле в \hasrep сопоставление с образцом объясняется через case-выражения, которые считаются более простыми. Вообще, определение функции следующего вида:

\begin{center}
$f\ p_{11}\ \ldots\ p_{1k}\ =\ e_1$\\
$\ldots$\\
$f\ p_{n1}\ \ldots\ p_{nk}\ =\ e_n$
\end{center}

,где $p_{ij}$ является шаблоном, семантически эквивалентно:

\begin{center}

\end{center}

\begin{figure}[ht]
\DHSp
\label{fig_caseexp1}
\begin{tabular}{ll}
\GrT{\code{f\ x1\ x2\ ...\ xk\ =\ case\ (x1,\ ...,\ xk)\ of}} & $\ (p_{11},\ \ldots,\ p_{1k})\ ->\ e_1$\\

\GrT{} & $\ldots$\\
\GrT{} & $\ (p_{n1},\ \ldots,\ p_{nk})\ ->\ e_n$
\end{tabular}
\end{figure}

,где \code{xi} - новые идентификаторы. (Больше деталей, включая гарды???, приведено в \verb|§|4.4.2.) Например, определение \code{take0}, приведённое выше, эквивалентно следующему:
\begin{figure}[ht]
\DHSp
\label{fig_take3}
\begin{tabular}{llll}
\GrT{\code{take\ m\ ys}} & \code{=\ case\ (m,ys)\ of}\\
\GrT{\code{}} & $(0, \verb|_|)\ $ & $->$ & \code{\ []}\\
\GrT{\code{}} & $(\verb|_|, [])\ $ & $->$ & \code{\ []}\\
\GrT{\code{}} & \code{(n,x:xs)\ } & $->$ & \code{\ x\ :\ take\ (n-1)\ xs}\\
\end{tabular}
\end{figure}

Мы не говорили ранее, что для типобезопасности все типы правых частей case-выражений или уравнений (определяющих функцию) должны быть одинаковыми; если быть более точным - они должны иметь одинаковый основной тип.\\

Правила сопоставления для case-выражений такие же, как и в определениях функций, так что здесь нет ничего особенного (кроме синтаксиса case-выражений). Существует особенный вид case-выражений, которые используются повсеместно: \textit{условные выражения} (conditional expressions). В \has условные выражения имеют общеизвестную форму:
\begin{center}
\code{if\ } $e_1$ \code{then} $e_2\ $ \code{else\ } $e_3$
\end{center}

которые на самом деле являются сокращением следующего case-выражения:
\begin{figure}[ht]
\DHSp
\label{fig_case2}
\begin{tabular}{lcl}
\GrT{\code{case\ } $e_1$ \code{of\ }} & $True$ & $->\ e_2$\\
\GrT{\code{}} & $False$ & $->\ e_3$
\end{tabular}
\end{figure}

Хорошо видно, что $e_1$ должно иметь тип \code{Bool}, а $e_2$ и $e_3$ должны иметь одинаковые типы (но могут быть произвольными). Другими словами, если рассматривать \code{if-then-else} как функцию, имеет следующий тип: \code{Bool->a->a->a}.

\subsection{Ленивые образцы (шаблоны)}
%??? спросить
В \has сущесвует ещё один тип шаблонов. Им дано название \textit{ленивые шаблоны} (lazy patterns) и они имеют следующий вид: $~pat$. Такие шаблоны являются неопровержимыми: если значение $v$ сопоставляется с $~pat$, то сопоставление проходит успешно независимо от $pat$. Если идентификатор в $pat$ позже "`используется"' в правой части, он будет привязан либо к $pat$, либо к $\bot$, если сопоставление прошло неуспешно.\\

Ленивые шаблоны используются если структуры данных определены рекурсивно. Например, бесконечные спиския являются иделаьной основой для написания \textit{симуляторов} (simulation programs) и в этом контексте бесконечные списки обычно называют \textit{потоками} (streams). Представьте, что мы хотим смоделировать простейшее взаимодействие между серверным процессом (\code{server}) и клиентским процессом (\code{client}),где  \code{client} шлёт \textit{запрос} (request) к \code{server}, а \code{server} отвечает на каждый запрос определённым \textit{откликом} (response). Такое взаимодействие показано на рис.2. (Учтите, что \code{client} принимает инициализируещее сообщение в качестве аргумента.) Вот соответствующий код: 

%рис2

\begin{figure}[ht]
\DHSp
\label{fig_clientserver}
\begin{tabular}{ll}
\GrT{\code{reqs}}  & \code{=\ client\ init\ resps}\\
\GrT{\code{resps}} & \code{=\ server\ reqs}
\end{tabular}
\end{figure}

Эти рекурсивные уравнения являются прямым отображением рисунка.\\

Давайте предположим, что структура клиента и сервера выглядит примерно так:\\
\begin{figure}[ht]
\DHSp
\label{fig_clientserver}
\begin{tabular}{ll}
\GrT{\code{client\ init\ (resp:resps)}} & \code{=\ init\ :\ client\ (next\ resp)\ resps}\\
\GrT{\code{server\ (req:reqs)}} & \code{=\ process\ req\ :\ server\ reqs}
\end{tabular}
\end{figure}

Предполагается, что \code{next} это функция, которая по отклику сервера вычисляет следующий запрос, а \code{process} это функция, которая обрабатывает запрос клиента и вычисляет соответствующий отклик.\\

%???
К сожалению, эта программа имеет огромную проблему: она не будет работать! Проблема заключается в том, что \code{client}, как показано в рекурсивном определении \code{reqs} и \code{resps}, пытается произвести сопоставление со списком отклика до того как отправит первый запрос! Другими словами, сопоставление "`производится слишком рано"'. Конечно, можно переопределить \code{client} следующим образом:
\begin{center}
\code{client\ init\ resps\ =\ init\ :\ client\ (next\ (head\ resps))\ (tail\ resps)}
\end{center}

%03.07.06
Хотя это и работает, но такая запись читается гораздо хуже. Вместо этого можно использовать ленивый шаблон:
\begin{center}
\code{client\ init\ ~(resp:resps)\ =\ init\ :\ client\ (next\ resp)\ resps}
\end{center}

Так как ленивые шаблоны являются неопровержимыми, сопоставление произойдёт сразу же, позволяя начальному запросу быть "`отправленным"', что в свою очередь генерирует первый ответ. Система "`завязана"' и рекурсия сделает всё остальное.\\

Чтобы показать работу программы, можно определить:
\begin{figure}[ht]
\DHSp
\label{fig_clientserver2}
\begin{tabular}{ll}
\GrT{\code{init}} & \code{=\ 0}\\
\GrT{\code{next\ resp}} & \code{=\ resp}\\
\GrT{\code{process\ req}} & \code{=\ req+1}
\end{tabular}
\end{figure}

Затем мы получаем:
\begin{center}
\code{take\ 10\ reqs\ } $\Rightarrow\ [0,1,2,3,4,5,6,7,8,9]$ 
\end{center}

Мы можем использовать ленивые шаблоны и для объявления чисел Фибоначчи. Вот старый вариант:
\begin{center}
\code{fib\ =\ 1\ :\ 1\ :\ [\ a+b\ |\ (a,b)\ <-\ zip\ fib\ (tail\ fib)\ ]}
\end{center}

А вот новый:
\begin{center}
\code{fib@(1:tfib)\ =\ 1\ :\ 1\ :\ [\ a+b\ |\ (a,b)\ <-\ zip\ fib\ tfib\ ]}
\end{center}

Эта версия \code{fib} имеет одно (небольшое) преимущество, которое заключается в том, что она не использует \code{tail} в правой части, так как он находится в разрушенном (destructed) виде слева (в качестве \code{tfib}).\\

[Такой тип уравнений называется \textit{привязкой шаблона} (pattern binding), так как это уравнение высшего уровня, в котором вся левая часть является шаблоном, т.е. и \code{fib}, и \code{tfib} связываютсся в области видимости этого объявления.]\\

Принимая во внимание наши доводы, мы должны считать, что программа не выводит ничего. Тем не менее, она \textit{выводит} по простой причине: в \has привязки шаблонов имеют впереди как бы неявный $~$, отражающий стандартное поведение и призванный решить некоторые проблемы, оставшиеся за рамками этого документа. Видно, что ленивые шаблоны (хотя и неявно) играют важную роль в \has.

%??? название
\subsection{Лексическая область видимости и вложенные формы}
Порой необходимо образовать в выражении вложенную область видмости. Это полезно для создания связок (bindings), которые нигде более не видимы - т.е. как бы "`блочную структуру программы"'. В \has для этого есть 2 способа:\\

\textbf{Let-выражения} (let-expressions). В качестве простого примера приведём следющее объявление:
\begin{figure}[ht]
\DHSp
\label{fig_let}
\begin{tabular}{lll}
\GrT{\code{let}} & \code{y} & \code{=\ a*b}\\
\GrT{\code{}} & \code{f\ x} & \code{=\ (x+y)/y}\\
\GrT{\code{in}} & \code{f\ c} & \code{+\ f\ d}
\end{tabular}
\end{figure}

Набор (множество) связок, созданных \code{let}-выражениями является \textit{взаимно рекурсивными} (mutually recursive) и неявно ленивыми (т.е. имеют неявный $~$ в начале). В определениях \code{let}-выражений разрешены только \textit{сигнатуры типов} (type signatures), \textit{связки функций} (function bindings), \textit{привязки шаблонов} (pattern bindings).\\

\textbf{Where-выражения} (where clauses). Иногда удобно использовать гарды??? для связок. Для этого можно применить \textit{Where-выражение}:
\begin{figure}[ht]
\DHSp
\label{fig_where}
\begin{tabular}{llll}
\GrT{\code{f\ x\ y}} & \code{|\ y>z} & \code{=} & $\ldots$\\
\GrT{\code{}} & \code{|\ y==z} & \code{=} & $\ldots$\\
\GrT{\code{}} & \code{|\ y<z} & \code{=} & $\ldots$\\
\GrT{\code{}} & \code{where\ z} & \code{=} & \code{x*x}
\end{tabular}
\end{figure}

Обратите внимание, что так нельзя делать с помощью \code{let}-выражений, которые видимы только из выражений, которые оно включает. \code{where}-выражения разрешены только на высшем уровне набора уравнений или \code{case}-выражений. Они обладают такими же свойствами и ограничениями, как и \code{let}-выражения.\\

Эти две формы вложенной области видимости очень похожи, но помните, что \code{let}-выражения являются полноценными выражениями, а \code{where}-выражения это всего лишь дополнительный синтаксис для объявления функций и \code{case}-выражений.

%название???
\subsection{Разметка}
Читатель должно быть давно задётся вопросом, как \has обходится без точки с запятой (или другого типа разделителей) для обозначения окончания уравнения, объявления и т.д. Например, посмотрите на \code{let}-выражение из последнего раздела:
\begin{figure}[ht]
\DHSp
\label{fig_let}
\begin{tabular}{lll}
\GrT{\code{let}} & \code{y} & \code{=\ a*b}\\
\GrT{\code{}} & \code{f\ x} & \code{=\ (x+y)/y}\\
\GrT{\code{in}} & \code{f\ c} & \code{+\ f\ d}
\end{tabular}
\end{figure}

Почему же разборщик не понимает это как:
\begin{figure}[ht]
\DHSp
\label{fig_let2}
\begin{tabular}{lll}
\GrT{\code{let}} & \code{y} & \code{=\ a*b\ f}\\
\GrT{\code{}} & \code{x} & \code{=\ (x+y)/y}\\
\GrT{\code{in}} & \code{f\ c} & \code{+\ f\ d}
\end{tabular}
\end{figure}
?\\
Ответ заключается в том, что \has использует двухмерный вид синтаксиса, называемый \textit{разметкой} (layout), который основан на том, что объявления "`расположены в несколько колонок"'. В предыдущем примере \code{y} и \code{f} находятся в одной колонке. Правила разметки обсуждаются в \hasrep (\verb|§|2.7,\verb|§|B.3), но вообще они обычно усваиваются с помощью практики. Просто запомните:\\

Во-первых, следующий символ, идущий за \code{where,let,of} открывает объявление этих конструкций и определяет начальную колонку (это относится и к \code{where} в объявлениях классов и экземпляров, о которых идёт речь в разделе 5). Таким образом, мы можем начинать объявление на этой же строке с ключевого слова (keyword), символа новой строки, и т.д. (\code{do}, рассматриваемое далее, тоже использует разметку)\\

Во-вторых, всегда проверяйте, находится ли первая колонка текущего уровня вложенности правее первой колонки его окружения (иначе возникнет двусмысленность). "`Окончание"' объявления происходит, когда что-то встречается с тем же отступом (или находится левее)\footnote{\has использует соглашение, что табуляция состоит из 8 пробелов, поэтому будьте внимательны со своим редактором, который может иметь другое соглашение}.\\

"`Разметка"' это сокращение от \textit{явного} механизма группировки, который заслуживает внимания, так как в некоторых случаях является очень полезным. Пример с \code{let} эквивалентен следующему:
\begin{figure}[ht]
\DHSp
\label{fig_let3}
\begin{tabular}{lll}
\GrT{\code{let}} & $\verb|{|\ y$ & \code{=\ a*b}\\
\GrT{\code{}} & \code{;\ f\ x} & \code{=\ (x+y)/y}\\
\GrT{\code{}} & $\verb|}|$  & \code{}\\
\GrT{\code{in}} & \code{f\ c} & \code{+\ f\ d}
\end{tabular}
\end{figure}

Обратите внимание на фигурные скобки и точку с запятой. Можно располагать несколько объявлений на одной строке, например так:
\begin{figure}[ht]
\DHSp
\label{fig_let3}
\begin{tabular}{lll}
\GrT{\code{let}} & $y$ & \code{=\ a*b;\ z\ =\ a/b}\\
\GrT{\code{}} & \code{f\ x} & \code{=\ (x+y)/z}\\
\GrT{\code{in}} & \code{f\ c} & \code{+\ f\ d}
\end{tabular}
\end{figure}

Другой пример явной разметки приведён в \verb|§|2.7.\\

Разметка такого типа сильно уменьшает "`синтаксический мусор"', а значит улучшаяет вид кода. Её легко принять и приятно использовать.\\ 

\section{Классы типов и перегрузка}
Существует ещё одно свойство (особенность) системы типов \has, которое выделяет его от других языков программирования. Вид полиморфизма, о котором мы так много говорили, называется \textit{параметрическим} (parametric) полиморфизмом. Существует и другой вид полиморфизма, названный \textit{специальным} (ad hoc) полиморфизмом:

\begin{itemize}
	\item Литералы (например, 1 и 2) обычно отображают как целые с фиксированной точностью, так и целые с произвольной точностью.
	\item Числовые операторы (например, +) обычно работают с различными видами чисел.
	\item Оператор равенства (equality operator) (в \has это ==) обычно работает с числами и многими другими (но не со всеми) типами.
\end{itemize}

Обратите внимание, что поведение операторов (и др.) меняется от типа к типу. Иногда поведение является неопределённым (undefined behavior) или ошибочным, в то время как с параметрическим полиморфизмом тип не играет никакой роли (\code{fringe} без разницы, какой тип у элементов дерева). В \has специальный полиморфизм (или перегрузка (overloading)) основан на \textit{классах типов} (type classes).\\

Приступим с простого, но очень важного, примера: равенства. Существует огромное количество типов, для которых мы желаем определить равенство, но есть и те, для которых этого не нужно. Например, трудно представить себе сравнение функций, в то время как сравнение двух списков очень желательно\footnote{Равенство, о котором мы говорим, является "`равенством значений"', а не "равенством указателей", как в случае с оператором == из Java. Равенство указателей не имеет "ссылочной прозрачности" (referential transparency), а значит не может присутствовать в чисто функциональном языке.}. Чтобы лучше понять это, рассмотрим определение функции \code{elem}, которая проверяет список на наличие в нём определённого элемента:

\begin{figure}[ht]
\DHSp
\label{fig_elem2}
\begin{tabular}{ll}
\GrT{\code{x\ `elem`\ []}} & \code{=\ False}\\
\GrT{\code{x\ `elem`\ (y:ys)}} & \code{=\ (x==y)\ ||\ (x\ `elem`\ ys)}
\end{tabular}
\end{figure}

[Из соображений, описанных в разделе 3.1, мы описываем эту функцию в инфиксной форме. \code{==} и \code{||} являются, соответственно, оператором сравнения и логическим "`или"']\\

Как видно отсюда, тип \code{elem} "`должен быть"' такой: \code{a->[a]->Bool}. Но это означает, что \code{==} имеет тип \code{a->a->Bool}, хотя мы только что согласились, что \code{==} не должен быть объявлен для всех типов.\\

Более того, даже если бы \code{==} был объявлен для всех типов, сравнение двух списков сильно отличается от сравнения двух чисел. Поэтому ожидается, что \code{==} будет \textit{перегружен} для различных типов.\\

\textit{Класы типов}\footnote{Далее просто классы (не путать с классами ООП/ООД) - \trans} служат для этих двух целей. Они позволяют нам указать, какие типы будут являться \textit{экземплярами} (instances) каких классов, а также дают возможность нам описать перегруженные \textit{операции} (operations), связанные с классом. Например, давайте опишем класс, содержащий оператор сравнения:

\begin{center}
\code{class\ Eq\ a\ where}\\
\code{\ (==)\ ::\ a\ ->\ a\ ->\ Bool}
\end{center}

Здесь \code{Eq} является именем класса, который мы определили, а \code{==} это единственная операция класса. Можно озвучить это определение следующим образом: "`тип \code{a} является экземпляром класса \code{Eq}, если существует такая (перегруженная) операция, как \code{==} определённого вида."' (Обратите внимание на то, что \code{==} определена только для пар объектов одинакового типа.)\\

Запись \code{Eq\ a} означает, что \code{a} должен являться экземпляром класса \code{Eq}. Это означает, что \code{Eq\ a} не является типовыражением, а неким ограничением, называемым \textit{контекстом} (contex). После контекста идёт типовыражение. Например, предыдущее выражение связывает (assign) следующий тип с \code{==}:
\begin{center}
\code{(==)\ ::\ (Eq\ a)\ =>\ a\ ->\ a\ ->\ Bool}
\end{center}

Это можно озвучить так: "`Для каждого типа \code{a}, который является экземпляром класса \code{Eq}, операция \code{==} имеет тип \code{a->a->Bool}"'. Этот тип, и использовался в примере с \code{elem}. Контекст налагает ограничение, так что основной тип \code{elem} будет такой:
\begin{center}
\code{elem\ ::\ (Eq\ a)\ =>\ a\ ->\ [a]\ ->\ Bool}
\end{center}

Это звучит так: "`Для любого типа \code{a}, который является экземпляром класса \code{Eq}, функция \code{elem} имеет тип \code{a->[a]->Bool}"'.Это то, что нам и нужно - мы утверждаем, что \code{elem} определена не для всех типов, а лишь для тех, которые имеют оператор сравнения.\\

Но как указать, какие типы являются экземплярами какого класса? Для этого существуют \textit{объявления экземпляров} (instance declarations). Вот пример:

\begin{center}
\code{instance\ Eq\ Integer\ where}\\
\code{x==y\ =\ x\ `integerEq`\ y}
\end{center}

Определение \code{==} называют \textit{методом} (method). Функция \code{integerEq}, по видимому, является функцией, которая сравнивает целые числа на равенство\footnote{Это не является правильным словосочетанием, но оно хорошо прижилось в мире программиования - \trans}, но вообще возможно любое выражение в правой части (как для обычных функций). Всё объявление говорит: "`Тип \code{Integer} является экземпляром класса \code{Eq}, а вот определение метода, соответствующего \code{==}"'. Благодаря этому определению, мы можем сравнивать целые числа на равенство с помощью \code{==}. Точно так же:
\begin{center}
\code{instance\ Eq\ Float\ where}\\
\code{x==y\ =\ x\ `floatEq`\ y}
\end{center}

Что позволяет нам сравнивать и действительные числа с плавающей запятой используя \code{==}.\\

Рекурсивные типы, такие как \code{Tree}, тоже можно использовать:

\code{instance\ (Eq\ a)\ =>\ Eq\ (Tree\ a)\ where}\\

\begin{figure}[ht]
\DHSp
\label{fig_funct}
\begin{tabular}{lllll}
\GrT{\code{Leaf\ a}} & \code{==\ Leaf\ b} & \code{=\ a\ ==\ b}\\
\GrT{\code{(Branch\ l1\ r1)}} & \code{==\ (Branch\ l2\ r2)} & \code{=\ (l1==l2)} & $\verb|&&| $ & \code{(r1==r2)}\\
$\verb|_|$ & \code{==} $\verb|_| $ & \code{=\ False}
\end{tabular}
\end{figure}

Обратите внимание на контекст \code{Eq\ a} в первой строке - это необходимо, так как элементы листьев (тип - \code{a}) сравниваются во второй строке. Дополнительное ограничение erfpsdftn, что мы можем сравнивать деревья из элементов типа \code{a}, если мы можем сравнивать между собой сами элементы типа \code{a}. Если бы мы опустили контекст из объявления экземпляра, то произойдёт ошибка типизации.\\

\hasrep, а особенно прелюдия включает огромное количество примеров классов. Например, класс \code{Eq} определён немного по-другому:

\begin{center}
\code{class\ Eq\ a\ where}\\
\code{(==),\ (/=)\ ::\ a\ ->\ a\ ->\ Bool}\\
\code{x\ /=\ y     =\ not\ (x==y)}
\end{center}

Это пример класса с двумя операциями. Он также показывает использование \textit{методов по-умолчанию} (default methods), в данном случае \code{/=}. Если метод для конкретной операции опущен в объявлении экземпляра, то используется метод по-умолчанию, объявленный в объявлении класса (если доступен). Для примера, три экземпляра \code{Eq}, объявленные выше, будут отлично работать с вышеприведённым определением класса, в том числе и операция неравенства \code{/=}, которая просто является логическим отрицанием равенства.\\

\has поддерживает и \textit{расширение классов} (class extension). Доустим, нам нужно объявить класс \code{Ord}, который \textit{наследует} (inherits) все операции класса \code{Eq} и имеет дополнительный набор операций сравнения и функции нахождения минимума и максимума:

\begin{figure}[ht]
\DHSp
\label{fig_eq}
\begin{tabular}{ll}
\GrT{\code{class\ (Eq\ a)\ =>\ Ord\ a\ where}}\\
\GrT{\code{(<),\ (<=),\ (>=),\ (>)}} & \code{::\ a\ ->\ a\ ->\ Bool}\\
\GrT{\code{max,\ min}} & \code{::\ a\ ->\ a\ ->\ a}
\end{tabular}
\end{figure}

Обратите внимание на контекст в декларации класса. \code{Eq} является \textit{суперклассом} (superclass) класса \code{Ord} (соответсвенно, \code{Ord} является \textit{подклассом} (subclass) класса \code{Eq}), и любой тип, являющийся экземпляром \code{Ord} должен являться экземпляром \code{Eq}. (В следующем разделе мы дадим более полноценное определение \code{Ord}, взятое из прелюдии.)\\

Одним из плюсов такого подхода является более короткий контекст: типовыражение для функции, которая требует операции из \code{Eq} и \code{Ord} может использовать лишь контекст \code{(Ord\ a)}, а не \code{(Eq\ a,\ Ord\ a)}, так как \code{Ord} "`подразумевает"' \code{Eq}. Важнее то, что методы для операций подкласса могут быть уверены в существовании методов для операций суперкласса. Например, в прелюдии для \code{Ord} определён метод по-умолчанию для (<):
\begin{center}
\code{x<y\ =\ x\ <=\ y} $\verb|&&|$ \code{x\ /=\ y}
\end{center}

В качестве примера использования \code{Ord} рассмотрим на основной тип функции \code{quicksort} из раздела 2.4.1:

\begin{center}
\code{quicksort\ ::\ (Ord\ a)\ =>\ [a]\ ->\ [a]}
\end{center}


Другими словами, \code{quicksort} оперирует только со списками из элементов, которые могут быть упорядочены.\\

В \has также разрешено \textit{множественное наследование} (multiple inheritance), т.е. класс может иметь несколько суперклассов. Вот пример:

\begin{center}
\code{class\ (Eq\ a, Show\ a)\ =>\ C\ a\ where ...}
\end{center}

Такой класс наследует операции из \code{Eq} и \code{Show}.\\

Методы класса рассматриваются как объявления высшего уровня. Они находятся в одном пространстве с обычными переменными. Одно имя не может принадлежать методу класса одновременно с переменной или другим методом другого класса.\\

В \code{data} объявлениях разрешены контексты. См. \verb|§|4.2.1.\\

Методы класса могут иметь дополнительные ограничения наложенные на любую переменную, кроме той, что описывает данный класс. Например, в следующем классе:

\begin{center}
\code{class\ C\ a\ where}\\
\code{m\ ::\ Show\ b\ =>\ a\ ->\ b}
\end{center}

метод \code{m} требует, чтобы тип \code{b} относился к классу \code{Show}. Тем не менее, метод \code{m} не может наложить никаких других ограничений на тип \code{a}. Это должно быть сделано в контексте объявления класса.\\

Мы расммотрели "`первоклассные"' типы. Например, конструктор типа \code{Tree} всегда имел аргумент, например: \code{Tree\ Integer} (дерево с \code{Integer} элементами) или \code{Tree\ a} (семейство деревьев с элементами типа \code{a}). Но сам по себе \code{Tree} является конструктором типа, а значит он принимает тип в качестве аргумента и возвращает тип в качестве результата. В \has не существует таких значений, но такие "`типы высшего уровня"' (higher-order types) могут быть использованы в объявлениях класса.\\

Начнём с примера класса \code{Functor} (взят из прелюдии):
\begin{center}
\code{class\ Functor\ f\ where}\\
\code{fmap\ ::\ (a\ ->\ b)\ ->\ f\ a\ ->\ f\ b}
\end{center}

Функция \code{fmap} очень похожа на функцию \code{map}. Обратите внимание, что переменная типа применяется к другим типам в \code{f\ a} и \code{f\ b}. Поэтому, можно ожидать, что она будет привязана к типу подобному, например, \code{Tree}, которые можно применять к аргументу. Экземпляр \code{Functor} для типа \code{Tree} будет выглядеть так: 


\begin{figure}[ht]
\DHSp
\label{fig_functor}
\begin{tabular}{ll}
\GrT{\code{instance\ Functor\ Tree\ where}}\\
\GrT{\code{fmap\ f\ (Leaf\ x)}} & \code{=\ Leaf\ (f\ x)}\\
\GrT{\code{fmap\ f\ (Branch\ t1\ t2)}} & \code{=\ Branch\ (fmap\ f\ t1)\ (fmap\ f\ t2)}
\end{tabular}
\end{figure}

Это объявление экземпляра объявляет\footnote{Тавтология автора - \trans}, что \code{Tree}, а не \code{Tree\ a}, является экземпляром \code{Functor}. Такая возможность очень полезна, а в примере использовалась для описания типов "`общих"' (generic) "`контейнеров"', позволяющих функциям (таким как \code{fmap}) работать в одном стиле с любыми деревьями, списками и другими типами.\\

[Аппликация типов пишется точно так же как и аппликация функций. Тип \code{T\ a\ b} разбирается как \code{(T\ a)\ b}. Типы, такие как кортежи, могут быть записаны с использованием другого синтаксиса (Карри???). Для функций (->) является конструктором типов; тип \code{f\ ->\ g} эквивалентен \code{(->)\ f\ g}. Точно также, типы \code{[a]} и \code{[]\ a} эквивалентны. Для кортежей \code{(,),\ (,,)...} являются конструкторами типа (как и конструктором данных).]\\

Как известно, система типов находит ошибки типизации в выражениях. А что же с ошибками в  типовыражениях? Выражение \code{(+)1\ 2\ 3} приводит к ошибке, так как \code{(+)} принимает всего два аргумента. Точно так же, тип \code{Tree\ Int\ Int} должен приводить к ошибке, так как \code{Tree} имеет всего один аргумент. Так как \has обнаруживает ошибочные типовыражения? Ответ кроется во второй системе типизации, которая проверяет типы на корректность! Каждый тип имеет соответствующий \textit{вид} (kind), от которого и зависит правильность.\\

Типовыражения подразделяются на различные \textit{виды}, которые могут принимать одну из двух следующих форм:
\begin{itemize}
	\item Символ $*$ означает, что тип связан с конкретными объектами данных. Т.е. если значение $v$ имеет тип $t$, то вид $v$ должен быть $*$.
	\item Если $k_1$ и $k_2$ являются видами, то $k_1 \rightarrow\ k_2$ это вид типов, который получает вид $k_1$ и возвращает вид $k_2$.
\end{itemize}

Конструктор типов \code{Tree} имеет вид $*\ \rightarrow\ *$; тип \code{Tree\ Int} имеет вид $*$. Все члены \code{Functor} должны иметь вид $*\ \rightarrow\ *$; произойдёт ошибка, если будет дано следующее объявление:

\code{instance\ Functor\ Integer\ where ...}
т.к. \code{Integer} имеет вид $*$.\\

Виды не присутствуют в коде программы. Компилятор автоматически (без каких-либо объявлений) выводит виды перед проверкой типов. Виды скрываются на заднем плане до тех пор, пока они не приводят к ошибкам. Виды просты настолько, что обычно компилятор может вывести достаточно полноценное сообщение об ошибке, как только она возникла. Подробности, связанные с видами, см. в \verb|§|4.1.1 и \verb|§|4.6.\\

\textbf{Другие взгляды.} Перед тем, как продолжить изучение классов, стоит рассмотреть два других взгляда на классы типов \has. Первый из них пришел из мира объектно ориентированного программирования (ООП). В следующем утверждении о ООП просто подставьте вместо \textit{классов} - \textit{классы типов}, а вместо \textit{объектов} - \textit{типы}:

\begin{quote}
"`\textit{Классы} включают общие операции. Конкретный \textit{объект} является экземпляром класса, и имеет методы, отвечающие его операциям. \textit{Классы} могут иметь иерархию, формируя связи между супер\textit{классами} и под\textit{классами}, разрешая наследование операций/методов. С операцией может быть связан метод по-умолчанию."'
\end{quote}

Должно быть понятно, что, в отличии от ООП, типы не есть объекты, и не существует понятия внутреннего изменяемого состояния (internal mutable state) типов или объектов. Преимущество \has по сравнению с ООП языками заключается в том, что методы в \has полностью типобезопасны: любая попытка применения метода к значению, тип которого имеет нужный класс, приведёт к ошибке времени компиляции, а не к ошибке времени выполнения. Другими словами, методы не  "`ищутся"' во время выполнения, а просто передаются как функции высшего порядка.\\

%???
Другой взгляд рассматривает связь между параметрическим и специальным полиморфизмом. Мы показали, как полезен параметрический полиморфизм в определении семейств типов с помощью квантификации. Иногда, тем не менее, нужен не столь "`широкий"' подход - необходимо определить лишь узкое множество типов, таких как в случае со сравнениями. Классы типов можно рассматривать как способ сделать это. Поэтому, можно считать параметрический полиморфизм (также)видом перегрузки! Просто перегрузка происходит неявно на всём множестве типов, а не на ограниченном (классе типов).\\

\textbf{Сравнение с другими языками}. Классы, используемые в \has есть тоже самое, что и в других ОО-языках (С++ и Java, например). Тем не менее, существуют и разительные отличия:

\begin{itemize}
	\item \has разделяет определение типа и определение методов, связанных с этим типом. Класс в С++ или Java обычно сразу же определяет и структуру данных (данные-члены), и функции, связанные со структурой (методы). В \has эти определения разграничены.
	\item Методы классов, определяемые в \has отвечают виртуальным функциям в С++. Каждый экземпляр класса имеет своё собственное определение каждого метода; функции по-умолчанию соответствуют виртуальной функции в базовом классе\footnote{Конечно же подразумевается неперегруженная или чистая виртуальная функция - \trans}.
	%??? implements???
	\item Классы в \has немного походят на интерфейсы в Java\footnote{Или на классы с чистыми виртуальными функциями в C++. Авторы, видимо, посчитали отсутсвие \code{implements} за недостаток С++ - \trans}. Как и определение интерфейса, объвление класса в \has определяют протокол (контракт) по взаимодействию с объектом, а не сам объект.
	\item \has не поддерживает стиль перегрузки С++, при котором функции с различными типами имеют одно имя. 
	\item Тип объекта в \has нельзя неявно приводить; не существует единого базового класса (вроде \code{Object}).
	\item Компиляторы С++ и Java формируют вспомогательные структуры (вроде виртуальной таблицы), которые существуют и во время выполнения. В \has таковая информация существует лишь на логическом уровне, а не на физическом.
	%??? блин, забыл!
	\item В \has не существует !!!ограничения доступа!!! (как то \code{public} или \code{private}). Для этого существует система модулей. 	
\end{itemize}

\section{Вновь Типы}
Давайте изучим более сложные аспекты системы типов.

\subsection{Newtype-объявление}
Обычной практикой является объявление нового типа, который идентичен уже существующему. В \has для этого служит \code{newtype}-объявление. Например, натуральные числа можно представить с помощью \code{Integer}:

\code{newtype\ Natural\ =\ MakeNatural\ Integer}
Это объявление создаёт полностью новый тип \code{Natural}, единственный конструктор которого содержит один \code{Integer}. Конструктор \code{MakeNatural} конвертирует натуральные числа в целые (и наоборот):


\begin{figure}[ht]
\label{fig_naturalnums}
\begin{tabular}{llll}
\GrT{\code{toNatural}} & \code{} & \code{::\ Integer\ ->\ Natural}\\
\GrT{\code{toNatural\ x}} & \code{|\ x\ <\ 0} & \code{=\ error\ "Can't create negative naturals!"}\\
\GrT{\code{}} & \code{|\ otherwise} & \code{=\ MakeNatural\ x}\\
\GrT{\code{}} & \code{} & \code{}\\
\GrT{\code{fromNatural}} & \code{} & \code{::\ Natural\ ->\ Integer}\\
\code{fromNatural\ (MakeNatural\ i)\ =\ i}
\end{tabular}
\end{figure}

Следующее объявление экземпляра заносит \code{Natural} в класс \code{Num}:\\
\begin{figure}[ht]
\label{fig_naturalnums}
\begin{tabular}{llll}
\code{instance\ Num\ Natural\ where}\\
\GrT{\code{fromInteger}} & \code{=\ toNatural}\\
\GrT{\code{x\ +\ y}} &\code{= \ toNatural\ (fromNatural\ x\ +\ fromNatural\ y)}\\
\GrT{\code{x\ -\ y}} &\code{=\ let\ r\ =\ fromNatural\ x\ -\ fromNatural\ y\ in}\\
\GrT{\code{}} & \code{\ if\ r\ <\ 0\ then\ error\ "Unnatural\ subtraction"}\\
\GrT{\code{}} & \code{\ else\ toNatural\ r}\\
\GrT{\code{x\ *\ y}} & \code{=\ toNatural\ (fromNatural\ x\ *\ fromNatural\ y)}\\
\end{tabular}
\end{figure}
Без этого объявления, \code{Natural} не будет являться экземпляром \code{Num}. Объявление экземпляров для старых типов не переходит к новым. Т.е. мы ввели этот тип для того, чтобы образовать ещё один экземпляр класса \code{Num}. Это было бы невозможно, если бы \code{Natural} был бы объявлен как синоним типа \code{Integer}.\\

Всё сработало с помощью \code{data} объявления, а не \code{newtype} объявления. Тем не менее, \code{data} объявление добавляет немного накладных расходов (extra overhead)(возникающих из-за ленивости), а \code{newtype} избегает их. См. раздел \verb|§|4.2.3 \hasrep, чтобы лучше разобраться в \code{newtype,\ data,\ type} объявлениях. \\

[Кроме самого названия, \code{newtype} объявления имеют такой же синтаксис, как и \code{data} объявления с одним конструктором, содержащим единственное поле. Это очень удобно, так как типы, созданные с помощью \code{newtype} практически идентичны созданным с помощью \code{data} объявлений.]\\

%4.07.06
\subsection{Метки и поля}
К полям в \has можно обращаться либо по их позиции, либо используя \textit{метки полей} (field labels). Представьте следующую структуру:
\begin{center}
\code{code\ Point\ =\ Pt\ Float\ Float}
\end{center}
Два \code{Point} являются первым и вторым аргументами для конструктора \code{Pt}. Функции на подобии таких:
\begin{figure}[ht]
\DHSp
\label{fig_pointx}
\begin{tabular}{lcl}
\GrT{\code{pointx}} & \code{::} & \code{Point\ ->\ Float}\\
\GrT{\code{pointx\ (Pt\ x}} & $\verb|_|)$ & \code{=\ x}
\end{tabular}
\end{figure}

могут быть использованы для доступа к первому компоненту, но для больших структур становится весьма проблематично писать такие функции.\\

Поэтому конструкторы в \code{data} объявлениях могут быть объявлены используя \textit{имена полей} (field names), заключенные в фигурные скобки. Такие имена "`ссылаются"' на компоненты конструктора по имени, а не по позиции. Вот другой способ определения \code{Point}:
\begin{center}
\code{data\ Point\ =\ Pt} $\verb|{|$ \code{pointx,pointy\ ::\ Float} $\verb|}|$
\end{center}
Этот тип данных абсолютно идентичен предыдущему определению \code{Point}. Конструктор \code{Pt} точно такой же. Тем не менее, последнее объявление определяет ещё и два имени: \code{pointx,\ pointy}. Такие имена могут быть использованы в качестве \textit{функции-селектора} (selector function) для доступа к компонентам. В этом примере имеется два селектора:

\begin{center}
\code{pointx\ ::\ Point\ ->\ Float}\\
\code{pointy\ ::\ Point\ ->\ Float}
\end{center}

Приведём функцию, использующую их:
\begin{figure}[ht]
\DHSp
\label{fig_selectors}
\begin{tabular}{lcll}
\GrT{\code{absPoint}} & \code{} & \code{::\ Point} & \code{->\ Float}\\
\GrT{\code{absPoint}} & \code{p} & \code{=\ sqrt} & \code{(pointx\ p\ *\ pointx\ p\ +}\\
\GrT{\code{}} & \code{} & \code{} & \code{\ pointy\ p\ *\ pointy\ p\ )}
\end{tabular}
\end{figure}

Метки полей могут быть использованы и для создания новых значений. Выражение \code{Pt} $\verb|{|$ \code{pointx=1,\ pointy=2} $\verb|}|$ идентично \code{Pt\ 1\ 2}. Использование меток при объявлении конструкторов данных не отменяет позиционного доступа: разрешены и \code{Pt} $\verb|{|$ \code{pointx=1,\ pointy=2} $\verb|}|$, и \code{Pt\ 1\ 2}. При конструировании значения с помощью имён полей, некоторые имена могут быть опущены - в этом случае они являются неопределёнными.\\

Сопоставление с образцом с помощью имён полей использует такой же синтаксис:
\begin{center}
\code{absPoint\ (Pt} $\verb|{|$ \code{pointx=x,\ pointy=y} $\verb|}|)$ \code{=\ sqrt\ (x*x\ +\ y*y)}
\end{center}

Функция обновления (update function) использует значения полей из исходной структуры для того, чтобы создать компоненты новой. Если \code{p} является \code{Point}, то \code{p} $\verb|{|$ \code{pointx=2} $\verb|}|$ это точка с таким же \code{pointy} как у \code{p}, но с \code{pointx} равным 2. Это не деструктивное обновление (destructive update): функция обновления создаёт копию объекта, заполняя поля значениями.\\

[Скобки, использованные с метками полей приведены для удобства: \has позволяет опускать скобки на основании \textit{правил разметки} (о которых шла речь в \verb|§|4.6). Тем не менее, скобки используемые с \textit{именами} полей должны явно присутствовать.]\\

%???
Имена полей не ограничены типами с единственным конструктором (такие типы обычно называются 'записями' (records)). Операции селекции или обновления (с использованием имён полей) у типов с многочисленными конструкторами могут приводить к ошибке времени выполнения). Это очень походит на поведение функции \code{head} с пустым списком в качестве аргумента.\\

%??? 
Метки полей находятся в пространстве имён высшего уровня, а значит делят его с переменными и методами классов. Метки полей не могут быть использованы более чем в одном типе данных. Тем не менее, одно имя поля может быть использовано множество раз в конструкторах одного типа данных, при условии, что во всех конструкторах оно имеет одинаковый тип:
\begin{figure}[ht]
\DHSp
\label{fig_dataconstructors}
\begin{tabular}{ll}
\GrT{\code{data\ T}} & \code{=\ С1} $\verb|{|$ \code{f\ ::\ Int,\ g\ ::\ Float} $\verb|}|$\\
\GrT{\code{}} & \code{|\ C2} $\verb|{|$ \code{f\ ::\ Int,\ h\ ::\ Bool} $\verb|}|$
\end{tabular}
\end{figure}

имя поля \code{f} используется в двух конструкторах \code{T}. Если \code{x} имеет тип \code{T}, то \code{x} $\verb|{|$ \code{f=5} $\verb|}|$ сработает для значений, сконструированных любым конструктором \code{T}.\\

Имена полей не изменяют природу алгебраических типов; они являются просто специальным синтаксисом, который облегчает доступ к компонентам структур данных. Они помогают легче использовать конструкторы с многочисленными компонентами, так как поля могут быть добавлены или удалены без изменения каждой ссылки на конструктор. Детали см. в разделе \verb|§|4.2.1.

\subsection{Строгие конструкторы данных}
Структуры данных в \has обычно являются \textit{ленивыми}: их компоненты не вычисляются до тех пор, пока в этом не будет надобности. Это разрешает структуры с элементами, которые в момент вычисления могут выдать ошибку или не смогут остановить процесс вычислений (войдут в бесконечный цикл). Ленивые структуры повышают выразительность языка и являются базовым аспектом стиля программирования \has.\\

Каждое поле ленивого объекта данных "`обёрнуто"' в структуру, которую обычно называют переходником (thunk). Переходник "`скрывает"' вычисления. Он не используется пока не требуется значение. Переходники, содержащие ошибку ($\bot$) не влияют на другие элементы структуры данных. Например, кортеж \code{('a',} $\bot )$ является абсолютно корректным значением. Значение \code{'a'} может быть использовано без затрагивания других компонентов кортежа. Напротив, большинство языков программирования являются \textit{строгими}, а не ленивыми: все компоненты структур "`приводятся"' к значениям перед помещением их в память.\\

Существует различные накладные расходы, связанные с переходниками: они требуют времени на создание и вычисление, они занимают место в хипе (heap), они заставляют сборщик мусора (garbage collector) учитывать дополнительные структуры, нужные для вычисления переходников. Для того, чтобы избежать этих накладных расходов, существует специальный \textit{флаг строгости} (strictness flag) в объявлениях \code{data}, позволяющий вычислять выбранные поля контсруктора немедленно. Этот флаг выборочно подавляет ленивость. Поле, отмеченное восклицательным знаком ($!$) в \code{data} объявлении, вычисляется когда структура создаётся, а не откладывается на потом.\\

Бывает полезно применить флаг строгости в нескольких случаях:

\begin{itemize}
	\item Если компоненты структуры должны быть вычислены на определённом этапе выполнения программы.
	\item Если комоненты структуры легко вычисляются и не приводят к ошибкам.
	\item Типы, в которых некоторые значения не требуются (частично неопределённые типы).
\end{itemize}

Для примера, библиотека для работы с комплексными числами определяет тип \code{Complex} следующим образом:
\begin{center}
\code{data\ RealFloat\ a\ =>\ Complex\ a\ =\ !a\ :+\ !a}
\end{center}

[Обратите внимание на инфиксную запись конструктора \code{:+}.] Такое определение указывает, что два компонента - действительная и мнимая части комплексного числа - являются строгими. Это более компактное представление комплексного числа, но это приводит к невозможности создания частично неопределённых структур (например, \code{1\ :+} $\bot$ приводит к $\bot$). Так как для комплексных чисел в этом нет особой надобности, то исползование флагов строгости полностью оправданно.\\

%???
Флаги строгости могут быть использованы для нахождения утечек памяти (memory leaks) - структур оставленных сборщиком мусора, но более не нужных.\\

Флаг строгости, $!$, может использовать только в \code{data} объявлениях. Он не может использоваться в других сигнатурах типов или в каких-либо определениях типов. Не существует равноценного способа обозначить аргументы функций на наличие строгости. Этого эффекта можно добиться с помощью функций \code{seq} или $!\verb|$|$. См. $\verb|§|$4.2.1.\\

Трудно четко определить, когда  должен использоваться флаг строгости. Он должен быть использован очень осторожно: ленивые вычисления являются одним из основных свойств \has, а использование флага строгости может привести к трудноуловимым проблемам и бесконечным циклам.

\section{Ввод/Вывод}
Система I/O в \has является чисто функциональной, но имеет все возможности обычных языков программирования. В императивных языках, программы описываются \textit{действиями} (actions), которые проверяют и изменяют текущее состояние мира. Обычные действия включают чтение и запись глобальных переменных, запись в файл, чтение с клавиатуры, создание окон. Такие действия есть и в \has, но они чётко отделены от чисто функционального ядра языка.\\

%??? теория групп?
Система I/O \has построена на основе какой-то страшно непонятной математики: на \textit{монадах} (monads). Тем не менее, изучение теории не обязательно для программирования на \has. Монады являются концептуальными структурами, которые подходят для I/O. Для того, чтобы работать с I/O не нужно ничего более знания теории групп для простых арифметических вычислений. Полноценное описание монад находится в разделе 9.\\

Операции с монадами, на который построена система I/O, используются и для других целей; вернёмся к этому позже. В данный момент постараемся избегать слова "`монада"', а просто рассмотрим использование системы I/O. Лучше всего рассматривать монады как абстрактные структуры данных.\\

В \has действия скорее описываются, нежели вызываются (исполняются). Вычисление определения действия на самом деле не вызывает этого действия. Действие происходит в другом месте, а не в выражении, о котором мы здесь говорим.\\

Действия либо являются атомарными (как и базовые системыные действиями), либо являются последовательной композицией других действий. Последнее очень походит на последовательное объеденение выражений с помощью $\verb|;|$ в других языках. Монады служат "`клеем"', который связывает действия в программе.

\subsection{Базовые операции I/O}
Любое I/O действие возвращает значение. В системе типов такое значение завязано с типом \code{IO}, что отличает действия от других значений. Например, типом функции \code{getChar} является:

\begin{center}
\code{getChar\ ::\ IO\ Char}
\end{center}

\code{IO\ Char} показывает, что \code{getChar}, когда вызывается, выполняет какие-то действия, которые возвращают символ. Действия, которые возвращают ненужные значения, используют тип \code{()}. Например, функция \code{putChar}:
\begin{center}
\code{putChar\ ::\ Char\ ->\ IO\ ()}
\end{center}

принимает символ, но не возвращает ничего полезного. Такой тип по сути является эквивалентом \code{void} других языков.\\

Действия упорядочены (sequenced) с помощью оператора, который имеет загадочное имя: \code{>>=} (читается как "`привязать"'). Вопреки прямому использованию этого оператора, мы используем синтаксический сахар в виде \code{do}. Такое сокращение можно тривиально развернуть в \code{>>=}, как описано в \verb|§|3.14.\\

Ключевое слово \code{do} начинает последовательность утверждений (statements), которые выполняются по порядку. Утверждениями называют либо действия, т.е. шаблон связанный с результатом действия с помощью \code{<-}, либо множество локальных определений с использованием \code{let}. \code{do} использует разметку точно так же, как и \code{let} или \code{where}, так что мы можем опустить скобки и точки с запятой. Вот простая программа, которая считывает символ с клавиатуры, а затем выводит символ на консоль:
\begin{figure}[ht]
\DHSp
\label{fig_readwrite1}
\begin{tabular}{ll}
\GrT{\code{main}} & \code{::\ IO\ ()}\\
\GrT{\code{main}} & \code{=\ do\ c\ <-\ getChar}\\
\GrT{\code{}} & \code{\ putChar\ c}
\end{tabular}
\end{figure}
Обратите внимание на использование имени \code{main}: оно является входной точкой программ на \has (как и \code{main} в С), и должно иметь тип \code{IO}, обычно \code{IO\ ()}. (имя \code{main} является особым только в модуле \code{Main}; вскоре мы обсудим и модули.) Эта программа последовательно выполняет два действия: сначала она считывает символ, привязывая результат к переменной \code{c}, а затем выводит его на консоль. В отличии от выражений \code{let}, где переменные видимы во всех определениях, переменные объявленные \code{<-} видимы лишь в следующих утверждениях.\\

Остаётся непонятным одно: как можно вернуть результат последовательности действий? Например, представьте функцию \code{ready}, которая считавает символ и возвращает \code{True} если это был \code{'y'}:
\begin{figure}[ht]
\DHSp
\label{fig_readwrite2}
\begin{tabular}{ll}
\GrT{\code{ready}} & \code{::\ IO\ Bool}\\
\GrT{\code{ready}} & \code{=\ do\ c\ <-\ getChar}\\
\GrT{\code{}} & \code{\ c\ ==\ 'y'\\ -- BAD!!!}
\end{tabular}
\end{figure}
Это не сработает, так как второе утверждение в \code{do} это просто значение-буль, а не действие. 

\include{TranslationGlossary}
\end{document}