Сорта и немного тип-фу

Конструкторы типов принимают другие типы в качестве параметров для того, чтобы рано или поздно вернуть конкретный тип. Это в некотором смысле напоминает мне функции, которые принимают значения в качестве параметров для того, чтобы вернуть значение. Мы видели, что конструкторы типов могут быть частично применены, так же как и функции (Either String – это тип, который принимает ещё один тип и возвращает конкретный тип, например, Either String Int). Это очень интересно. В данном разделе мы рассмотрим формальное определение того, как типы применяются к конструкторам типов. Точно так же мы выясняли, как формально определяется применение значений к функциям по декларациям типов. Вам не обязательно читать этот раздел для того, чтобы продолжить своё волшебное путешествие в страну языка Haskell, и если вы не поймёте, что здесь изложено, – не стоит сильно волноваться. Тем не менее, если вы усвоили содержание данного раздела, это даст вам чёткое понимание системы типов.

Итак, значения, такие как 3, "ДА" или takeWhile (функции тоже являются значениями, поскольку мы можем передать их как параметр и т. д.), имеют свой собственный тип. Типы – это нечто вроде маленьких меток, привязанных к значениям, чтобы мы могли строить предположения относительно них. Но и типы имеют свои собственные маленькие меточки, называемые сортами. Сорт – это нечто вроде «типа типов». Звучит немного странно, но на самом деле это очень мощная концепция.

Что такое сорта и для чего они полезны? Давайте посмотрим сорт типа, используя команду :k в интерпретаторе GHCi.

ghci> :k Int

Int :: *

Звёздочка? Как затейливо! Что это значит? Звёздочка обозначает, что тип является конкретным. Конкретный тип – это такой тип, у которого нет типов-параметров; значения могут быть только конкретных типов. Если бы мне надо было прочитать символ * вслух (до этого не приходилось), я бы сказал «звёздочка» или просто «тип».

О’кей, теперь посмотрим, каков сорт у типа Maybe:

ghci> :k Maybe

Maybe :: * –> *

Конструктор типов Maybe принимает один конкретный тип (например, Int) и возвращает конкретный тип (например, Maybe Int). Вот о чём говорит нам сорт. Точно так же тип Int –> Int означает, что функция принимает и возвращает значение типа Int; сорт * – > * означает, что конструктор типов принимает конкретный тип и возвращает конкретный тип. Давайте применим параметр к типу Maybe и посмотрим, какого он станет сорта.

ghci> :k Maybe Int

Maybe Int :: *

Так я и думал! Мы применили тип-параметр к типу Maybe и получили конкретный тип. Можно провести параллель (но не отождествление: типы – это не то же самое, что и сорта) с тем, как если бы мы сделали :t isUpper и :t isUpper 'A'. У функции isUpper тип Char –> Bool; выражение isUpper 'A' имеет тип Bool, потому что его значение – просто False. Сорт обоих типов, тем не менее, *.

Мы используем команду :k для типов, чтобы получить их сорт, так же как используем команду :t для значений, чтобы получить их тип. Выше уже было сказано, что типы – это метки значений, а сорта – это метки типов; и в этом они схожи.

Посмотрим на другие сорта.

ghci> :k Either

Either :: * –> * –> *

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

ghci> :k Either String

Either String :: * –> *

ghci> :k Either String Int

Either String Int :: *

Когда нам нужно было сделать для типа Either экземпляр класса Functor, пришлось частично применить его, потому что класс Functor принимает типы только с одним параметром, в то время как у типа Either их два. Другими словами, класс Functor принимает типы сорта * –> *, и нам пришлось частично применить тип Either для того, чтобы получить сорт * –> * из исходного сорта * –> * –> *. Если мы посмотрим на определение класса Functor ещё раз:

class Functor f where

   fmap :: (a –> b) –> f a –> f b

то увидим, что переменная типа f используется как тип, принимающий один конкретный тип для того, чтобы создать другой. Мы знаем, что возвращается конкретный тип, поскольку он используется как тип значения в функции. Из этого можно заключить, что типы, которые могут «подружиться» с классом Functor, должны иметь сорт * –> *.

Ну а теперь займёмся тип-фу. Посмотрим на определение такого класса типов:

class Tofu t where

   tofu :: j a –> t a j

Объявление выглядит странно. Как мы могли бы создать тип, который будет иметь экземпляр такого класса? Посмотрим, каким должен быть сорт типа. Так как тип j a используется как тип значения, который функция tofu принимает как параметр, у типа j a должен быть сорт *. Мы предполагаем сорт * для типа a и, таким образом, можем вывести, что тип j должен быть сорта * –> *. Мы видим, что тип t также должен производить конкретный тип, и что он принимает два типа. Принимая во внимание, что у типа a сорт * и у типа j сорт * –> *, мы выводим, что тип t должен быть сорта * –> (* –> *) –> *. Итак, он принимает конкретный тип (a) и конструктор типа, который принимает один конкретный тип (j), и производит конкретный тип. Вау!

Хорошо, давайте создадим тип такого сорта: * –> (* –> *) –> *. Вот один из вариантов:

data Frank a b = Frank {frankField :: b a} deriving (Show)

Откуда мы знаем, что этот тип имеет сорт * –> (* –> *) – > *? Именованные поля в алгебраических типах данных сделаны для того, чтобы хранить значения, так что они по определению должны иметь сорт *. Мы предполагаем сорт * для типа a; это означает, что тип b принимает один тип как параметр. Таким образом, его сорт – * –> *. Теперь мы знаем сорта типов a и b; так как они являются параметрами для типа Frank, можно показать, что тип Frank имеет сорт * –> (* –> *) – > *. Первая * обозначает сорт типа a; (* –> *) обозначает сорт типа b. Давайте создадим несколько значений типа Frank и проверим их типы.

ghci> :t Frank {frankField = Just "ХА-ХА"}

Frank {frankField = Just "ХА-ХА"} :: Frank [Char] Maybe

ghci> :t Frank {frankField = Node 'a' EmptyTree EmptyTree}

Frank {frankField = Node 'a' EmptyTree EmptyTree} :: Frank Char Tree

ghci> :t Frank {frankField = "ДА"}

Frank {frankField = "ДА"} :: Frank Char []

Гм-м-м… Так как поле frankField имеет тип вида a b, его значения должны иметь типы похожего вида. Например, это может быть Just "ХА-ХА", тип в этом примере – Maybe [Char], или ['Д','А'] (тип [Char]; если бы мы использовали наш собственный тип для списка, это был бы List Char). Мы видим, что значения типа Frank соответствуют сорту типа Frank. Сорт [Char] – это *, тип Maybe имеет сорт * –> *. Так как мы можем создать значение только конкретного типа и тип значения должен быть полностью определён, каждое значение типа Frank имеет сорт *.

Сделать для типа Frank экземпляр класса Tofu довольно просто. Мы видим, что функция tofu принимает значение типа a j (примером для типа такой формы может быть Maybe Int) и возвращает значение типа t a j. Если мы заменим тип Frank на t, результирующий тип будет Frank Int Maybe.

instance Tofu Frank where

   tofu x = Frank x

Проверяем типы:

ghci> tofu (Just 'a') :: Frank Char Maybe

Frank {frankField = Just 'a'}

ghci> tofu ["ПРИВЕТ"] :: Frank [Char] []

Frank {frankField = ["ПРИВЕТ"]}

Пусть и без особой практической пользы, но мы потренировали наше понимание типов. Давайте сделаем ещё несколько упражнений из тип-фу. У нас есть такой тип данных:

data Barry t k p = Barry { yabba :: p, dabba :: t k }

Ну а теперь определим для него экземпляр класса Functor. Класс Functor принимает типы сорта * –> *, но непохоже, что у типа Barry такой сорт. Каков же сорт у типа Barry? Мы видим, что он принимает три типа-параметра, так что его сорт будет похож на (нечто –> нечто –> нечто –> *). Наверняка тип p – конкретный; он имеет сорт *. Для типа k мы предполагаем сорт *; следовательно, тип t имеет сорт * –> *. Теперь соединим всё в одну цепочку и получим, что тип Barry имеет сорт (* –> *) –> * –> * –> *. Давайте проверим это в интерпретаторе GHCi:

ghci> :k Barry

Barry :: (* –> *) –> * –> * –> *

Ага, мы были правы. Как приятно! Чтобы сделать для типа Barry экземпляр класса Functor, мы должны частично применить первые два параметра, после чего у нас останется сорт * –> *. Следовательно, начало декларации экземпляра будет таким:

instance Functor (Barry a b) where

Если бы функция fmap была написана специально для типа Barry, она бы имела тип

fmap :: (a –> b) –> Barry c d a –> Barry c d b

Здесь тип-параметр f просто заменён частично применённым типом Barry c d. Третий параметр типа Barry должен измениться, и мы видим, что это удобно сделать таким образом:

instance Functor (Barry a b) where

   fmap f (Barry {yabba = x, dabba = y}) = Barry {yabba = f x, dabba = y}

Готово! Мы просто отобразили тип f по первому полю.

В данной главе мы хорошенько изучили, как работают параметры типов, и как они формализуются с помощью сортов по аналогии с тем, как формализуются параметры функций с помощью декларации типов. Мы провели любопытные параллели между функциями и конструкторами типов, хотя на первый взгляд они и не имеют ничего общего. При реальной работе с языком Haskell обычно не приходится возиться с сортами и делать вывод сортов вручную, как мы делали в этой главе. Обычно вы просто частично применяете свой тип к сорту * –> * или * при создании экземпляра от одного из стандартных классов типов, но полезно знать, как это работает на самом деле. Также интересно, что у типов есть свои собственные маленькие типы.

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