В продолжении разговора о функторах стандартной библиотеки Haskell, подумаем над их законами.

Функториальные законы⌗

Все реализации Functor должны подчиняться следующим двум законам:

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

Первый закон очень ёмок, несмотря на кажущуюся простоту. Он говорит нам о том, что втягивание функции тождества (id a = a) в вычислительный контекст не может изменять контекст. Второй закон говорит нам о дистрибутивности fmap относительно композиции: применение одной функции внутри контекста вслед за другой – это то же самое, что применение композиции этих функций внутри контекста. На самом деле, как оказывается, из первого закона можно вывести второй.

Упражнения⌗

1. Although it is not possible for a Functor instance to satisfy the first Functor law but not the second (excluding undefined), the reverse is possible. Give an example of a (bogus) Functor instance which satisfies the second law but not the first.⌗

Мой вариант тривиален. Тем не менее, он подчиняется лишь второму функториальному закону.

data List a = End | Cons a (List a)

instance Functor List where
  fmap _ _ = End

2. Which laws are violated by the evil Functor instance for list shown above: both laws, or the first law alone? Give specific counterexamples.⌗

Неправильный функтор определён как

-- Evil Functor instance
instance Functor [] where
  fmap _ [] = []
  fmap g (x:xs) = g x : g x : fmap g xs

Лифтинг тождественной функции меняет контекст (контейнер) – он разрастается с каждым fmap. Ровно поэтому нарушен и второй функториальный закон: два fmap вставят в два раза больше лишних элементов, чем один fmap некоторой композиции g . h.

Лифтинг?⌗

Поскольку, как и все функции в Haskell, fmap каррируется и на самом деле не принимает “два аргумента”, а принимает ровно один, но возвращает функцию, можно преписать сигнатуру fmap в таком виде:

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

что ещё раз подчёркивает тот факт, что fmap просто втягивает (т.н. lifting) обычную функцию в контекст, фактически преобразуя её в функцию над контекстами:

g  = (< 5) -- обычная функция над числами

g' = fmap g -- функция над вычислительными контекстами с числами

Легко видеть, как fmap сделал из “простой” функции функцию “f-мира” (тип нашего функтора):

g  :: (Num a, Ord a) => a -> Bool
g' :: (Functor f, Num a, Ord a) => f a -> f Bool

Сигнатуры подсказывают, как будут вести себя g и g'.

g есть отображение чего-то одновременно численного (класс Num) и упорядоченного (класс Ord), в тип Bool значений истина/ложь.

g' есть отображение чего-то, что функтор (класс Functor) поверх численного и упорядоченного содержания, в такой-же функтор поверх булевого типа.

> g 3
True

> -- Functor []
> g' [1, 3, 6, 9]
[True,True,False,False]

> -- Functor Maybe
> g' (Just 6)
Just False

> -- Functor Tree
> g' $ Node 5 [Node 4 [Node 3 []], Node 6 [Node 7 []]]
Node {rootLabel = False, subForest = [Node {rootLabel = True, subForest = [Node {rootLabel = True, subForest = []}]},Node {rootLabel = False, subForest = [Node {rootLabel = False, subForest = []}]}]}

> -- а можно сразу и нарисовать это дерево
> (putStrLn . drawTree . fmap show . g') $ Node 5 [Node 4 [Node 3 []], Node 6 [Node 7 []]]
False
|
+- True
|  |
|  `- True
|
`- False
   |
   `- False

Просто замечательно!