- Что еще за параллель такая, - смутно отзывался Митрич. - Может, такой никакой параллели и вовсе нету. Этого мы не знаем. В гимназиях не обучались.

(Ильф и Петров, "Двенадцать стульев")

что такое функтор?

если вы можете применить к своим специальным (boxed) данным некую функцию (map), принимающую в качестве одного параметра функцию от одного простого (unboxed) аргумента, а в качестве второго - ваше специальное (boxed) значение и возвращающую измененное специальное же (boxed) значение, то "поздравляю тебя Шарик - ты балбес" © ваши данные - функтор

функтор - это конструктор boxed-типа x с методом map, такой что:

функция map

функтор - это тип данных, предоставляющий (специальный) контекст для (обычного) вычисления

положим, что десять лет тому назад вы написали клевую библиотеку арифметики для целых:


  // file intlib.c

  int twice (int x) { return x * 2 ; }
  int plus2 (int x) { return x + 2 ; }
  int div2  (int x) { return x / 2 ; }
тогда же вы оттестировали свою библиотеку и после этого долго и успешно используете ее при работе с целыми

положим, что у вас в новом проекте теперь появился сложный тип данных, но одно из полей - целое


  struct mydata
  {
    int  a ;
    char b ;
  }
и вы хотели бы использовать свою старую библиотеку, но уже с новым типом, применяя ваши старые библиотечные функции, понятное дело, только к этому полю

как же применить библиотечные функции к полю a и вернуть измененную структуру?

можно так:

// file withoutfunctor.c

#include <stdio.h>
#include "intlib.c"

struct mydata { int a ; char b ; } ; 

int
main (void)
{
  struct mydata z = { z.a = 20, z.b = 'k', } ;
  struct mydata z1, z2, z3 ;

  z1.a = twice (z.a), z1.b = z.b ;
  z2.a = plus2 (z.a), z2.b = z.b ;
  z3.a = div2  (z.a), z3.b = z.b ;

  printf ("%5i %5i %5i %5i\n", z.a, z1.a, z2.a, z3.a) ;
  return 0 ;
}

пробуем:

$> gcc withoutfunctor.c 
$> ./a.out 
   20    40    22    10

это работает, но это как-то неспортивно

а можно ведь и этак:

// file functor.c

#include <stdio.h>
#include "intlib.c"

struct mydata { int a ; char b ; } ; 
struct mydata map (int (*)(int), struct mydata) ;

int 
main (void) 
{
  struct mydata z = { z.a = 20, z.b = 'k', } ;

  z1 = map (twice, z) ; 
  z2 = map (plus2, z) ;
  z3 = map (div2,  z) ;

  printf ("%5i %5i %5i %5i\n", z.a, z1.a, z2.a, z3.a) ;
  return 0 ;
}

struct mydata 
map (int f(int), struct mydata x)
{
  x.a = f (x.a) ;
  return x ;
}

пробуем:

$> gcc functor.c
$> ./a.out 
   20    40    22    10

чем второй подход лучше? отсутствием копипасты, инкапсуляцией данных. если кодить на кацкеле или на окамле - то еще и полиморфизмом

но это только начало ...


функторы появляются всякий раз, когда мы пишем адаптеры (прокладки) между разными частями софта

предположим, что мы уже имеем реализованными две функции:


f :: Int -> Bool 
f = \x -> even x

g :: Bool -> Char 
g = \x -> case x of True -> 't' ; False -> 'f'

две функции коммутируют образуя для нас функцию Int -> Char и жизнь воистину прекрасна. но "внезапно" нам понадобилось манипулировать списками целых:


h :: [Int] -> [Char]

причем логика манипуляции один-в-один прежняя: если целое четно, то оно преобразуется в знак t, а если нечетно - то в знак f, точно такой-же, но с перламутровыми пуговицами но на списках

мы не будем писать код с нуля и не будем переписывать старые функции, чтобы они стали работать со списком - мы не такие, мы ждем трамвая

мы отобразим морфизмы домена целых и морфизмы домена символов в морфизмы домена списков

как?

в кацкеле "изкаропки" (Prelude) мы имеем map:


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

воспользуемся им:


h :: [Int] -> [Char] 
h = map (g . f) 

пробуем:

ghci> let x = [1..7]
ghci> h x
"ftftftf"

нетрудно заметить, что map является функтором ибо:


    map (g . f)  =  map g . map f
    map id       =  id

использование функторов автоматически делает ваш код future-proof: вы пишете компоненты в удобном для вас домене, а когда приходит пора применить подобные морфизмы в другом домене, вы определяете функтор, который отобразит ваш старый код в новый домен

но и это еще не все...


из любой монады можно получить функтор:

ghci> let fmap' f m = m >>= (return . f)
ghci> :t fmap'
fmap' :: Monad m => (a -> b) -> m a -> m b

то есть любая монада всегда также является и функтором. в том числе, это относится к монаде IO, что позволяет писать:

ghci> reverse <$> getLine >>= return
abcdef
"fedcba"

но в общем случае, без явного объявления экземпляра класса, функтора из монады вы не получите

вернемся к предыдущему примеру, но слегка поменяем функцию h. а именно - сделаем ее морфизмом Клейсли. это вовсе не то, что вы подумали, а совсем-совсем другое: h была у нас типа [a] → [b], а станет типа a → Maybe b

итак:


f :: Int -> Bool 
f = even 

g :: Bool -> Char 
g True = 't' 
g _    = 'f'

h :: Char -> Maybe Int 
h 't' = Just 1
h 'f' = Just 0 
h _   = Nothing
пока все чинно-благородно и понятно. добавим перца

morph :: Monad m => (a -> b) -> (a -> m b)
morph = (return . )
а теперь сделаем так:

j :: Int -> Maybe Int 
j =  \x -> morph f x >>= morph g >>= h
или "некоторые любят погорячеe" © ;:

k :: Int -> Maybe Int 
k = \x -> h =<< morph (g . f) x
продолжим этот занимательный эксперимент:

h2 :: Char -> Either String Int
h2 't' = Right 1 
h2 'f' = Right 0
h2 _   = Left "some error" 
и снова сделаем так:

y :: Int -> Either String Int 
y = \x -> morph (g . f) x >>= h2 
или "в джазе только девушки" © ;:

w :: Int -> Either String Int 
w = \x -> h2 =<< morph g =<< morph f x 

что это за morph такой-сякой, брутальный и крутой? ба, так это же наш старый знакомый - функтор!

функтор morph транcформирует одну категорию в другую категорию, сохраняя при этом морфизмы

в приведенном выше коде категорией-источником была категория с морфизмами (функциями) одной переменной. и что характерно - любая такая категория:

            idA  = id
            (.)A = (.)

а категорией-получателем была Kleisli-категория (тоже - любая):

            idB  = return
            (.)B = (>=>)

нетрудно заметить, что наш morph подчиняется правилам:

            morph id = return
            morph (g . f) = morph f >=> morph g

поэтому он и функтор

это - круто, но можно стать еще более крутым кацкелом хеллом


предположим, что у меня есть приличный обьем кода, который использует библиотеку Foo

module Foo where

f :: Int -> Maybe Bool 
f = \k -> if k > 100 then Just True else Just False

g :: Bool -> Maybe Char 
g = \k -> if k then Just 't' else Just 'f'

в один прекрасный день я нашел на haskell.hackage.org другую библиотеку - Bar, которая предлагает заманчивые функции для моих данных, но ... реализованные в другой монаде

module Bar where

h :: Char -> [Double]
h = \k -> case k of 't' -> [1.0] ; 'f' -> [0] ; _ -> []

j :: Int -> [Char]
j = \k -> if k > 100 then ['t'] else ['f'] 

я не хочу (да и не могу) ничего переписывать в библиотеках Foo и Bar, но я хочу при этом использовать СОВМЕСТНО функции как из одной, так и из другой библиотеки. поэтому я решил написать адаптер, который позволит мне смешивать в одном конвейере функции из двух библиотек

import qualified Foo as A
import qualified Bar as B
import Control.Monad ((<=<) , (>=>))

-- теперь так:

mmorph1 :: Maybe a -> [a]
mmorph1 (Just x) = [x]
mmorph1 Nothing  = []

transf1 :: (a -> Maybe b) -> (a -> [b])
transf1 = (mmorph1 .)

code11 :: Int -> [Double] 
code11 = \i -> transf1 (A.f >=> A.g) i >>= B.h

-- и еще:

mmorph2 :: [a] -> Maybe a 
mmorph2 []     = Nothing
mmorph2 (x:xs) = Just x

transf2 :: (a -> [b]) -> (a -> Maybe b)
transf2 = (mmorph2 .)

code21 :: Int -> Maybe Double
code21 = \i -> transf2 B.h =<< (A.g <=< A.f) i

code22 :: Int -> Maybe Double
code22 = transf2 (B.j >=> B.h)

ну вот, чего ни делай, а всегда получаются автоматы Калашникова функторы

функторы transf1 и transf2 транcформируют одну категорию в другую категорию, сохраняя при этом морфизмы

на этот раз категория-источник и категрия-назначение совпали (обе являются Клейсли-морфизмами). получившиеся функторы transf1 и transf2 сохраняют композицию и идентичность - собственно поэтому они и функторы

для функций mmorph1 и mmorth2 есть название: monad morphism. таким морфизмом является любая функция с сигнатурой:

monad_morph :: (Monad m, Monad n) => forall r . m r -> n r

такая, что (monad_morph . ) определяет функтор monad_transf между двумя категориями Клейсли:

monad_transf :: (Monad m, Monad n) => (a -> m b) -> (a -> n b)
monad_transf = (monad_morph . )

продвинутые кацкелисты увидят легкую вариацию этого шаблона:

(lift . ) return    = return  

(lift . ) (f >=> g) = (lift . ) f >=> (lift . ) g   

так это же законы функтора для монадных трансформеров! первый - identity law, а второй - composition law. да, монадные трансформеры являются подмножеством монадных морфизмов и законы монадных трансформеров - это законы функторов!

* * *

вот так-то, малята! а вы говорите - "пойдем купаться"