Миран Липовача - Изучай Haskell во имя добра!

Nothing

ghci> fmap (*2) (Just 200)

Just 400

ghci> fmap (*2) Nothing

Nothing

Ещё один тип, который можно отображать и сделать для него экземпляр класса Functor, – это наш тип Tree. Дерево может хранить ноль или более других элементов, и конструктор типа Treeпринимает один тип-параметр. Если бы мы хотели записать функцию fmapтолько для типа Tree, её сигнатура выглядела бы так: (a –> b) –> Tree a –> Tree b.

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

instance Functor Tree where

fmap f EmptyTree = EmptyTree

fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

Проверим:

ghci> fmap (*2) EmptyTree

EmptyTree

ghci> fmap (*4) (foldr treeInsert EmptyTree [5,7,3])

Node 20 (Node 12 EmptyTree EmptyTree) (Node 28 EmptyTree EmptyTree)

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

Отлично! Ну а теперь как насчёт 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 a– только один. Если бы функция 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'.

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

Попытайтесь самостоятельно догадаться, как для типа 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и посмотрим, какого он станет сорта.