Возможно, вам уже знакома функция map:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs


> map (x -> x + 1) [1, 2, 3]
[2, 3, 4]

Она берет функцию типа a -> b и применяет ее к каждому элементу списка. Элементы меняются, но тип данных, хранящих их ([]), остается прежним. В этой статье мы будем называть такой тип данных с другим типом внутри контекстом.

Преобразование значений внутри фиксированных контекстов — обычное явление в программировании.

Например, необязательный тип данных (Maybe) предоставляет контекст возможного неудачного вычисления. Его также можно «отобразить», пытаясь применить функцию к обернутому значению без изменения контекста.

map' :: (a -> b) -> Maybe a -> Maybe b

map' f (Just x) = Just (f x)
map' f Nothing = Nothing


> map' (x -> x + 1) (Just 1)
Just 2
> map' (x -> x + 1) Nothing
Nothing

Эта статья познакомит вас с Functor — типовым классом, который унифицирует эти виды преобразований и предоставляет для них общую функциональность.

После прочтения этой статьи вы будете знать:

• что такое Functor в Haskell;
• как определять и использовать свои собственные экземпляры Functor;
• почему и где полезны Functor.

Мы также предоставим набор упражнений для закрепления ваших знаний.

Как обобщить map.

Посмотрите на сигнатуру типа map:

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

Она принимает функцию a -> b. Затем она использует эту функцию для изменения содержимого списка.

Теперь посмотрите на тип map'. Он использует функцию того же типа — a -> b — для изменения содержимого Maybe.

map' :: (a -> b) -> Maybe a -> Maybe b

Сигнатуры типов похожи!

Можем ли мы иметь более общую функцию, которая работает в различных контекстах? Безусловно. Это же Haskell, в конце концов.

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

Вот как это работает. fmap принимает функцию a -> b и тип данных f a (a обернуто в любой контекст f). Функция применяется к тому, что находится внутри контекста, и возвращается значение типа b, обернутое в f. Значение может меняться, но контекст остается прежним.

Давайте рассмотрим несколько примеров:

-- Apply `reverse :: String -> String`
-- to a list of `String`s
-- to get a list of `String`s.
> fmap reverse ["abc", "def", "ghi"]
["cba","fed","ihg"]
> fmap reverse []
[]

-- Apply `show :: Int -> String`
-- to a list of `Int`s
-- to get a list of `String`s.
> fmap show [1..3]
["1","2","3"]
> fmap show []
[]

-- Apply `(+1) :: Int -> Int` 
-- to `Maybe Int`
-- to get `Maybe Int`.
> fmap (+1) $ Just 1
Just 2
> fmap (+1) Nothing
Nothing

-- Apply `(> 0) :: Int -> Bool` 
-- to `Maybe Int`
-- to get `Maybe Bool`.
> fmap (> 0) $ Just (-1)
Just False
> fmap (> 0) $ Just 1
Just True
> fmap (> 0) Nothing
Nothing

-- Apply `chr :: Int -> Char`
-- to a pair `(a, Int)`
-- to get a pair `(a, Char)`.
-- Note that only the second value is mapped.
> fmap chr (65,65)
(65,'A')
> fmap chr ('a',97)
('a','a')

Как вы уже догадались, map — это просто синоним fmap для списков. Но он может делать гораздо больше. С помощью fmap мы можем выполнять действия внутри таких типов данных, как [], Maybe, Either a, ((,) a), и других.

Конечно, мы не можем предоставить реализацию fmap, которая работает для всех контекстов. Вместо этого, чтобы использовать ее на типе данных, этот тип должен иметь экземпляр типового класса Functor. Как мы увидим, Functor — это то, что обеспечивает реализацию.

Типовой класс Functor

Что такое класс Functor? Давайте спросим у GHCi.

> :info Functor
type Functor :: (* -> *) -> Constraint
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}

Functor в Haskell — это класс типов, который предоставляет два метода — fmap и (<$) — для структурно-сохраняющих преобразований.

Чтобы реализовать экземпляр Functor для типа данных, необходимо предоставить специфическую для типа реализацию fmap — функции, которую мы уже рассматривали.

Для большинства распространенных типов данных экземпляры Functor уже реализованы. Для ваших собственных типов данных вам придется определить их самостоятельно.

data Option a = Some a | None

instance Functor Option where
  fmap f (Some a) = Some (f a)
  fmap f None = None

Более подробно о том, как это сделать, мы расскажем позже.

Что может быть функтором?

Есть две вещи, которые ограничивают то, для чего вы можете реализовать экземпляр Functor: сигнатура вида Functor и его законы.

Подпись вида Functor

Вид Functor — (* -> *) -> Constraint, что означает, что мы можем реализовать Functor для типов, вид которых * -> *. Другими словами, мы можем реализовать Functor для типов, которые имеют одну непримененную переменную типа.

Например, Maybe и [] принимают одну переменную типа. Следовательно, их вид * -> *, и для них существует простая реализация Functor.

> :kind Maybe
Maybe :: * -> *

Int не имеет переменных типа, и его вид *, поэтому для него нельзя создать экземпляр Functor.

> :kind Int
Int :: *

Either принимает две переменные типа, поэтому его вид * -> * -> *. Но если мы применим его один раз, мы можем сделать так, чтобы вид был * -> * -> *.

> :kind Either
Either :: * -> * -> *
> :kind Either String
Either String :: * -> *

Поэтому для примененного Either существует допустимый экземпляр Functor — instance Functor Either a, где a обозначает любую переменную, которая может быть применена.

Законы функтора

Некоторые из типовых классов Haskell имеют законы — условия, которым должны удовлетворять экземпляры. Обычно эти законы берутся из одноименного математического понятия.

Функтор — это отображение в теории категорий. Следовательно, нам нужно, чтобы fmap придерживался следующих законов.

1. Тождество

2. Композиция

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

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

Существует инструмент, который может проверить, следует ли экземпляр законам — QuickCheck. Он проверяет свойства путем случайного тестирования. Вы можете указать ему свойство, которому должен удовлетворять код (в нашем случае закон типового класса), которое затем проверяется на большом количестве случайно сгенерированных значений. В качестве иллюстрации можно обратиться к разделу «Проверка законов» этой статьи.

Оператор (<$)

fmap — это все, что вам нужно для определения экземпляра Functor. Однако оператор (<$) тоже заслуживает внимания.

Вот сигнатура типа (<$):

(<$) :: a -> f b -> f a

Оператор принимает значение типа a, значение типа b, упакованное в вектор f — f b — и производит вектор f a. По сути, оператор упаковывает значение первого аргумента в контекст второго аргумента, отбрасывая второе значение.

Теперь небольшое упражнение. Давайте попробуем угадать определение (<$), используя приведенное описание и следующие примеры.

-- replace an `Int` value
-- inside `Maybe Int`
-- with a `String`
> "abc" <$ Just 123
Just "abc"
> "abc" <$ Nothing
Nothing

-- replace each element
-- of the list `[Int]`
-- with an `Int`
> 1 <$ []
[]
> 1 <$ [0]
[1]
> 1 <$ [1..5]
[1,1,1,1,1]

Обратите пристальное внимание на примеры из списка. y <$ [x1, x2, x3] приводит к [y, y, y], а не к [y], поскольку список имеет внутри много значений, а не одно. Каждый элемент списка преобразуется вместо того, чтобы обернуть значение в [].

Итак, как вы думаете, каким должно быть определение (<$) по умолчанию?

Определение (<$).

Именно! (<$) просто запускает fmap с функцией const.

x <$ f = fmap (const x) f

Теперь, когда мы рассмотрели основные компоненты Functor, пришло время создать собственный экземпляр этого типового класса!

Как реализовать экземпляр Functor

Давайте посмотрим, как можно реализовать свой собственный экземпляр Functor. В качестве примера мы будем использовать тип данных NonEmpty.

NonEmpty' представляет собой список, в котором есть хотя бы один элемент. Он состоит из двух компонентов: обязательной головы a и хвоста [a], который может быть пустым.

data NonEmpty' a = NonEmpty'
  { neHead :: a
  , neTail :: [a]
  }

Чтобы определить экземпляр Functor, нам нужно реализовать fmap.

Мы определяем его путем сопоставления по образцу головы и хвоста непустого списка. Применение f к голове x позаботится об этом, но что насчет хвоста?

Примечание: чтобы иметь возможность записать сигнатуру типа fmap в определении экземпляра, необходимо использовать расширение InstanceSigs.

instance Functor NonEmpty' where
  fmap :: (a -> b) -> NonEmpty' a -> NonEmpty' b
  fmap f (NonEmpty' x xs) = NonEmpty' (f x) ??

Хвост — это обычный список. А fmap для списков уже определен, поэтому мы можем просто использовать его:

instance Functor NonEmpty' where
  fmap :: (a -> b) -> NonEmpty' a -> NonEmpty' b
  fmap f (NonEmpty' x xs) = NonEmpty' (f x) (fmap f xs)

Однако давайте изучим реализацию, чтобы лучше понять механику fmap.

instance Functor [] where
  fmap :: (a -> b) -> [a] -> [b]
  fmap f x:xs = f x : fmap f xs
  fmap _ [] = []

По сути, здесь используется тот же принцип — разбиение списка на голову и хвост и рекурсивный вызов функции. На каждой итерации мы применяем f к голове и вызываем fmap с хвостом списка. В конце нам нужно покрыть случай пустого списка — «fmap» пустого списка дает пустой список.

И все! Вы только что увидели, как определить экземпляр Functor. Если вы хотите попрактиковаться еще, в разделе упражнений есть дополнительное упражнение на реализацию.

Functor не всегда является контейнером

Есть один примечательный факт о Functor — он не всегда является контейнером. Законы Functor допускают некоторые довольно дикие реализации. Например, функции — это тоже функторы!

Но существует ли тип данных, который соответствует функциям? Ответ — да. Это (->).

> :info (->)
type (->) :: * -> * -> *
data (->) a b

(->) параметризован двумя типами — (->) a b. Другими словами, это a -> b — функция с одним аргументом.

Мы знаем, что Functor может быть реализован только для типов с видом * -> *. К сожалению, видом (->) является * -> * -> *. В таком виде он не удовлетворяет экземпляру Functor, потому что Functor может иметь только один аргумент типа.

Следовательно, его нужно применить один раз, как мы это делаем с Either a или ((,) a). В случае (->) это означает предоставление типа аргумента функции — (->) a или a -> (последнее, однако, не является допустимым синтаксисом в Haskell).

Например, функции со следующими сигнатурами типов имеют экземпляры Functor:

Int -> a
String -> a
(Char, Int) -> a
[Int] -> a

Итак, мы выяснили, какие функции могут быть функторами и каким данным они соответствуют. Следующий вопрос — что значит fmap функции? Интуитивно понятно, что речь идет об изменении функции, то есть действия, которое она выполняет. Но что здесь является фиксированным контекстом?

Давайте построим определение типа fmap для одноаргументной функции. Для произвольного Функтора f, fmap — это:

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

Тип наших данных (->) c. Поэтому нам нужно заменить f t на (->) c t или c -> t. Следовательно, сигнатура типа имеет вид:

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

Теперь мы видим, что фиксированный контекст соответствует типу аргумента функции c. А изменяемое значение — это тип возврата функции — мы переходим от a к b с помощью функции a -> b.

В целом, fmap для функций преобразует то, что возвращает функция, сохраняя входные данные неизменными! Вам это знакомо?

Какая функция или оператор языка Haskell может создать функцию c -> b из a -> b и c -> a?

Состав функции:

> :t (.)
(.) :: (a -> b) -> (c -> a) -> c -> b

Обратите внимание, что

(a -> b) -> (c -> a) -> c -> b

точно такая же, как

(a -> b) -> (c -> a) -> (c -> b)

поскольку -> в Haskell является право-ассоциативным.

Круто! fmap для Functor — это просто композиция функций.

Вот реализация экземпляра ((->) a):

instance Functor ((->) a) where
  fmap = (.)

В заключение, давайте убедимся, что fmap является (.) для одноаргументной функции a -> b на примере ниже:

-- fmap :: (Int -> Int) -> (Int -> Int) -> Int -> Int
> fmap (+1) (*2) 2
5
> (+1) . (*2) $ 2
5

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

Почему Functor полезен?

В целом, Functor не является экстраординарным типовым классом. Его методы просты для понимания и реализации.

Тем не менее, проект на Haskell вряд ли может обойтись без пары экземпляров Functor. Он позволяет выполнять преобразования над обернутым типом, ничего не зная об обертке, а это очень полезно.

Более того, Functor является прочной основой и предшественником типокласса Applicative, который далее ведет к Monad. Последний является известным и широко используемым классом в Haskell. Его понимание позволит вам значительно лучше владеть языком.

Заключение

В этой статье мы рассмотрели типовой класс Functor: что это такое, где его можно использовать и как реализовать собственные экземпляры Functor. Это часть цикла статей What’s That Typeclass, в котором мы знакомим читателей с часто используемыми типовыми классами Haskell.

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

И, наконец, если вы видите, что в статье что-то не так, или вам что-то непонятно, вы можете оставить вопрос в нашем репозитории на GitHub — мы будем вам очень признательны!

Упражнения

1. Реализуйте Functor для бинарных деревьев поиска.

2. Реализуйте (<$) для Maybe a.

3. Реализуйте функцию, преобразующую строки в верхний регистр (toUpperString :: String -> String) без использования toUpper.

4. Докажите, что функтор экземпляров ((->) a), который мы обсуждали ранее, следует законам тождества и композиции.