Приглашаю всех любознательных новичков, как и я, на прогулку по классам^[В данном случае термины класс и экземляр, разумеется, не имеют ничего общего с созвучными терминами из объектно-ориентированного программирования.] типов стандартной библиотеки языка Haskell. На wiki сообщества хакеров Haskell есть страница Typeclassopedia, в которой подробно рассказывается про самые фундаментальные классы языка, приводятся интересные примеры интуиции (метафор, которыми можно понимать для себя тот или иной класс), а также даются полезные упражнения.

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

Начнём наше путешествие по дивному саду с класса Functor.

Functor⌗

Класс Functor – один из самых фундаментальных классов. Представляет собой вычислительный контекст. Экземпляр^[Являться экземпляром класса типов значит реализовывать необходимый и достаточный интерфейс этого ласса] класса Functor является в некотором роде контейнером, к элементам внутри которого можно равномерно применять некоторую функцию.

Определение⌗ 

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

  (<$) :: a -> f b -> f a
  (<$) = fmap . const

Как видно из сигнатуры fmap, тип f, претендующий на звание функтора, это не конкретный тип вроде Int, а тип рода * -> *, то есть унарный конструктор типов вроде Maybe (не существует значений типа Maybe, а есть значения типа Maybe Int) или [] (не существует значений типа [], но есть значения типа [] Int или, в снитаксическом сахаре, [Int]).

Например, полиморфический тип обыкновенного списка [] – это функтор, поэтому мы можем применять функцию к его содержимому:

> fmap (+ 100) [1, 2, 3, 4]
[101, 102, 103, 104]

Как нетрудно догадаться, реализация fmap для списка соответствует функции map над списками.

Труднее но полезнее думать о списке как о вычислительном контексте с недетерминированным результатом, то есть при выполнении принимающим сразу все значения одновременно. Функтор Maybe при этом представляет собой контекст, вычисление в котором может произойти (вычислиться в Just a) или не произойти вовсе (то есть вычислиться в Nothing). Например, стандартная функция lookup над списками производит поиск значения по указанному ключу и выдаёт результат в таком контексте Maybe (указанного ключа в списке может и не существовать, отсюда и негарантированность вычисления). Рождественские скидки на фрукты:

> fmap christmasSale $ lookup "apple" [("orange", 36), ("apple", 32), ("banana", 24)]
Just 28.8
> fmap christmasSale $ lookup "peach" [("orange", 36), ("apple", 32), ("banana", 24)]
Nothing
> fmap (christmasSale . snd) [("orange", 36), ("apple", 32), ("banana", 24)]
[32.4,28.8,21.6]

Нетрудно догадаться, что реализация fmap для Functor Maybe представляет собой применение заданной функции к значению a, если результат контекста Just a и возвращение Nothing без какого-либо применения, если в контексте Nothing.

Ту же самую функцию можно применить и к другому контексту (функтору []); сама функция при этом ничего не знает и не должна знать об устройстве этого контейнера. По сути, fmap как-бы втягивает функцию в контейнер и применяет к содержимому. Это допустимо лишь если совпадёт тип входного параметра функции и тип внутри контейнера, что очевидно из сигнатуры.

Функторы⌗

Функторы из Prelude стандартной библиотеки:

instance Functor (Either a) -- Defined in ‘Data.Either’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
instance Functor IO -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base’
instance Functor ((,) a) -- Defined in ‘GHC.Base’

Меня особенно возбуждают последние два функтора.

Тип ((->) r) (иначе записывается как r ->) представляет собой тип функций, которые принимают параметр типа r. Конкретный же тип ((->) r a) (иначе записывается r -> a) таким образом представляет собой тип всевозможных функций из значений типа r в значения типа a (т.н. функциональное пространтсво), то есть все возможные способы индексировать значения a значениями r. Как вычислительный контекст, интуитивно, Functor ((->) r) представляет из себя некоторое окружение, в котором значение типа r доступно вычисляемой сущности для чтения (консультации). Например, можно представить, как (Int ->) предстаёт таким абстрактным контекстом, где для “консультации” всегда будет доступно значение типа Int, то есть некоторое число (как входной параметр): тип (Int -> Char) обыкновенных функций из чисел в символы ASCII, фактически, есть не что иное, как символы, помещённые в такой вычислительный контекст.

Крутейшим образом реализован fmap для Functor ((->) r) (на самом деле это упражнение). Вот мой вариант:

instance Functor ((->) r) where
  fmap :: (a -> b) -> (r -> a) -> (r -> b)
  fmap fromAtoB ctxWithR = fromAtoB . ctxWithR

Выполнение вычисления в “окружении r” есть обыкновенная композиция функций (в Haskell обозначается .)! Довольно тривиальный пример:

> let ctx = (* 2) -- контекст "умножения всего на два"
> let f x = 100 - x -- обычная функция над числом (вычитаем его из ста)

> ctx 3 -- помещаем тройку в контекст
6

> (fmap f ctx) 3 -- втягиваем функцию в контекст
94

> fmap f ctx 3 == (f . ctx) 3
True

Тип ((,) e) представляет собой контейнер с аннотацией, который наряду со своим полезным содержимом (может быть, некоторого типа a), обязательно содержит “аннотацию” типа e. Интересно, что таким образом в Haskell осмысливаются гетерогенные пары вроде ("john", 65536), которые являются одним из базовых типов языка. Кстати, запись ((,) e), по аналогии выше, можно представлять себе как неграмматичное в стандартном языке (e, ). Собственно, обычные пары вроде (123, False) на самом деле конструируются (,) 123 False.

Одно из упражнений ниже предлагает сделать ((,) e) функтором. Элементарно:

instance Functor ((,) e) where
  fmap f ((,) e c) = (,) e (f c)

То есть fmap применяет функцию к содержимому, не нарушая аннотации контейнера.

> fmap (+100) (3, 29)
(3,129)

Упражнения⌗

1. Implement Functor instances for Either e and ((->) e).⌗

Напомню определение типа Either (контейнера, который может содержать либо значение типа a, либо значение типа b):

data Either a b = Left a | Right b 	-- Defined in ‘Data.Either’

Этот тип часто используется для сигнализации некоторой сбойной ситуации (но в отличии от Maybe могут нести причину сбоя), при этом значения, построенные конструктором Left, считаются неординарными. Втягиваем функцию только если был использован конструктор Right:

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

Тривиально.

2. Implement Functor instances for ((,) e) and for Pair, defined as⌗ 

data Pair a = Pair a a

Explain their similarities and differences.

Просто,

instance Functor ((,) e) where
  fmap f ((,) e c) = (,) e (f c)

instance Functor Pair where
  fmap f (Pair a b) = Pair (f a) (f b)

Мы видим, что первый функтор сохраняет первый элемент пары (аннотацию), в то время как второй трактует пару равноправно и применяет функцию к обеим элементам. При некоторой похожести на первый взгляд, у них разная семантика: оба типа данных хранят пару элементов ((,) a b гетерогенен, Pair a гомогенен), но приведённые определения функторов вкладывают разные смыслы в понятия вычислительного контекста.

3. Implement a Functor instance for the type ITree, defined as⌗ 

data ITree a = Leaf (Int -> a) 
             | Node [ITree a]

Заметим, что аргумент в конструкторе Leaf – функтор (см. Пункт 1). Аргумент в конструкторе Node тоже функтор (список), внутри которого помещён тип нашего дерева ITree a, т.е. определение данного типа данных рекурсивно (правая часть ссылается на левую часть).

Математическая индукция: пусть мы определили fmap над деревом из конструктора Leaf, тогда fmap над конструктором Node есть применение fmap к каждому дереву из списка (по определению типа ITree). Но списки суть функторы; мы имеем три разных вычислительных контекста с единым интерфейсом тайпкласса Functor:

instance Functor ITree where
  fmap f (Leaf x) = Leaf $ fmap f x
  fmap f (Node x) = Node $ fmap (fmap f) x

fmap для списков – это синоним map. В нашей реализации видно, как функторы вкладываются друг в друга. Что может быть приятнее?

4. Give an example of a type of kind * -> * which cannot be made an instance of Functor (without using undefined).⌗

Такой тип должен иметь какие-либо ограничения на параметрический полиморфизм в определении типа. Например, функтором не может стать “список поверх чисел” ниже:

{-# LANGUAGE DatatypeContexts #-}

data Num a => List a = End | Cons a (List a) deriving Show

instance Functor List where
  fmap f End = End
  fmap f (Cons a as) = Cons (f a) (fmap f as) -- но в сигнатуре fmap только абстрактные типы!

    No instance for (Num a) arising from a use of ‘Cons’
    Possible fix:
      add (Num a) to the context of
        the type signature for fmap :: (a -> b) -> List a -> List b
    In the pattern: Cons a as
    In an equation for ‘fmap’:
        fmap f (Cons a as) = Cons (f a) (fmap f as)
    In the instance declaration for ‘Functor List’

Не получится также сделать функтором следующий странный тип:

data Flip a b = Flip b a

Функция fmap не должна менять структуру контекста, но любое конструирование типа данных выше, фактически, это делает. Если кто-нибудь сможет дать лучшее объяснение или даже опровергнуть моё утверждение, то пожалуйста напишите мне.

5. Is this statement true or false?⌗

The composition of two Functors is also a Functor.

If false, give a counterexample; if true, prove it by exhibiting some appropriate Haskell code.

Если честно, то мне не совсем понятно, что автор имеет в виду под “композицией функторов”… Если речь идёт о двух функторах f1 a и f2 (f1 a), то, разумеется, такая композиция будет функтором в силу определения композиции и того факта, что функторы не могут менять своей структуры.