Haskell Language
Функтор

Вступление

замечания

fmap id == id

fmap (f . g) = (fmap f) . (fmap g)

Общие примеры Functor

Может быть

Maybe , это Functor содержащий возможно отсутствующее значение:

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

Maybe , пример Functor применяет функцию к значению, заключенному в Just . Если вычисление ранее потерпело неудачу (так что значение Maybe - это Nothing ), тогда нет никакого значения для применения функции, поэтому fmap является no-op.

> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing

Мы можем проверить законы функтора для этого примера, используя эквациональные рассуждения. Для закона идентичности,

fmap id Nothing
Nothing  -- definition of fmap
id Nothing  -- definition of id

fmap id (Just x)
Just (id x)  -- definition of fmap
Just x  -- definition of id
id (Just x)  -- definition of id

По закону о композиции,

(fmap f . fmap g) Nothing
fmap f (fmap g Nothing)  -- definition of (.)
fmap f Nothing  -- definition of fmap
Nothing  -- definition of fmap
fmap (f . g) Nothing  -- because Nothing = fmap f Nothing, for all f

(fmap f . fmap g) (Just x)
fmap f (fmap g (Just x))  -- definition of (.)
fmap f (Just (g x))  -- definition of fmap
Just (f (g x))  -- definition of fmap
Just ((f . g) x)  -- definition of (.)
fmap (f . g) (Just x)  -- definition of fmap

Списки

Экземпляр экземпляров Functor применяет функцию к каждому значению в списке.

instance Functor [] where
    fmap f [] = []
    fmap f (x:xs) = f x : fmap f xs

В качестве альтернативы это можно записать в виде понимания списка: fmap f xs = [fx | x <- xs] .

Этот пример показывает, что fmap обобщает map . map работает только в списках, тогда как fmap работает на произвольном Functor .

Можно доказать, что закон тождества сохраняется по индукции:

-- base case
fmap id []
[]  -- definition of fmap
id []  -- definition of id

-- inductive step
fmap id (x:xs)
id x : fmap id xs  -- definition of fmap
x : fmap id xs  -- definition of id
x : id xs  -- by the inductive hypothesis
x : xs  -- definition of id
id (x : xs)  -- definition of id

и аналогичным образом, составной закон:

-- base case
(fmap f . fmap g) []
fmap f (fmap g [])  -- definition of (.)
fmap f []  -- definition of fmap
[]  -- definition of fmap
fmap (f . g) []  -- because [] = fmap f [], for all f

-- inductive step
(fmap f . fmap g) (x:xs)
fmap f (fmap g (x:xs))  -- definition of (.)
fmap f (g x : fmap g xs)  -- definition of fmap
f (g x) : fmap f (fmap g xs)  -- definition of fmap
(f . g) x : fmap f (fmap g xs)  -- definition of (.)
(f . g) x : fmap (f . g) xs  -- by the inductive hypothesis
fmap (f . g) xs  -- definition of fmap

функции

Не каждый Functor выглядит как контейнер. Экземпляр функций Functor применяет функцию к возвращаемому значению другой функции.

instance Functor ((->) r) where
    fmap f g = \x -> f (g x)

Заметим, что это определение эквивалентно fmap = (.) . Таким образом, fmap обобщает функцию композиции.

Еще раз проверьте закон о личности:

fmap id g
\x -> id (g x)  -- definition of fmap
\x -> g x  -- definition of id
g  -- eta-reduction
id g  -- definition of id

и закон состава:

(fmap f . fmap g) h
fmap f (fmap g h)  -- definition of (.)
fmap f (\x -> g (h x))  -- definition of fmap
\y -> f ((\x -> g (h x)) y)  -- definition of fmap
\y -> f (g (h y))  -- beta-reduction
\y -> (f . g) (h y)  -- definition of (.)
fmap (f . g) h  -- definition of fmap

Определение класса функтора и законов

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

Один из способов взглянуть на это - это то, что fmap возвращает функцию значений в функцию значений в контексте f .

Правильный экземпляр Functor должен удовлетворять законам функтора , хотя они не применяются компилятором:

fmap id = id                    -- identity
fmap f . fmap g = fmap (f . g)  -- composition

Существует широко используемый псевдоним infix для fmap называемый <$> .

infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

Замена всех элементов функтора на одно значение

Модуль Data.Functor содержит два комбинатора, <$ и $> , которые игнорируют все значения, содержащиеся в функторе, заменяя их все одним постоянным значением.

infixl 4 <$, $>

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

$> :: Functor f => f a -> b -> f b
($>) = flip (<$)

void игнорирует возвращаемое значение вычисления.

void :: Functor f => f a -> f ()
void = (() <$)

Полиномиальные функторы

Существует полезный набор комбинаторов типов для построения больших Functor s из меньших. Они являются поучительными примерами Functor , и они также полезны в качестве метода для общего программирования, поскольку они могут использоваться для представления большого класса общих функторов.

Тождественный функтор

Идентичный функтор просто завершает свой аргумент. Это реализация уровня I комбинатора из исчисления SKI.

newtype I a = I a

instance Functor I where
    fmap f (I x) = I (f x)

I могу найти под именем Identity в модуле Data.Functor.Identity .

Постоянный функтор

Постоянный функтор игнорирует свой второй аргумент, содержащий только постоянное значение. Это аналоговый аналог типа const , комбинатор K из исчисления SKI.

newtype K c a = K c

Заметим, что K ca не содержит никаких a -значений; K () изоморфно Proxy . Это означает, что реализация K fmap не делает никакого отображения вообще!

instance Functor (K c) where
    fmap _ (K c) = K c

K иначе известен как Const , из Data.Functor.Const .

Остальные функторы в этом примере объединяют меньшие функторы в более крупные.

Продукты Functor

Произведение функтора принимает пару функторов и упаковывает их. Это аналогично кортежу, за исключением того, что while (,) :: * -> * -> * работает на types * , (:*:) :: (* -> *) -> (* -> *) -> (* -> *) действует на functors * -> * .

infixl 7 :*:
data (f :*: g) a = f a :*: g a

instance (Functor f, Functor g) => Functor (f :*: g) where
    fmap f (fx :*: gy) = fmap f fx :*: fmap f gy

Этот тип можно найти под названием Product в модуле Data.Functor.Product .

Сопутствующие товары

Точно так же :*: аналогично (,) :+: является аналогом уровня функтора Either .

infixl 6 :+:
data (f :+: g) a = InL (f a) | InR (g a)

instance (Functor f, Functor g) => Functor (f :+: g) where
    fmap f (InL fx) = InL (fmap f fx)
    fmap f (InR gy) = InR (fmap f gy)

:+: можно найти под именем Sum , в модуле Data.Functor.Sum .

Состав functor

Наконец, :.: Работает как тип уровня (.) , Беря вывод одного функтора и вставляя его во вход другого.

infixr 9 :.:
newtype (f :.: g) a = Cmp (f (g a))

instance (Functor f, Functor g) => Functor (f :.: g) where
    fmap f (Cmp fgx) = Cmp (fmap (fmap f) fgx)

Тип Compose можно найти в Data.Functor.Compose

Полиномиальные функторы для общего программирования

I , K :*: , :+: и :.: Можно рассматривать как набор строительных блоков для определенного класса простых типов данных. Набор становится особенно мощным, когда вы объединяете его с фиксированными точками, потому что типы данных, построенные с помощью этих комбинаторов, автоматически являются экземплярами Functor . Вы используете комплект для создания типа шаблона, маркировки рекурсивных точек с помощью I , а затем подключите его к Fix чтобы получить тип, который можно использовать со стандартным зоопарком рекурсивных схем.

Этот подход «набора» к разработке типов данных является идеей создания общих библиотек программирования, таких как generics-sop . Идея состоит в том, чтобы писать общие операции, используя набор, подобный представленному выше, а затем использовать класс типа для преобразования произвольных типов данных в их общее представление:

class Generic a where
    type Rep a  -- a generic representation built using a kit
    to :: a -> Rep a
    from :: Rep a -> a

Функторы в теории категорий

Функтор определен в теории категорий как сохраняющее структуру отображение (а 'гомоморфизм') между категориями. В частности, (все) объекты отображаются на объекты, а (все) стрелки отображаются на стрелки, так что законы категории сохраняются.

Категорией, в которой объекты являются типами и морфизмами Haskell, являются функции Haskell, называемые Hask . Таким образом, функтор от Hask до Hask будет состоять из отображения типов в типы и отображения из функций в функции.

Взаимоотношения, которые теоретическая концепция этой категории относится к программированию программирования Haskell, Functor довольно прямая. Отображение от типов к типам принимает вид типа f :: * -> * , а отображение функций в функции принимает вид функции fmap :: (a -> b) -> (fa -> fb) , Объединяя их в классе,

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

fmap - операция, которая принимает функцию (тип морфизма), :: a -> b и сопоставляет ее с другой функцией :: fa -> fb . Предполагается (но оставленный программисту для обеспечения), что экземпляры Functor действительно являются математическими функторами, сохраняя категориальную структуру Хаска :

fmap (id {- :: a -> a -})  ==  id {- :: f a -> f a -}
fmap (h . g)               ==  fmap h . fmap g

fmap поднимает функцию :: a -> b в подкатегорию Хаска таким образом, который сохраняет как существование любых точечных стрелок, так и ассоциативность композиции.

Класс Functor только кодирует эндофункторы на Hask . Но в математике функторы могут отображать между произвольными категориями. Более точное кодирование этой концепции будет выглядеть так:

class Category c where
    id  :: c i i
    (.) :: c j k -> c i j -> c i k

class (Category c1, Category c2) => CFunctor c1 c2 f where
    cfmap :: c1 a b -> c2 (f a) (f b)

Стандартный класс Functor - это особый случай этого класса, в котором исходная и целевая категории являются как Hask . Например,

instance Category (->) where        -- Hask
    id    = \x -> x
    f . g = \x -> f (g x)

instance CFunctor (->) (->) [] where
    cfmap = fmap

Получение эффекта

DeriveFunctor языка DeriveFunctor позволяет GHC автоматически генерировать экземпляры Functor .

{-# LANGUAGE DeriveFunctor #-}

data List a = Nil | Cons a (List a) deriving Functor

-- instance Functor List where            -- automatically defined
--   fmap f Nil = Nil
--   fmap f (Cons x xs) = Cons (f x) (fmap f xs)

map :: (a -> b) -> List a -> List b
map = fmap