Haskell Language
Функтор
Поиск…
Вступление
Functor
- это класс типов f :: * -> *
который может быть ковариантно отображен . Сопоставление функции над структурой данных применяет функцию ко всем элементам структуры без изменения самой структуры.
замечания
Функтор можно рассматривать как контейнер для некоторого значения или контекст вычисления. Примерами могут Maybe a
или [a]
. В статье Typeclassopedia есть хорошая формулировка концепций, стоящих за Функциями.
Чтобы считаться реальным Функтором, экземпляр должен соблюдать два следующих закона:
тождественность
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
чтобы получить тип, который можно использовать со стандартным зоопарком рекурсивных схем.
название | Как тип данных | Использование набора функций |
---|---|---|
Пары ценностей | data Pair a = Pair aa | type Pair = I :*: I |
Сети «два-два» | type Grid a = Pair (Pair a) | type Grid = Pair :.: Pair |
Естественные числа | data Nat = Zero | Succ Nat | type Nat = Fix (K () :+: I) |
Списки | data List a = Nil | Cons a (List a) | type List a = Fix (K () :+: K a :*: I) |
Двоичные деревья | data Tree a = Leaf | Node (Tree a) a (Tree a) | type Tree a = Fix (K () :+: I :*: K a :*: I) |
Розовые деревья | data Rose a = Rose a (List (Rose a)) | type Rose a = Fix (K a :*: List :.: I) |
Этот подход «набора» к разработке типов данных является идеей создания общих библиотек программирования, таких как 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