И тип Either является функтором

↑

▷ Содержание

⇐ ПредыдущаяСтр 20 из 60Следующая ⇒

Отлично! Ну а теперь как насчёт Either a b? Можно ли сделать его функтором? Класс типов Functor требует конструктор типов с од- ним параметром, а у типа Either их два. Гм-м... Придумал – мы час- тично применим конструктор Either, «скормив» ему один пара- метр, и таким образом он получит один свободный параметр. Вот как для типа Either определён экземпляр класса Functor в стандарт- ных библиотеках:

instance Functor (Either a) where fmap f (Right x) = Right (f x) fmap f (Left x) = Left x

Что же здесь происходит? Как видно из записи, мы сделали экземпляр класса не для типа Either, а для Either a. Это потому, что Either – конструктор типа, который принимает два парамет- ра, а Either а – только один. Если бы функция fmap была только для Either a, сигнатура типа выглядела бы следующим образом:

(b –> c) –> Either a b –> Either a c

поскольку это то же самое, что

(b –> c) –> (Either a) b –> (Either a) c

В реализации мы выполняем отображение в конструкторе дан- ных Right, но не делаем этого в Left. Почему? Вспомним, как опре- делён тип Either a b:

data Either a b = Left a | Right b

Если мы хотим применять некую функцию к обеим альтернати- вам, параметры a и b должны конкретизироваться одним и тем же типом. Если попытаться применить функцию, которая принимает строку и возвращает строку, то b у нас – строка, а a – число; это не сработает. Также, когда мы смотрели на тип функции fmap для типа Either a, то видели, что первый параметр не изменяется, а второй может быть изменён; первый параметр актуализируется конструк- тором данных Left.

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

Отображения из модуля Data.Map также можно сделать функто- ром, потому что они хранят (или не хранят) значения. Для типа Map k v функция fmap будет применять функцию v –> v' на отображе- нии типа Map k v и возвращать отображение типа Map k v'.

ПРИМЕЧАНИЕ. Обратите внимание: апостроф не имеет специ- ального значения в типах (как не имеет его и в именовании зна- чений). Этот символ используется для обозначения cхожих поня- тий, незначительно отличающихся друг от друга.

Попытайтесь самостоятельно догадаться, как для типа Map k оп- ределён экземпляр класса Functor!

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

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

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

функции, которые принимают значения в качестве параметров для того, чтобы вернуть значение. Мы видели, что конструкторы типов могут быть частично при- менены, так же как и функции (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 а используется как тип зна- чения, который функция tofu принимает как параметр, у типа j a должен быть сорт *. Мы предполагаем сорт * для типа а и, таким образом, можем вывести, что тип j должен быть сорта * –> *. Мы видим, что тип t также должен производить конкретный тип, и что он принимает два типа. Принимая во внимание, что у типа a сорт * и у типа j сорт * –> *, мы выводим, что тип t должен быть сорта * –> (* –> *) –> *. Итак, он принимает конкретный тип (а) и конструктор типа, который принимает один конкретный тип (j), и производит конкретный тип. Вау!

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

Вот один из вариантов:

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

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

–> *) – > *. Первая * обозначает сорт типа а; (* –> *) обозначает сорт типа 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 имеет тип вида а 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.

ВВОД-ВЫВОД

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману