05. Функторы

Контейнерные структуры данных

В предыдущих главах мы познакомились с некоторыми структурами данных:

data [a] = [] | a : [a] -- это псевдокод, Haskell не разрешает такой синтаксис
data Maybe a = Nothing | Just a
data Tree a = Leaf | Node (Tree a) a (Tree a)

Все эти структуры данных объединяет одно общее свойство — они представляют различные контейнеры. Перечисленные структуры различаются расположением элементов и «ёмкостью». Аналогичным образом мы могли бы определить и другие контейнеры:

data MultiTree a = Leaf | Node a [MultiTree a]
data Stream = Cons a (Stream a)
data OneOrTwo a = One a | Two a a

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

Как вы помните, классы типов призваны выносить общий интерфейс типов данных. Функцию map в общем виде, как функцию, преобразующую каждый элемент структуры, не меняя саму структуру, вполне можно вынести в класс типов:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Типы, к которым применима обобщенная функция map, называются функторами. Заметьте, что сигнатура типа функции fmap очень похожа на сигнатуру функции map:

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

Разница заключается в том, что конкретный конструктор типа «список» заменен на общий конструктор типа f.

Рассмотрим реализацию функции fmap для некоторых структур данных:

instance Functor Maybe where
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

instance Functor Tree where
    fmap _ Leaf = Leaf
    fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

Упражнения

5.1 Попробуйте самостоятельно написать реализацию класса типов Functor для следующих типов:

data MultiTree a = Leaf | Node a [MultiTree a]
data Stream a = Cons a (Stream a)

Контекст вычислений

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

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

sub :: (Num t) => Maybe t -> Maybe t -> Maybe t
sub (Just x) (Just y) = Just (x + y)
sub _ _ = Nothing

div :: (Num t) => Maybe t -> Maybe t -> Maybe t
div _ (Just 0) = Nothing
div (Just x) (Just y) = Just (x / y)
div _ _ = Nothing

-- решение уравнения y = kx + b относительно x
solve :: (Num t) => Maybe t -> Maybe t -> Maybe t -> Maybe t
solve k x b = (sub y b) `div` k

В этом примере функтор Maybe используется как своеобразный контекст для вычислений, которые могут завершиться неудачно: Nothing сигнализирует об ошибке в вычислениях (например, делении на ноль), Just — о нормальном ходе вычислений. При этом, если возникла ошибка, программа не «падает», а вернет Nothing вместо ответа. Таким образом, ошибки в этом контексте являются в некоторой степени контролируемыми. Аналогичным образом, список может быть интерпретирован как контекст недетерминированных вычислений.

Рассмотрим несколько примеров, когда рассуждать о функторе, как о контейнере, не очень удобно. Для начала, рассмотрим тип ((->) e). Этот тип можно воспринимать, как каррированный тип функции: (e ->). В качестве контейнера тип (e -> a) может быть интерпретирован, как множество (возможно, бесконечное) значений типа a, которые индексируются значениями типа e. Однако, гораздо проще рассуждать об этом типе, как о контексте вычислений с окружением типа e, доступным для чтения. Рассмотрим реализацию класса Functor для этого типа:

instance Functor ((->) e) where
    fmap f g = f . g

Действительно, значение типа (e -> a) должно преобразоваться в значение типа (e -> b). Если бы нам был известен контекст x, то (g x) было бы значением, заключенным в наш функтор, а (f (g x)) — было бы значением, заключенным в результат применения функции fmap. Соответственно, (\x -> f (g x)) — это сам результат применения функции fmap. Но это то же самое, что и (f . g).

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

  • Either e — контекст вычислений, которые могут завершиться ошибкой. Значение типа Either e a представляет собой контейнер, содержащий либо значение типа a, либо ошибку типа e. Функтор очень похож на функтор Maybe. Отличие в том, что Maybe в случае ошибки в вычислениях не может нести никакую информацию о самой ошибке.
  • ((,) e) — контекст вычислений с «аннотациями». Значение типа (e, a) представляет собой контейнер, содержащий значение типа a и аннотацию типа e.

Упражнения

5.2. Напишите реализацию функтора для конструктора типов Either e.

6.3. Напишите реализацию функтора для конструкторов ((,) e) и Pair:

    data Pair a = Pair a a

В чем сходство и отличие этих двух конструкторов?

6.4. ★ Приведите пример конструктора типов вида (* -> *), для которого невозможно написать реализацию функтора.

Законы

Несмотря на то, что Haskell способен проверять множество логических ошибок на этапе компиляции, некоторые вещи все равно находяться на совести программиста. В случае в функторами, Haskell будет проверять только соответствие реализации функции fmap её типу. Но правильная реализация функтора должна также удовлетворять следующим законам:

fmap id      == id
fmap (g . h) == fmap g . fmap h

Соблюдение этих законов гарантирует, что структура контейнера/контекста не изменяется.

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

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

-- некорректная реализация
instance Functor [] where
    fmap _ [] = []
    fmap g (x:xs) = g x : g x : fmap g xs

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

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

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

Упражнения

6.5. ★★ Хотя реализация не может удовлетворять первому закону и не удовлетворять второму, обратное возможно. Приведите пример некорректной реализации функтора, нарушающей первый закон, но не нарушающей второй.

Понимание функторов

Как уже говорилось выше, распространены два способа интерпретации функторов:

  • f a — это набор значений типа a, помещенные в контейнер f.
  • f a — это значение типа a в контексте f.

Вспомним, что как и все функции от нескольких агрументов в Haskell, fmap является каррированной. Подчеркнем это в сигнатуре типа:

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

Из такой сигнатуры понятно, что fmap преобразует функцию над значениями в функцию над контейнерами/контекстами. Такое преобразование часто называется подъемом (lift). Таким образом, функция fmap «поднимает» функцию из «мира значений» в «мир функтора f».

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

Упражнения

6.6. ★★ Является ли композиция функторов также функтором? Если нет — приведите контрпример. Если да — приведите соответствующий код на Haskell.

6.7. ★★★ Напишите реализацию функтора для следующих конструкторов типов и предложите свою интерпретацию:

data S e a = e -> (a, e)
data C r a = C ((a -> r) -> r)