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

Нет лучшего способа изучить класс типов Functor, чем посмотреть, как он реализован. Вот и посмотрим:

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

Итак, что у нас имеется? Класс определяет одну функцию fmap и не предоставляет для неё реализации по умолчанию. Тип функции fmap весьма интересен. Во всех вышеприведённых определениях классов типов тип-параметр, игравший роль типа в классе, был некоторого конкретного типа, как переменная a в сигнатуре (==) :: (Eq a) => a –> a –> Bool. Но теперь тип-параметр f не имеет конкретного типа (нет конкретного типа, который может принимать переменная, например Int, Bool или Maybe String); в этом случае переменная – конструктор типов, принимающий один параметр. (Напомню: выражение Maybe Int является конкретным типом, а идентификатор Maybe – конструктор типов с одним параметром.) Мы видим, что функция fmap принимает функцию из одного типа в другой и функтор, применённый к одному типу, и возвращает функтор, применённый к другому типу.

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

Гм-м… что-то мне напоминает объявление функции fmap! Если вы не знаете сигнатуру функции map, вот она:

map :: (a –> b) –> [a] –> [b]

О, как интересно! Функция map берёт функцию из a в b и список элементов типа a и возвращает список элементов типа b. Друзья, мы только что обнаружили функтор! Фактически функция map – это функция fmap, которая работает только на списках. Вот как список сделан экземпляром класса Functor:

instance Functor [] where

   fmap = map

И всё! Заметьте, мы не пишем instance Functor [a] where, потому что из определения функции

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

мы видим, что параметр f должен быть конструктором типов, принимающим один тип. Выражение [a] – это уже конкретный тип (список элементов типа a), а вот [] – это конструктор типов, который принимает один тип; он может производить такие конкретные типы, как [Int], [String] или даже [[String]].

Так как для списков функция fmap – это просто map, то мы получим одинаковые результаты при их использовании на списках:

map :: (a –> b) –> [a] –> [b]

ghci>fmap (*2) [1..3]

[2,4,6]

ghci> map (*2) [1..3]

[2,4,6]

Что случится, если применить функцию map или fmap к пустому списку? Мы получим опять же пустой список. Но функция fmap преобразует пустой список типа [a] в пустой список типа [b].

Экземпляр класса Functor для типа Maybe

Типы, которые могут вести себя как контейнеры по отношению к другим типам, могут быть функторами. Можно представить, что списки – это коробки с бесконечным числом отсеков; все они могут быть пустыми, или же один отсек заполнен, а остальные пустые, или несколько из них заполнены. А что ещё умеет быть контейнером для других типов? Например, тип Maybe. Он может быть «пустой коробкой», и в этом случае имеет значение Nothing, или же в нём хранится какое-то одно значение, например "ХА-ХА", и тогда он равен Just "ХА-ХА".

Вот как тип Maybe сделан функтором:

instance Functor Maybe where

   fmap f (Just x) = Just (f x)

   fmap f Nothing = Nothing

Ещё раз обратите внимание на то, как мы записали декларацию instance Functor Maybe where вместо instance Functor (Maybe m) where – подобно тому как мы делали для класса YesNo. Функтор принимает конструктор типа с одним параметром, не конкретный тип. Если вы мысленно замените параметр f на Maybe, функция fmap работает как (a –> b) –> Maybe a –> Maybe b, только для типа Maybe, что вполне себя оправдывает. Но если заменить f на (Maybe m), то получится (a –> b) –> Maybe m a –> Maybe m b, что не имеет никакого смысла, так как тип Maybe принимает только один тип-параметр.

Как бы то ни было, реализация функции fmap довольно проста. Если значение типа Maybe – это Nothing, возвращается Nothing. Если мы отображаем «пустую коробку», мы получим «пустую коробку», что логично. Точно так же функция map для пустого списка возвращает пустой список. Если это не пустое значение, а некоторое значение, упакованное в конструктор Just, то мы применяем функцию к содержимому Just:

ghci> fmap (++ " ПРИВЕТ, Я ВНУТРИ JUST") (Just "Серьёзная штука.")

Just "Серьёзная штука. ПРИВЕТ, Я ВНУТРИ JUST"

ghci> fmap (++ " ПРИВЕТ, Я ВНУТРИ JUST") Nothing

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 является функтором

Отлично! Ну а теперь как насчёт 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 мы увидели, что классы типов могут представлять довольно мощные концепции высокого порядка. Также немного попрактиковались в частичном применении типов и создании экземпляров. В одной из следующих глав мы познакомимся с законами, которые должны выполняться для функторов.