Описание Haskell 98: Объявления Описание Haskell 98
наверх | назад | вперед | содержание | предметный указатель функций

4  Объявления и связывания имен

В этой главе мы опишем синтаксис и неформальную семантику объявлений Haskell .

module -> module modid [exports] where body
| body
body -> { impdecls ; topdecls }
| { impdecls }
| { topdecls }
topdecls -> topdecl1 ; ... ; topdecln (n>=1)
topdecl -> type simpletype = type
| data [context =>] simpletype = constrs [deriving]
| newtype [context =>] simpletype = newconstr [deriving]
| class [scontext =>] tycls tyvar [where cdecls]
| instance [scontext =>] qtycls inst [where idecls]
| default (type1 , ... , typen) (n>=0)
| decl
decls -> { decl1 ; ... ; decln } (n>=0)
decl -> gendecl
| (funlhs | pat0) rhs
cdecls -> { cdecl1 ; ... ; cdecln } (n>=0)
cdecl -> gendecl
| (funlhs | var) rhs
idecls -> { idecl1 ; ... ; idecln } (n>=0)
idecl -> (funlhs | var) rhs
| (пусто)
gendecl -> vars :: [context =>] type (сигнатура типа)
| fixity [integer] ops (infix-объявление)
| (пустое объявление)
ops -> op1 , ... , opn (n>=1)
vars -> var1 , ... , varn (n>=1)
fixity -> infixl | infixr | infix

Перевод:
модуль -> module идентификатор-модуля [список-экспорта] where тело
| тело
тело -> { список-объявлений-импорта ; список-объявлений-верхнего-уровня }
| { список-объявлений-импорта }
| { список-объявлений-верхнего-уровня }
список-объявлений-верхнего-уровня -> объявление-верхнего-уровня1 ; ... ; объявление-верхнего-уровняn (n>=1)
объявление-верхнего-уровня -> type простой-тип = тип
| data [контекст =>] простой-тип = список-конструкций [deriving-инструкция]
| newtype [контекст =>] простой-тип = новая-конструкция [deriving-инструкция]
| class [простой-контекст =>] класс-типа переменная-типа [where список-объявлений-классов]
| instance [простой-контекст =>] квалифицированный-класс-типа экземпляр [where список-объявлений-экземпляров]
| default (тип1 , ... , типn) (n>=0)
| объявление
список-объявлений -> { объявление1 ; ... ; объявлениеn } (n>=0)
объявление -> общее-объявление
| (левая-часть-функции | образец0) правая-часть
список-объявлений-классов -> { объявление-класса1 ; ... ; объявление-классаn } (n>=0)
объявление-класса -> общее-объявление
| (левая-часть-функции | переменная) правая-часть
список-объявлений-экземпляров -> { объявление-экземпляра1 ; ... ; объявление-экземпляраn } (n>=0)
объявление-экземпляра -> (левая-часть-функции | переменная) правая-часть
| (пусто)
общее-объявление -> список-переменных :: [контекст =>] тип (сигнатура типа)
| ассоциативность [целый-литерал] список-операторов (infix-объявление)
| (пустое объявление)
список-операторов -> оператор1 , ... , операторn (n>=1)
список-переменных -> переменная1 , ... , переменнаяn (n>=1)
ассоциативность -> infixl | infixr | infix

Объявления в синтаксической категории topdecls (список-объявлений-верхнего-уровня) допустимы только на верхнем уровне модуля Haskell (см. главу 5), тогда как decls (список-объявлений) можно использовать или на верхнем уровне, или во вложенных областях видимости (т.е. в пределах конструкций let или where).

Для описания мы разделили объявления на три группы: группу определяемых пользователем типов данных, состоящую из объявлений type, newtype и data (раздел 4.2), группу классов типов и перегрузок операторов, состоящую из объявлений class, instance и default (раздел 4.3), и группу вложенных объявлений, состоящую из связываний значений, сигнатур типов и infix-объявлений (раздел 4.4).

В Haskell есть несколько примитивных типов данных, которые являются "зашитыми" (такие как целые числа и числа с плавающей точкой), но большинство "встроенных" типов данных определено с помощью обычного кода на Haskell с использованием обычных объявлений type и data. Эти "встроенные" типы данных подробно описаны в разделе 6.1.

4.1  Обзор типов и классов

Haskell использует традиционную систему полиморфных типов Хиндли-Милнера (Hindley-Milner) для того, чтобы обеспечить статическую семантику типов [3, 5], но система типов была расширена с помощью классов типов (или просто классов), которые обеспечивают структурированный способ ввести перегруженные функции.

Объявление class (раздел 4.3.1) вводит новый класс типа и перегруженные операции, которые должны поддерживаться любым типом, который является экземпляром этого класса. Объявление instance (раздел 4.3.2) объявляет, что тип является экземпляром класса и включает определения перегруженных операций, называемых методами класса, инстанцированных на названном типе.

Например, предположим, что мы хотим перегрузить операции (+) и negate на типах Int и Float. Мы вводим новый класс типов, названный Num:

  class Num a  where          -- упрощенное объявление класса Num
    (+)    :: a -> a -> a     -- (Класс Num определен в Prelude)
    negate :: a -> a

Это объявление можно толковать так: "тип a является экземпляром класса Num, если есть методы класса (+) и negate заданных типов, определенные на этом типе."

Затем мы можем объявить Int и Float экземплярами этого класса:

  instance Num Int  where     -- упрощенный экземпляр Num Int
    x + y       =  addInt x y
    negate x    =  negateInt x
  
  instance Num Float  where   -- упрощенный экземпляр Num Float
    x + y       =  addFloat x y
    negate x    =  negateFloat x

где предполагается, что addInt, negateInt, addFloat и negateFloat --- примитивные, в данном случае, функции, но вообще могут быть любыми определяемыми пользователем функциями. Первое сверху объявление можно толковать так: "Int является экземпляром класса Num в соответствии с этими определениями (т.е. методами класса) для (+) и negate. "

Большее количество примеров классов типов можно найти в работах Джонса (Jones) [7] или Уодлера и Блотта (Wadler и Blott) [12]. Термин "класс типа" использовался для описания системы типов в исходном языке Haskell 1.0, а термин "конструктор класса" --- для описания расширения исходных классов типов. Больше нет никакой причины использовать два различных термина: в этом описании "класс типа" включает и классы типов исходного языка Haskell , и конструируемые классы, введенные Джонсом (Jones).

4.1.1  Виды

Для того чтобы гарантировать их допустимость, выражения с типами разделены на классы различных видов . Каждый вид имеет одну из двух возможных форм:

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

4.1.2  Синтаксис типов

type -> btype [-> type] (тип функции)
btype -> [btype] atype (наложение типов)
atype -> gtycon
| tyvar
| ( type1 , ... , typek ) (тип кортежа, k>=2)
| [ type ] (тип списка)
| ( type ) (конструктор в скобках)
gtycon -> qtycon
| () (тип объединения)
| [] (конструктор списка)
| (->) (конструктор функции)
| (,{,}) (конструкторы кортежей)

Перевод:
тип -> b-тип [-> тип] (тип функции)
b-тип -> [b-тип] a-тип (наложение типов)
a-тип -> общий-конструктор-типа
| переменная-типа
| ( тип1 , ... , типk ) (тип кортежа, k>=2)
| [ тип ] (тип списка)
| ( тип ) (конструктор в скобках)
общий-конструктор-типа -> квалифицированный-конструктор-типа
| () (тип объединения)
| [] (конструктор списка)
| (->) (конструктор функции)
| (,{,}) (конструкторы кортежей)

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

Основными видами выражений с типами являются следующие:

  1. Переменные типов, которые обозначаются идентификаторами, начинающимися со строчной буквы. Вид, к которому относится переменная, определяется неявно из контекста, в котором она появилась.

  2. Конструкторы типов. Большинство конструкторов типов обозначаются идентификаторами, начинающимися с заглавной буквы. Например:
    • Char, Int, Integer, Float, Double и Bool являются константами типов и относятся к виду *.
    • Maybe и IO являются конструкторами типов с одним аргументом и рассматриваются как типы, относящиеся к виду *->*.
    • Объявления data T ... или newtype T ... добавляют в список типов конструктор типа T. Вид, к которому относится тип T, определяется с помощью вывода вида.
    Для конструкторов определенных встроенных типов предусмотрен специальный синтаксис:
    • Тривиальный тип обозначается () и относится к виду *. Он обозначает тип "кортеж с нулевым числом аргументов" и имеет ровно одно значение, которое также обозначается () (см. разделы 3.9 и 6.1.5).
    • Тип функции обозначается (->) и относится к виду *->*->*.
    • Тип списка обозначается [] и относится к виду *->*.
    • Типы кортежей обозначаются (,), (,,) и так далее. Они относятся к видам *->*->*, *->*->*->* и так далее .
    Использование констант (->) и [] более подробно описано ниже.

  3. Наложение типов. Если t1 --- тип, относящийся к виду k1->k2, а t2 --- тип, относящийся к виду k1, то t1 t2 является выражением с типом, относящимся к виду k2.

  4. Тип в скобках вида (t) идентичен типу t.

Например, выражение типа IO a можно воспринимать как применение константы IO к переменной a. Поскольку конструктор типа IO относится к виду *->*, из этого следует, что и переменная a, и все выражение IO a должно относиться к виду *. Вообще, процесс вывода вида (см. раздел 4.6) необходим для того, чтобы установить соответствующие виды для определяемых пользователем типов данных, синонимов типов и классов.

Поддерживается специальный синтаксис, который позволяет записывать выражения с определенными типами с использованием более традиционного стиля:

  1. Тип функции имеет вид t1 -> t2 и эквивалентен типу (->) t1 t2. Стрелки функций являются правоассоциативными операциями. Например, Int -> Int -> Float означает Int -> (Int -> Float).

  2. Тип кортежа имеет вид (t1, ... , tk), где k>=2, и эквивалентен типу (,...,) t1 ... tk, где имеются k-1 запятых между круглыми скобками. Он обозначает тип k-кортежей, у которых первая компонента имеет тип t1, вторая компонента --- тип t2 и так далее (см. разделы 3.8 и 6.1.4).

  3. Тип списка имеет вид [t] и эквивалентен типу [] t. Он обозначает тип списков с элементами типа t (см. разделы 3.7 и 6.1.3).

Эти специальные синтаксические формы всегда обозначают конструкторы встроенных типов для функций, кортежей и списков, независимо от того, что находится в области видимости. Аналогично, префиксные конструкторы типов (->), [], (), (,) и так далее всегда обозначают конструкторы встроенных типов; их нельзя ни использовать с квалификаторами, ни указывать в списках импорта или экспорта (глава 5). (Отсюда специальное правило вывода gtycon (общего-конструктора-типа), описанное выше.)

Несмотря на то, что у типов списков и кортежей специальный синтаксис, их семантика --- такая же, как и у эквивалентных определяемых пользователем алгебраических типов данных.

Отметим, что выражения и типы имеют согласующийся синтаксис. Если ti --- тип выражения или образца ei, то выражения (\ e1 -> e2), [e1] и (e1,e2) имеют соответственно типы (t1 -> t2), [t1] и (t1,t2).

За одним исключением (переменной типа в объявлении класса (раздел 4.3.1)), все переменные типов в выражении с типами Haskell предполагаются стоящими под квантором всеобщности; квантор всеобщности [3] не указывается явно, для этого нет специального синтаксиса. Например, выражение a -> a обозначает тип forall a. a ->a. Тем не менее, для ясности, мы часто записываем кванторы явно при обсуждении типов программ на Haskell . Когда мы записываем тип с явным использованием квантора, область действия квантора forall (для всех) простирается вправо насколько возможно, например, forall a. a ->a означает forall a. (a ->a).

4.1.3  Синтаксис утверждений классов и контекстов

context -> class
| ( class1 , ... , classn ) (n>=0)
class -> qtycls tyvar
| qtycls ( tyvar atype1 ... atypen ) (n>=1)
qtycls -> [ modid . ] tycls
tycls -> conid
tyvar -> varid

Перевод:
контекст -> класс
| ( класс1 , ... , классn ) (n>=0)
класс -> квалифицированный-класс-типа переменная-типа
| квалифицированный-класс-типа ( переменная-типа a-тип1 ... a-типn ) (n>=1)
квалифицированный-класс-типа -> [ идентификатор-модуля . ] класс-типа
класс-типа -> идентификатор-конструктора
переменная-типа -> идентификатор-переменной

Утверждение класса имеет вид qtycls tyvar и указывает на то, что тип tyvar является элементом класса qtycls. Идентификатор класса начинается с заглавной буквы. Контекст состоит из нуля или более утверждений класса и имеет общий вид

( C1 u1, ..., Cn un )

где C1, ..., Cn --- идентификаторы класса, и каждый из u1, ..., un является или переменной типа, или применением переменной типа к одному или более типам. Внешние круглые скобки можно опустить при n=1. Вообще, мы используем cx для обозначения контекста и мы записываем cx => t для указания того, что тип t ограничен контекстом cx. Контекст cx должен содержать только переменные типов, упомянутые в t. Для удобства мы записываем cx => t, даже если контекст cx пуст, хотя в этом случае конкретный синтаксис не содержит =>.

4.1.4  Семантика типов и классов

В этом разделе мы дадим неформальные детали системы типов. (Уодлер (Wadler) и Блотт (Blott) [12] и Джонс (Jones) [7] рассматривают соответственно классы типов и конструируемые классы более подробно.)

Система типов в Haskell приписывает тип каждому выражению в программе. Вообще, тип имеет вид forall u. cx =>t, где u --- набор переменных типов u1, ..., un. В любом таком типе любая из стоящих под квантором всеобщности переменных типов ui, которая является свободной в cx, должна также быть свободной в t. Кроме того, контекст cx должен иметь вид, описанный выше в разделе 4.1.3. В качестве примера приведем некоторые допустимые типы:


  Eq a => a -> a
  (Eq a, Show a, Eq b) => [a] -> [b] -> String
  (Eq (f a), Functor f) => (a -> b) -> f a -> f b -> Bool

В третьем типе ограничение Eq (f a) не может быть упрощено, потому что f стоит под квантором всеобщности.

Тип выражения e зависит от окружения типа, которое задает типы для свободных переменных в e, и окружения класса, которое объявляет, какие типы являются экземплярами каких классов (тип становится экземпляром класса только посредством наличия объявления instance или инструкции deriving).

Типы связаны прямым порядком обобщения (указан ниже); наиболее общий тип, с точностью до эквивалентности, полученный посредством обобщения, который можно присвоить конкретному выражению (в заданном окружении), называется его основным типом. В системе типов в языке Haskell , которая является расширением системы Хиндли-Милнера (Hindley-Milner), можно вывести основной тип всех выражений, включая надлежащее использование перегруженных методов класса (хотя, как описано в разделе 4.3.4, при этом могут возникнуть определенные неоднозначные перегрузки). Поэтому использование явных указаний типов (называемые сигнатурами типов) обычно является необязательным (см. разделы 3.16 и 4.4.1).

Тип forall u. cx1 =>t1 является более общим чем тип forall w. cx2 =>t2, если и только если существует подстановка S с областью определения u, такая что:

Значение типа forall u. cx =>t можно инстанцировать на типах s, если и только если выполняется контекст cx[s/u]. Например, рассмотрим функцию double:


  double x = x + x

Наиболее общим типом для double является forall a. Num a =>a ->a. double можно применять к значениям типа Int (инстанцирование a к Int), так как выполняется Num Int, потому что Int является экземпляром класса Num. Однако double обычно нельзя применять к значениям типа Char, потому что Char обычно не является экземпляром класса Num. Пользователь может предпочесть объявить такой экземпляр, в этом случае double можно действительно применить к Char.

4.2  Типы данных, определяемые пользователем

В этом разделе мы опишем алгебраические типы данных (объявления data), переименованные типы данных (объявления newtype) и синонимы типов (объявления type). Эти объявления можно использовать только на верхнем уровне модуля.

4.2.1  Объявления алгебраических типов данных

topdecl -> data [context =>] simpletype = constrs [deriving]
simpletype -> tycon tyvar1 ... tyvark (k>=0)
constrs -> constr1 | ... | constrn (n>=1)
constr -> con [!] atype1 ... [!] atypek (число аргументов конструктора con = k, k>=0)
| (btype | ! atype) conop (btype | ! atype) (инфиксный оператор conop)
| con { fielddecl1 , ... , fielddecln } (n>=0)
fielddecl -> vars :: (type | ! atype)
deriving -> deriving (dclass | (dclass1, ... , dclassn)) (n>=0)
dclass -> qtycls

Перевод:
объявление-верхнего-уровня -> data [контекст =>] простой-тип = список-конструкций [deriving-инструкция]
простой-тип -> конструктор-типа переменная-типа1 ... переменная-типаk (k>=0)
список-конструкций -> конструкция1 | ... | конструкцияn (n>=1)
конструкция -> конструктор [!] a-тип1 ... [!] a-типk (число аргументов конструктора con = k, k>=0)
| (b-тип | ! a-тип) оператор-конструктора (b-тип | ! a-тип) (инфиксный оператор conop)
| конструктор { объявление-поля1 , ... , объявление-поляn } (n>=0)
объявление-поля -> список-переменных :: (тип | ! a-тип)
deriving-инструкция -> deriving (производный-класс | (производный-класс1, ... , производный-классn)) (n>=0)
производный-класс -> квалифицированный-класс-типа
Приоритет для constr (конструкции) --- тот же, что и для выражений: применение обычного конструктора имеет более высокий приоритет, чем применение инфиксного конструктора (таким образом, a : Foo a интерпретируется при разборе как a : (Foo a)).

Объявление алгебраического типа данных имеет вид:

data cx => T u1 ... uk = K1 t11 ... t1k1 | ...| Kn tn1 ... tnkn

где cx --- контекст. Это объявление вводит новый конструктор типа T с одной или более составляющими конструкторами данных K1, ..., Kn. В этом описании неуточненный термин "конструктор" всегда означает "конструктор данных".

Типы конструкторов данных задаются следующим образом:

Ki :: forall u1 ... uk. cxi =>ti1 ->...->tiki ->(T u1 ... uk)

где cxi --- наибольшее подмножество cx, которое содержит только те переменные типов, котрые являются свободными в типах ti1, ..., tiki. Переменные типов u1, ..., uk должны быть различными и могут появляться в cx и tij; если любая другая переменная типа появится в cx или в правой части --- возникнет статическая ошибка. Новая константа типа T относится к виду k1->...->kk->*, где виды ki, к которым относятся переменные аргументов ui, устанавливаются с помощью выводы вида, описанного в разделе 4.6. Это означает, что T можно использовать в выражениях с типами с любым числом аргументов от 0 до k.

Например, объявление

  data Eq a => Set a = NilSet | ConsSet a (Set a)

вводит конструктор типа Set, который относится к виду *->*, и конструкторы NilSet и ConsSet с типами

NilSet :: forall a. Set a
ConsSet :: forall a. Eq a =>a ->Set a ->Set a

В данном примере перегруженный тип для ConsSet гарантирует, что ConsSet можно применить только к значениям типа, который является экземпляром класса Eq. Сопоставление с образцом ConsSet также приводит к ограничению Eq a. Например:

  f (ConsSet a s) = a

Функция f имеет установленный с помощью вывода тип Eq a => Set a -> a. Контекст в объявлении data вообще не имеет никакого другого результата.

Видимость конструкторов типов данных (т.е. "абстрактность" типа данных) вне модуля, в котором определен тип данных, управляется посредством указания имени типа данных в списке экспорта, описанном в разделе 5.8.

Необязательная в объявлении data часть deriving должна относиться к производным экземплярам и описана в разделе 4.3.3.

Именованные поля

Конструктор данных с k аргументами создает объект с k компонентами. К этим компонентам обычно обращаются исходя из их позиций, как с аргументами конструктора в выражениях или образцах. Для больших типов данных полезно присваивать имена полей компонентам объекта данных. Это позволяет ссылаться на определенное поле независимо от его размещения в пределах конструктора.

Определение конструктора в объявлении data может присвоить имена полям конструктора, используя синтаксис записи (C { ... }). Конструкторы, использующие имена полей, можно свободно смешивать с конструкторами без них. Конструктор со связанными именами полей можно по-прежнему использовать как обычный конструктор; использование имен просто является краткой записью для операций, использующих лежащий в основе позиционный конструктор. Аргументы позиционного конструктора находятся в том же порядке, что и именованные поля. Например, объявление

  data C = F { f1,f2 :: Int, f3 :: Bool }

определяет тип и конструктор, идентичный тому, который соответствует определению

  data C = F Int Int Bool

Операции, использующие имена полей, описаны в разделе 3.15. Объявление data может использовать то же самое имя поля во множестве конструкторов до тех пор, пока тип поля, после раскрытия синонимов, остается одним и тем же во всех случаях. Одно и то же имя не могут совместно использовать несколько типов в области видимости. Имена полей совместно используют пространство имен верхнего уровня вместе с обычными переменными и методами класса и не должны конфликтовать с другими именами верхнего уровня в области видимости.

Образец F {} соответствует любому значению, построенному конструктором F, независимо от того, был объявлен F с использованием синтаксиса записи или нет.

Флажки строгости

Всякий раз, когда применяется конструктор данных, каждый аргумент конструктора вычисляется, если и только если соответствующий тип в объявлении алгебраического типа данных имеет флажок строгости, обозначаемый восклицательным знаком "!". С точки зрения лексики, "!" --- обычный varsym (символ-переменной), а не reservedop (зарезервированный-оператор), он имеет специальное значение только в контексте типов аргументов объявления data.

Трансляция:

Объявление вида

data cx => T u1 ... uk = ... | K s1 ... sn | ...

где каждый si имеет вид ! ti или ti, замещает каждое вхождение K в выражении на

(\ x1 ... xn -> ( ((K op1 x1) op2 x2) ... ) opn xn)

где opi --- нестрогое применение функции $, если si имеет вид ti, а opi --- строгое применение функции $! (см. раздел 6.2), если si имеет вид ! ti. На сопоставление с образцом в K не влияют флажки строгости.

4.2.2  Объявление синонимов типов

topdecl -> type simpletype = type
simpletype -> tycon tyvar1 ... tyvark (k>=0)

Перевод:
объявление-верхнего-уровня -> type простой-тип = тип
простой-тип -> конструктор-типа переменная-типа1 ... переменная-типаk (k>=0)
Объявление синонима типа вводит новый тип, который эквивалентен старому типу. Объявление имеет вид

type T u1 ... uk = t

и вводит конструктор нового типа --- T. Тип (T t1 ... tk) эквивалентен типу t[t1/u1, ..., tk/uk]. Переменные типа u1, ... , uk должны быть различными и находятся в области видимости только над t; если любая другая переменная типа появится в t --- возникнет статическая ошибка. Конструктор нового типа T относится к виду k1->...->kk->k, где виды ki, к которым относятся аргументы ui, и k в правой части t устанавливаются с помощью вывода вида, описанного в разделе 4.6. Например, следующее определение можно использовать для того, чтобы обеспечить альтернативный способ записи конструктора типа список:

  type List = []

Символы конструкторов типов T, введенные с помощью объявлений синонимов типов, нельзя применять частично; если использовать T без полного числа аргументов --- возникнет статическая ошибка.

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


  type Rec a   =  [Circ a]
  data Circ a  =  Tag [Rec a]

допустимы, тогда как

  type Rec a   =  [Circ a]        -- неправильно
  type Circ a  =  [Rec a]         -- неправильно

--- нет. Аналогично, type Rec a = [Rec a] недопустим.

Синонимы типов представляют собой удобный, но строго синтаксический механизм, который делает сигнатуры более читабельными. Синоним и его определение --- полностью взаимозаменяемы, за исключением типа экземпляра в объявлении instance (раздел 4.3.2).

4.2.3  Переименования типов данных

topdecl -> newtype [context =>] simpletype = newconstr [deriving]
newconstr -> con atype
| con { var :: type }
simpletype -> tycon tyvar1 ... tyvark (k>=0)

Перевод:
объявление-верхнего-уровня -> newtype [контекст =>] простой-тип = новая-конструкция [deriving-инструкция]
новая-конструкция -> конструктор a-тип
| конструктор { переменная :: тип }
простой-тип -> конструтор-типа переменная-типа1 ... переменная-типаk (k>=0)

Объявление вида

newtype cx => T u1 ... uk = N t

вводит новый тип, который имеет то же самое представление, что и существующий тип. Тип (T u1 ... uk) переименовывает тип данных t. Он отличается от синонима типа тем, что создает отдельный тип, который должен явно приводиться к исходному типу или обратно. Также, в отличие от синонимов типа, newtype может использоваться для определения рекурсивных типов. Конструктор N в выражении приводит значение типа t к типу (T u1 ... uk). Использование N в образце приводит значение типа (T u1 ... uk) к типу t. Эти приведения типов могут быть реализованы без накладных расходов времени выполнения, newtype не меняет лежащее в основе представление объекта.

Новые экземпляры (см. раздел 4.3.2) можно определить для типа, определенного с помощью newtype, но нельзя определить для синонима типа. Тип, созданный с помощью newtype, отличается от алгебраического типа данных тем, что представление алгебраического типа данных имеет дополнительный уровень непрямого доступа. Это отличие может сделать доступ к представлению менее эффективным. Различие отражено в различных правилах для сопоставления с образцом (см. раздел 3.17). В отличие от алгебраического типа данных, конструктор нового типа данных N является неповышенным, так что N _|_ --- то же самое, что и _|_.

Следующие примеры разъясняют различия между data (алгебраическими типами данных), type (синонимами типов) и newtype (переименованными типами). При данных объявлениях

  data D1 = D1 Int
  data D2 = D2 !Int
  type S = Int
  newtype N = N Int
  d1 (D1 i) = 42
  d2 (D2 i) = 42
  s i = 42
  n (N i) = 42

выражения ( d1 _|_), ( d2 _|_) и (d2 (D2 _|_) ) эквивалентны _|_, поскольку ( n _|_), ( n ( _|_) ), ( d1 ( D1 _|_) ) и ( s _|_) эквивалентны 42. В частности, ( N _|_) эквивалентно _|_, тогда как ( D1 _|_) неэквивалентно _|_.

Необязательная часть deriving объявления newtype трактуется так же, как и компонента deriving объявления data (см. раздел 4.3.3).

В объявлении newtype можно использовать синтаксис для именования полей, хотя, конечно, может быть только одно поле. Таким образом,

  newtype Age = Age { unAge :: Int }

вводит в область видимости и конструктор, и деструктор:

  Age   :: Int -> Age
  unAge :: Age -> Int

4.3  Классы типов и перегрузка

4.3.1  Объявления классов

topdecl -> class [scontext =>] tycls tyvar [where cdecls]
scontext -> simpleclass
| ( simpleclass1 , ... , simpleclassn ) (n>=0)
simpleclass -> qtycls tyvar
cdecls -> { cdecl1 ; ... ; cdecln } (n>=0)
cdecl -> gendecl
| (funlhs | var) rhs

Перевод:
объявление-верхнего-уровня -> class [простой-контекст =>] класс-типа переменная-типа [where список-объявлений-классов]
простой-контекст -> простой-класс
| ( простой-класс1 , ... , простой-классn ) (n>=0)
простой-класс -> квалифицированный-класс-типа переменная-типа
список-объявлений-классов -> { объявление-класса1 ; ... ; объявление-классаn } (n>=0)
объявление-класса -> общее-объявление
| (левая-часть-функции | переменная) правая-часть

Объявление класса вводит новый класс и операции (методы класса) над ним. Объявление класса имеет общий вид:

class cx => C u where cdecls

Это объявление вводит новый класс C; переменная типа u находится только в области видимости над сигнатурами методов класса в теле класса. Контекст cx определяет суперклассы C, как описано ниже; единственной переменной типа, на которую можно ссылаться в cx, является u.

Отношение суперкласса не должно быть циклическим; т.е. оно должно образовывать ориетированный ациклический граф.

Часть cdecls (список-объявлений-классов) в объявлении class содержит три вида объявлений:

В остальных случаях, отличных от описанных здесь, никакие другие объявления не допустимы в cdecls.

Объявление class без части where может оказаться полезным для объединения совокупности классов в больший класс, который унаследует все методы исходных классов. Например,

  class  (Read a, Show a) => Textual a

В таком случае, если тип является экземпляром всех суперклассов, это не означает, что он автоматически является экземпляром подкласса, даже если подкласс не имеет непосредственных методов класса. Объявление instance должно быть задано явно без части where.

4.3.2  Объявления экземпляров

topdecl -> instance [scontext =>] qtycls inst [where idecls]
inst -> gtycon
| ( gtycon tyvar1 ... tyvark ) (k>=0, все tyvar различны)
| ( tyvar1 , ... , tyvark ) (k>=2, все tyvar различны)
| [ tyvar ]
| ( tyvar1 -> tyvar2 ) (tyvar1 и tyvar2 различны)
idecls -> { idecl1 ; ... ; idecln } (n>=0)
idecl -> (funlhs | var) rhs
| (пусто)

объявление-верхнего-уровня -> instance [простой-контекст =>] квалифицированный-класс-типа экземпляр [where список-объявлений-экземпляров]
экземпляр -> общий-конструктор-типа
| ( общий-конструктор-типа переменная-типа1 ... переменная-типаk ) (k>=0, все переменные-типа различны)
| ( переменная-типа1 , ... , переменная-типаk ) (k>=2, все переменные-типа различны)
| [ переменная-типа ]
| ( переменная-типа1 -> переменная-типа2 ) (переменная-типа1 и переменная-типа2 различны)
список-объявлений-экземпляров -> { объявление-экземпляра1 ; ... ; объявление-экземпляраn } (n>=0)
объявление-экземпляра -> (левая-часть-функции | переменная) правая-часть
| (пусто)
Объявление экземпляра вводит экземпляр класса. Пусть

class cx => C u where { cbody }

является объявлением class. Тогда соответствующее объявление экземпляра в общем виде:

instance cx' => C (T u1 ... uk) where { d }

где k>=0. Тип (T u1 ... uk) должен иметь вид конструктора типа T, примененного к простым переменным типа u1, ... uk; кроме того, T не должен являться синонимом типа, и все ui должны быть различными.

Поэтому такие объявления экземпляров запрещены:

  instance C (a,a) where ...
  instance C (Int,a) where ...
  instance C [[a]] where ...

Объявления d могут содержать связывания имен только для методов класса C. Неправильно задавать связывание имен для метода класса, который не находится в области видимости, но имя, в области которого он находится, несущественно; в частности, это может быть имя с квалификатором. (Это правило идентично тому, что используется для подчиненных имен в списках экспорта, см. раздел 5.2.) Например, это допустимо, даже если range находится в области видимости только с именем с квалификатором Ix.range.

  module A where
    import qualified Ix

    instance Ix.Ix T where
      range = ...

Объявления не могут содержать сигнатуры типов или infix-объявления, поскольку они уже были заданы в объявлении class. Как и в случае методов класса по умолчанию (раздел 4.3.1), объявления методов должны иметь вид переменной или определения функции.

Если для некоторого метода класса не заданы связывания имен, тогда используется соответствующий метод класса по умолчанию, заданный в объявлении class (если таковое имеется); если такой метод по умолчанию не существует, тогда метод класса этого экземпляра связывается с undefined, и ошибка компиляции не возникнет.

Объявление instance, которое объявляет тип T экземпляром класса C, называется объявлением экземпляра C-T и подчиняется следующим статическим ограничениям:

Следующий пример иллюстрирует ограничения, налагаемые экземплярами суперкласса:

  class Foo a => Bar a where ...
  
  instance (Eq a, Show a) => Foo [a] where ...
  
  instance Num a => Bar [a] where ...


Этот пример является правильным в Haskell. Так как Foo является суперклассом Bar, второе объявление экземпляра будет правильным, только если [a] является экземпляром Foo исходя из предположения Num a. Первое объявление экземпляра действительно сообщает, что [a] является экземпляром Foo исходя из этого предположения, потому что Eq и Show являются суперклассами Num.

Если, вместо этого, объявления двух экземпляров оказались бы подобны этим:

  instance Num a => Foo [a] where ...
  
  instance (Eq a, Show a) => Bar [a] where ...

тогда программа была бы неправильной. Объявление второго экземпляра будет правильным, только если [a] является экземпляром Foo исходя из предположений (Eq a, Show a). Но это не выполняется, так как [a] является экземпляром Foo только исходя из более сильного предположения Num a.

Дополнительные примеры объявлений instance можно найти в главе 8.

4.3.3  Производные экземпляры

Как упомянуто в разделе 4.2.1, объявления data и newtype содержат необязательную форму deriving . Если форма включена, то для каждого из названных классов типов данных автоматически генерируются объявления производных экземпляров. Эти экземпляры подчинены тем же самым ограничениям, что и определяемые пользователем экземпляры. При выведении класса C для типа T, для T должны существовать экземпляры для всех суперклассов класса C, либо посредством явного объявления instance, либо посредством включения суперкласса в инструкцию deriving.

Производные экземпляры предоставляют удобные, широко используемые операции для определяемых пользователем типов данных. Например, производные экземпляры для типов данных в классе Eq определяют операции == и /=, освобождая программиста от необходимости определять их.

Классами в Prelude, для которых разрешены производные экземпляры, являются: Eq, Ord, Enum, Bounded, Show и Read. Все они приведены на рис. 6.1, стр. . Точные детали того, как генерируются производные экземпляры для каждого из этих классов, даны в главе 10, включая подробное описание того, когда такие производные экземпляры возможны. Классы, определенные стандартными библиотеками, также можно использовать для порождения производных.

Если невозможно произвести объявление instance над классом, названном в форме deriving, --- возникнет статическая ошибка. Например, не все типы данных могут должным образом поддерживать методы класса Enum. Также статическая ошибка возникнет в случае, если задать явное объявление instance для класса, который также является производным.

Если форма deriving в объявлении data или newtype опущена, то никакие объявления экземпляров для этого типа данных не производятся, то есть отсутствие формы deriving эквивалентно включению пустой формы: deriving ().

4.3.4  Неоднозначные типы и значения по умолчанию для перегруженных числовых операций

topdecl -> default (type1 , ... , typen) (n>=0)

Перевод:
объявление-верхнего-уровня -> default (тип1 , ... , типn) (n>=0)

Проблема, связанная с перегрузкой в Haskell , состоит в возможности неоднозначного типа. Например, возьмем функции read и show, определенные в главе 10, и предположим, что именно Int и Bool являются членами Read и Show, тогда выражение

  let x = read "..." in show x -- неправильно

является неоднозначным, потому что условия, налагаемые на типы для show и read

show :: forall a. Show a =>a ->String
read :: forall a. Read a =>String ->a

можно выполнить путем инстанцирования a как Int или Bool в обоих случаях. Такие выражения считаются неправильно типизированными, возникнет статическая ошибка.

Мы говорим, что выражение e имеет неодназначный тип, если в его типе forall u. cx =>t есть переменная типа u в u, которая встречается в cx, но не в t. Такие типы недопустимы.

Например, ранее рассмотренное выражение, включающее show и read, имеет неоднозначный тип, так как его тип forall a. Show a, Read a =>String.

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

  let x = read "..." in show (x::Bool)

Это устраняет неоднозначность типа.

Иногда предпочтительнее, чтобы неоднозначное выражение было того же типа, что и некоторая переменная, а не заданного с помощью сигнатуры фиксированного типа. В этом состоит назначение функции asTypeOf (глава 8): x `asTypeOf` y имеет значение x, но заставляет x и y иметь один и тот же тип. Например,

  approxSqrt x = encodeFloat 1 (exponent x `div` 2) `asTypeOf` x

(Описание encodeFloat и exponent см. в разделе 6.4.6.)

Неоднозначности в классе Num наиболее распространены, поэтому Haskell предоставляет другой способ разрешить их --- с помощью default-объявления:

default (t1 , ... , tn)

где n>=0, и каждая ti должна иметь тип, для которого выполняется Num ti. В ситуациях, когда обнаружен неоднозначный тип, переменная неоднозначного типа v является умолчательной, если:

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

В модуле может быть только одно default-объявление, и его влияние ограничено этим модулем. Если в модуле default-объявление не задано, то предполагается, что задано объявление

  default (Integer, Double)

Пустое default-объявление default () отменяет все значения по умолчанию в модуле.

4.4  Вложенные объявления

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

4.4.1  Сигнатуры типов

gendecl -> vars :: [context =>] type
vars -> var1 , ..., varn (n>=1)

Перевод:
общее-объявление -> список-переменных :: [контекст =>] тип
список-переменых -> переменная1 , ..., переменнаяn (n>=1)
Сигнатура типа определяет типы для переменных, возможно по отношению к контексту. Сигнатура типа имеет вид:

v1, ..., vn :: cx => t

который эквивалентен утверждению vi :: cx => t для каждого i от 1 до n. Каждая vi должна иметь связанное с ним значение в том же списке объявлений, который содержит сигнатуру типа, т.е. будет неправильным задать сигнатуру типа для переменной, связанной во внешней области видимости. Кроме того, будет неправильным задать более одной сигнатуры типа для одной переменной, даже если сигнатуры идентичны.

Как упомянуто в разделе 4.1.2, каждая переменная типа, появляющаяся в сигнатуре, находится под квантором всеобщности над сигнатурой, и, следовательно, область видимости переменной типа ограничена сигнатурой типа, которая ее содержит. Например, в следующих объявлениях

  f :: a -> a
  f x = x :: a -- неправильно

a
в двух сигнатурах типа совершенно различны. Действительно, эти объявления содержат статическую ошибку, так как x не имеет тип forall a. a. (Тип x зависит от типа f; в настоящее время в Haskell нет способа указать сигнатуру для переменной с зависимым типом, это раэъясняется в разделе 4.5.4.)

Если данная программа включает сигнатуру для переменной f, тогда каждое использование f трактуется как f, имеющая объявленный тип. Если тот же тип нельзя также вывести для определяемого вхождения f --- возникнет статическая ошибка.

Если переменная f определена без соответствующей сигнатуры типа, тогда при использовании f вне его собственной группы объявлений (см. раздел 4.5) переменная трактуется как имеющая соответствующий выведенный или основной тип . Тем не менее, для того чтобы гарантировать, что вывод типа еще возможен, определяемое вхождение и все использования f в пределах его группы объявлений должны иметь один и тот же мономорфный тип (из которого основной тип получается путем обобщения, описанного в разделе 4.5.2).

Например, если мы определим

  sqr x  =  x*x

тогда основным типом будет sqr :: forall a. Num a =>a ->a. Этот тип позволяет такое применение, как sqr 5 или sqr 0.1. Также правильным будет объявить более специализированный тип, например

  sqr :: Int -> Int

но теперь такое применение, как sqr 0.1, будет неправильным. Такие сигнатуры типов, как

  sqr :: (Num a, Num b) => a -> b     -- неправильно
  sqr :: a -> a                       -- неправильно

являются неправильными, поскольку они являются более общими, чем основной тип sqr.

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

  data T a  =  K (T Int) (T a)

  f         :: T a -> a
  f (K x y) =  if f x == 1 then f y else undefined


Если мы уберем объявление сигнатуры, тип f будет выведен как T Int -> Int благодаря первому рекурсивному вызову, для которого аргументом f является T Int. Полиморфная рекурсия позволяет пользователю указать более общую сигнатуру типа T a -> a.

4.4.2  Infix-объявления

gendecl -> fixity [integer] ops
fixity -> infixl | infixr | infix
ops -> op1 , ... , opn (n>=1)
op -> varop | conop

Перевод:
общеее-объявление -> ассоциативность [целый-литерал] список-операторов
ассоциативность -> infixl | infixr | infix
список-операторов -> оператор1 , ... , операторn (n>=1)
оператор -> оператор-переменной | оператор-конструктора
infix-объявление задает ассоциативность и приоритет (силу связывания) одного или более операторов. Целое число integer в infix-объявлении должно быть в диапазоне от 0 до 9. infix-объявление можно разместить всюду, где можно разместить сигнатуру типа. Как и сигнатура типа, infix-объявление задает свойства конкретного оператора. Так же, как и сигнатура типа, infix-объявление можно разместить только в той же последовательности объявлений, что и объявление самого оператора, и для любого оператора можно задать не более одного infix-объявления. (Методы класса являются небольшим исключением: их infix-объявления можно размещать в самом объявлении класса или на верхнем уровне.)

По способу ассоциативности операторы делятся на три вида: неассоциативные, левоассоциативные и правоассоциативные ( infix, infixl и infixr соответственно). По приоритету (силе связывания) операторы делятся на десять групп, в соответствии с уровнем приоритета от 0 до 9 включительно (уровень 0 связывает операнды наименее сильно, а уровень 9 --- наиболее сильно). Если целое число integer не указано, оператору присваивается уровень приоритета 9. Любой оператор, для которого нет infix-объявления, считается объявленным infixl 9 (более подробную информацию об использовании infix-объявлений см. в разделе 3). В таблице 4.1 перечислены ассоциативности и приоритеты операторов, определенных в Prelude.

Прио- Левоассоциативные Неассоциативные Правоассоциативные
ритет операторы операторы операторы
9 !! .
8 ^, ^^, **
7 *, /, `div`,
`mod`, `rem`, `quot`
6 +, -
5 :, ++
4 ==, /=, <, <=, >, >=,
`elem`, `notElem`
3 &&
2 ||
1 >>, >>=
0 $, $!, `seq`

Таблица 2

Приоритеты и ассоциативности операторов в Prelude

Ассоциативность является свойством конкретного объекта (конструктора или переменной), как и его тип; ассоциативность не является свойством имени объекта. Например,

  module Bar( op ) where
    infixr 7 `op`
    op = ...
  
  module Foo where
    import qualified Bar
    infix 3 `op`
  
    a `op` b = (a `Bar.op` b) + 1
  
    f x = let
     p `op` q = (p `Foo.op` q) * 2
  in ...

Здесь `Bar.op` --- оператор с infixr 7, `Foo.op` --- оператор с infix 3, а оператор op во вложенном определении в правой части f имеет заданные по умолчанию infixl 9. (Свойства оператора `op` во вложенном определении можно было бы также задать с помощью вложенного infix-объявления.)

4.4.3  Связывание имен в функциях и образцах

decl -> (funlhs | pat0) rhs
funlhs -> var apat {apat }
| pati+1 varop(a,i) pati+1
| lpati varop(l,i) pati+1
| pati+1 varop(r,i) rpati
| ( funlhs ) apat {apat }
rhs -> = exp [where decls]
| gdrhs [where decls]
gdrhs -> gd = exp [gdrhs]
gd -> | exp0

Перевод:
объявление -> (левая-часть-функции | образец0) правая-часть
левая-часть-функции -> переменная такой-как-образец {такой-как-образец }
| образецi+1 оператор-переменной(a,i) образецi+1
| левый-образецi оператор-переменной(l,i) образецi+1
| образецi+1 оператор-переменной(r,i) правый-образецi
| ( левая-часть-функции ) такой-как-образец {такой-как-образец }
правая-часть -> = выражение [where список-объявлений]
| правая-часть-со-стражами [where список-объявлений]
правая-часть-со-стражами -> страж = выражение [правая-часть-со-стражами]
страж -> | выражение0
Мы различаем два случая использования этого синтаксиса: связывание имен в образцах происходит, когда левой частью является pat0, в противном случае это связывание имен в функциях. Связывание имен может иметь место на верхнем уровне модуля или в пределах конструкций where или let.

4.4.3.1  Связывание имен в функциях
Связывание имен в функции связывает переменную со значением функции. Связывание имен в функции для переменной x в общем виде выглядит так:

x p11 ... p1k match1
...
x pn1 ... pnk matchn

где каждое pij --- образец, а каждое matchi в общем виде выглядит так:

= ei where { declsi }

или

| gi1 = ei1
...
| gimi = eimi
where { declsi }

n>=1, 1<=i<=n, mi>=1. Первый из двух вариантов рассматривается как краткая запись для особого случая второго варианта, а именно:

| True = ei where { declsi }

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

Для связывания значений функций с инфиксными операторами имеется альтернативный синтаксис. Например, все эти три определения функции эквивалентны:

  plus x y z = x+y+z
  x 
`plus` y = \ z -> x+y+z
  (x 
`plus` y) z = x+y+z

Трансляция:

Связывание имен для функций в общем виде семантически эквивалентно уравнению (т.е. простому связыванию имен в образцах):

x = \ x1 ... xk -> case (x1...xk) of

(p11, ..., p1k) match1
...
(pn1, ..., pnk) matchn

где xi --- новые идентификаторы.

4.4.3.2  Связывание имен в образцах

Связывание имен в образцах связывает переменные со значениями. Простое связывание имен в образцах имеет вид p = e. Образец p "лениво" сопоставляется значению, как неопровержимый образец, как если бы впереди него был указана ~ (см. трансляцию в разделе 3.12).

В общем виде связывание имен в образцах выглядит так: p match, где match имеет ту же структуру, что для описанного выше связывания имен в функциях, другими словами, связывание имен в образцах имеет вид:

p | g1 = e1
| g2 = e2
...
| gm = em
where { decls }

Трансляция:

Описанное выше связывание имен в образцах семантически эквивалентно этому простому связыванию имен в образцах:

p = let decls in
if g1 then e1 else
if g2 then e2 else
...
if gm then em else error "Несопоставимый образец"

Замечание о синтаксисе.

Обычно просто отличить, является ли связывание имен связыванием имен в образце или в функции, но наличие n+k-образцов иногда сбивает с толку. Рассмотрим четыре примера:

  x + 1 = ... -- Связывание имен в функции, определяет (+)
-- Эквивалентно   (+) x 1 = ...

  (x + 1) = ... -- Связывание имен в образце, определяет x

  (x + 1) * y = ... -- Связывание имен в функции, определяет (*)
-- Эквивалентно   (*) (x+1) y = ...

  (x + 1) y = ... -- Связывание имен в функции, определяет (+)
-- Эквивалентно   (+) x 1 y = ...

Первые два связывания имен можно различить, потому что связывание имен в образце имеет в левой части pat0, а не pat, связывание имен в первом примере не может быть n+k-образцом без скобок.

4.5  Статическая семантика связываний имен в функциях и образцах

В этом разделе рассматривается статическая семантика связываний имен в функциях и образцах в let-выражении или инструкции where.

4.5.1  Анализ зависимостей

Вообще статическая семантика задается обычными правилами вывода Хиндли-Милнера (Hindley-Milner). Преобразование на основе анализа зависимостей --- первое, что выполняется для того, чтобы расширить полиморфизм. Две переменные, связанные посредством объявлений со значениями, находятся в одной группе объявлений, если

  1. они связаны одним и тем же связыванием имен в образце или
  2. их связывания имен взаимно рекурсивны (возможно, посредством некоторых других объявлений, которые также являются частью группы).
Применение следующих правил служит причиной того, что каждая let- или where-конструкция (включая where-конструкцию, которая задает связывание имен верхнего уровня в модуле) связывает переменные лишь одной группы объявлений, охватывая, таким образом, необходимый анализ зависимостей: (Сходное преобразование описано в книге Пейтона Джонса (Peyton Jones) [10].)
  1. Порядок объявлений в where / let-конструкциях несущественен.
  2. let {d1d2} in e = let {d1} in (let {d2} in e)
    (когда нет идентификатора, связанного в d2, d2 является свободным в d1)

4.5.2  Обобщение

Система типов Хиндли-Милнера (Hindley-Milner) устанавливает типы в let-выражении в два этапа. Сначала определяется тип правой части объявления, результатом является тип без использования квантора всеобщности. Затем все переменные типа, которые встречаются в этом типе, помещаются под квантор всеобщности, если они не связаны со связанными переменными в окружении типа; это называется обобщением. В заключение определяется тип тела let-выражения.

Например, рассмотрим объявление

  f x = let g y = (y,y)
        in ...


Типом определения g является a ->(a,a). На шаге обобщения g будет приписан полиморфный тип forall a. a ->(a,a), после чего можно переходить к определению типа части "...".

При определении типа перегруженных определений все ограничения на перегрузки из одной группы объявлений собираются вместе для того, чтобы создать контекст для типа каждой переменной, объявленной в группе. Например, в определении

  f x = let g1 x y = if x>y then show x else g2 y x
            g2 p q = g1 q p
        in ...

Типом определений g1 и g2 является a ->a ->String, а собранные ограничения представлют собой Ord a (ограничение, возникшее из использования >) и Show a (ограничение, возникшее из использования show). Переменные типа, встречающиеся в этой совокупности ограничений, называются переменными ограниченного типа.

На шаге обобщения g1 и g2 будет приписан тип

forall a. (Ord a, Show a) =>a ->a ->String

Заметим, что g2 перегружен так же, как и g1, хотя > и show находятся в определении g1.

Если программист укажет явные сигнатуры типов для более чем одной переменной в группе оъявлений, контексты этих сигнатур должны быть идентичны с точностью до переименования переменных типа.

4.5.3  Ошибки приведения контекста

Как сказано в разделе 4.1.4, контекст типа может ограничивать только переменную типа или применение переменной типа одним или более типами. Следовательно, типы, полученные при обобщении, должны иметь вид, в котором все ограничения контекста приведены к этой "главной нормальной форме". Рассмотрим, к примеру, определение

  f xs y  =  xs == [y]


Его типом является

  f :: Eq a => [a] -> a -> Bool

а не

  f :: Eq [a] => [a] -> a -> Bool

Даже если равенство имеет место в типе списка, перед обобщением необходимо упростить контекст, используя объявление экземпляра для Eq на списках. Если в области видимости нет такого экземпляра --- возникнет статическая ошибка.

Рассмотрим пример, который показывает необходимость ограничения вида C (m t), где m --- одна из переменных типа, которая подвергается обобщению, то есть где класс C применяется к выражению с типами, которое не является переменной типа или конструктором типа. Рассмотрим

  f :: (Monad m, Eq (m a)) => a -> m a -> Bool
  f x y = return x == y

Типом return является Monad m => a -> m a, типом(==) является Eq a => a -> a -> Bool. Следовательно, типом f должен являться (Monad m, Eq (m a)) => a -> m a -> Bool, и контекст не может быть более упрощен.

Объявление экземпляра, полученное из инструкции deriving типа данных (см. раздел 4.3.3) должно, как любое объявление экземпляра, иметь простой контекст, то есть все ограничения должны иметь вид C a, где a --- переменная типа. Например, в типе

  data Apply a b = App (a b)  deriving Show

выведенный экземпляр класса Show создаст контекст Show (a b), который нельзя привести и который не является простым контекстом, поэтому возникнет статическая ошибка.

4.5.4  Мономорфизм

Иногда невозможно выполнить обобщение над всеми переменными типа, используемыми в типе определения. Например, рассмотрим объявление

  f x = let g y z = ([x,y], z)
        in ...

В окружении, где x имеет тип a, типом определения g является a ->b ->([a],b). На шаге обобщения g будет приписан тип forall b. a ->b ->([a],b); только b можно поставить под квантор всеобщности, потому что a встречается в окружении типа. Мы говорим, что тип g является мономорфным по переменной типа a.

Следствием такого мономорфизма является то, что первый аргумент всех применений g должен быть одного типа. Например, это выполняется, если "..." будет иметь тип

  (g True, g False)

(это, кстати, привело бы к тому, что x будет иметь тип Bool), но это не выполнится, если выражение будет иметь тип

  (g True, g 'c')

Вообще, говорят, что тип forall u. cx =>t является мономорфным по переменной типа a, если a является свободной в forall u. cx =>t.

Стоит отметить, что предоставляемые Haskell явные сигнатуры типов не являются достаточно мощным средством для того, чтобы выразить типы, которые включают мономорфные переменные типов. Например, мы не можем записать

  f x = let 
          g :: a -> b -> ([a],b)
          g y z = ([x,y], z)
        in ...

потому что это утверждало бы, что g является полиморфным по a и b (раздел 4.4.1). В этой программе для g можно задать сигнатуру типа, только если ее первый параметр ограничен типом, не содержащим переменные типа, например

  g :: Int -> b -> ([Int],b)

Эта сигнатура также привела бы к тому, что x должен иметь тип Int.

4.5.5  Ограничение мономорфизма

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

Ограничение мономорфизма зависит от синтаксиса связывания переменной. Вспомним, что переменная связывается посредством связывания имен в функциях или связывания имен в образцах, и что связывание имен в простом образце --- это связывание имен в образце, в котором образец состоит только из одной переменной (раздел 4.4.3).

Следующие два правила определяют ограничение мономорфизма:

Ограничение мономорфизма

Правило 1.
Мы говорим, что данная группа объявлений является неограниченной, если и только если:
(a):
каждая переменная в группе связана посредством связывания имен в функциях или посредством связывания имен в простых образцах (раздел 4.4.3.2), и
(b):
для каждой переменной в группе, которая связана посредством связывания имен в простых образцах, явно указана сигнатура типа.
Обычное ограничение полиморфизма Хиндли-Милнера (Hindley-Milner) заключается в том, что только переменные типа, которые являются свободными в окружении, могут быть подвергнуты обобщению. Кроме того, переменные ограниченного типа из группы ограниченных объявлений нельзя подвергать обобщению на шаге обобщения для этой группы. (Вспомним, что переменная типа ограничена, если она должна принадлежать некоторому классу типа, см. раздел 4.5.2.)

Правило 2.
Любые переменные мономорфного типа, которые остаются после завершения вывода типа для всего модуля, считаются неоднозначными, и разрешение неоднозначности с определением конкретных типов выполняется с использованием правил по умолчанию (раздел 4.3.4).

Обоснование

Правило 1 требуется по двум причинам, обе из них довольно тонкие.

Правило 2 требуется потому, что нет никакого иного способа предписать мономорфное использование экспортируемого связывания, кроме как выполняя вывод типов на модулях вне текущего модуля. Правило 2 устанавливает, что точные типы всех переменных, связанных в модуле, должны быть определены самим модулем, а не какими-либо модулями, которые импортируют его.

  module M1(len1) where
    default( Int, Double )
    len1 = genericLength "Здравствуйте"

  module M2 where
    import M1(len1)
    len2 = (2*len1) :: Rational

Когда вывод типа в модуле M1 закончится, len1 будет иметь мономорфный тип Num a => a (по Правилу 1). Теперь Правило 2 усатанавливает, что переменная мономорфного типа a является неоднозначной, и неоднозначность должна быть разрешена путем использования правил по умолчанию раздела 4.3.4. Поэтому len1 получит тип Int, и его использование в len2 является неправильным из-за типа. (Если вышеупомянутый код в действительности именно то, что требуется, то сигнатура типа для len1 решила бы проблему.)

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

Следствия

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

  f x y = x+y


функция f может использоваться при любой перегрузке в классе Num. Здесь нет никакой опасности перевычисления. Тем не менее, та же функция, определенная с использованием синтаксиса образца

  f = \x -> \y -> x+y

требует указания сигнатуры типа, если f должна быть полностью перегружена. Многие функции наиболее естественно определяются посредством использования связывания имен в простых образцах; пользователь должен быть внимателен, добавляя к ним сигнатуры типов, чтобы сохранить полную перегрузку. Стандартное начало (Prelude) содержит много таких примеров:


  sum  :: (Num a) => [a] -> a
  sum  =  foldl (+) 0  

Правило 1 применяется к определениям верхнего уровня и к вложенным определениям. Рассмотрим пример:

  module M where
    len1 = genericLength "Здравствуйте"
    len2 = (2*len1) :: Rational

Здесь с помощью вывода типа устанавливаем, что len1 имеет мономорфический тип (Num a => a); при выполнении вывода типа для len2 определяем, что переменная типа a имеет тип Rational.

4.6  Вывод вида

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

Первый шаг в процессе вывода вида заключается в разделении набора определений типов данных, синонимов и классов на группы зависимостей. Этого можно достичь почти таким же способом, как анализ зависимостей для объявлений значений, который был описан в разделе 4.5. Например, следующий фрагмент программы включает определение конструктора типа данных D, синонима S и класса C, все они будут включены в одну группу зависимостей:

  data C a => D a = Foo (S a)
  type S a = [D a]
  class C a where
      bar :: a -> D a -> Bool

Виды, к которым относятся переменные, конструкторы и классы в пределах каждой группы, определяются с использованием стандартных методов вывода типа и сохраняющей вид унификации (объединения) [7]. Например, в приведенном выше определении параметр a является аргументом конструктора функции (->) в типе bar и поэтому должен относиться к виду *. Из этого следует, что и D, и S должны относиться к виду *->* и что каждый экземпляр класса C должен относиться к виду *.

Возможно, что некоторые части выведенного вида не могут быть полностью определены исходя из соответствующих определений; в таких случаях принимается значение по умолчанию вида *. Например, мы могли принять произвольный вид k для параметра a в каждом из следующих примеров:

  data App f a = A (f a)
  data Tree a  = Leaf | Fork (Tree a) (Tree a)

Тогда мы получили бы виды (k->*) ->k->* и k->* соответственно для App и Tree для любого вида k. Это также потребовало бы, чтобы расширение допускало полиморфные виды. Вместо этого, используя по умолчанию связывание k= *, действительными видами для этих двух конструкторов являются соответственно (*->*) ->*->* и *->*.

Значения по умолчанию применяются к каждой группе зависимостей, независимо от того, как конкретные константы конструктора типа или классов используются в более поздних группах зависимостей или где-либо в другом месте в программе. Например, добавление следующего определения к приведенным выше не влияет на вид, выведенный для Tree (путем изменения его на (*->*) ->*, например), и вместо этого приводит к статической ошибке, потому что вид, которому принадлежит [], *->*, не соответствует виду *, который ожидается для аргумента Tree:

  type FunnyTree = Tree []     -- неправильно

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


Описание Haskell 98
наверх | назад | вперед | содержание | предметный указатель функций
Декабрь 2002