Впустите приемник функторов Haskell.

Left и Right не являются типами, а Left x и Right y относятся к одному типу. Они просто конструкторы Either. Вы можете рассмотреть

Left :: c -> Either c d
Right :: d -> Either c d

У вас может быть 2 объявления fmap , потому что мы знаем, что Left и Right - разные значения. Это похоже на

g :: Int -> Int
g 1 = 2
g 2 = 4
g n = n

. Здесь мы не можем сказать, что 1 и 2 и n являются разными «типами» только потому, что сопоставление с образцом работает.

Класс Functor определен таким образом, что

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

Обратите внимание, что a и b являются произвольными типами. Для ясности давайте переименуем a в вашем экземпляре в c , а функцию f в func .

instance Functor (Either c) where  
    fmap func (Right x) = Right (x)  
    fmap func (Left x) = Left (func x)

Предположим, что ваш Either следует определению по умолчанию

data Either c d = Left c | Right d

, тогда по вашему определению

fmap    func     (Right x) = Right x
-- # (a -> b) ->      f a       f  b
-- # f = Either c

это вынуждает a = b , а

fmap    func     (Left x) = Left (func x)
-- # (a -> b) ->     f a       f b
-- # f = Either c

вынуждает c = a = b . Оба они недействительны, учитывая, что a , b и c являются независимыми произвольными типами.

Экземпляр, который вы пытаетесь написать, назовем его fmap2 , имеет следующий тип:

fmap2 :: (a -> b) -> Either a c -> Either b c

Если вы установите LANGUAGE ] pragma TypeOperators , GHC также принимает тип

fmap2 :: (a -> b) -> (a `Either` c) -> (b `Either` c)

В идеальном мире это также будет работать:

fmap2 :: (a -> b) -> (`Either` c) a -> (`Either` c) b

, который даст экземпляр Functor для (`Either` c) , но сходство между обычными операторами (и их разделами) и операторами типов исчезает на этом этапе (если нет опции GHC, которую мне не хватает!)

Короче говоря: ваше понимание функторов в порядке, но вас укусила отсутствие лямбд на уровне типов.

Надеюсь, это поможет ...

Но сначала немного предыстории:

1) Функтору нужен «конструктор типа», (ну, не тип как таковой , ...) тип, которому «нужен» другой обычный тип, данный ему для формирования «полного типа», точно так же, как универсальный тип в Java / C ++. Так, например, List является Functor (это, кстати) или Array , потому что (среди прочего) полный тип не является t только Список , но Список . Так, : Функтор принимает «конструктор типа», неполный тип.

fmap :: (a -> b) -> (Either Integer a -> Either Integer b)

fmap f (Right x) = Right (x)  
fmap f (Left x) = Left (f x)

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

Хотя в конечном итоге я буду придерживаться вашего формата, я собираюсь начать с чего-то в немного другом формате, поскольку я думаю, что это сделает мое объяснение более ясным.

Давайте рассмотрим другой тип данных

data Choice a = Default Integer | Chosen a

-- This corresponds to your top, working, instance.
instance Functor Choice where
  fmap f (Default i) = Default i
  fmap f (Chosen  a) = Chosen  (f a)

Должно быть понятно, почему этот пример работает. Однако, что насчет следующего:

-- Broken!
instance Functor Choice where
  fmap f (Default i) = Default (f i)
  fmap f (Chosen  a) = Chosen  a

Вы должны быть в состоянии понять, почему это не работает. Типом fmap является Functor f => (a -> b) -> f a -> f b; в данном контексте это (a -> b) -> Choice a -> Choice b. Таким образом, аргумент f имеет тип a -> b. Однако во втором (неудачном) объявлении экземпляра вы пишете f i. Из объявления типа данных мы знаем, что i должно быть Integer, поэтому мы не можем применить к нему f. Аналогично, поскольку a имеет тип a, Chosen a будет иметь тип Chosen a, а не тип Chosen b. Таким образом, экземпляр Functor внизу не может работать.

Хорошо, ваш верхний экземпляр для Either работает, потому что, как и в примере с Choice, он подчиняется типам. Давайте посмотрим на него, несколько переименовав:

instance Functor (Either c) where  
  fmap f (Left  c) = Left  c
  fmap f (Right a) = Right (f a)

Это объявление экземпляра не объявляет экземпляр Functor для Either- оно и не может. То, что является экземпляром Functor, должно принимать один параметр типа. Таким образом, Int не может быть функтором, поскольку Int не принимает параметров типа, но [] и Maybe могут быть, поскольку [a] и Maybe a - полные типы. Either, однако, принимает два параметра типа: Either a b. Таким образом, этот экземпляр делает то, что объявляет, что Either c является функтором для любого возможного c. Этот c является фиксированным на время объявления экземпляра. Итак, давайте пройдемся и добавим типы (это не законный синтаксис! ):

instance Functor (Either c) where
  fmap :: forall a b. (a -> b) -> (Either c) a -> (Either c) b
  fmap f (Left  (c :: c)) = Left  c
  fmap f (Right (a :: a)) = Right (f a :: b)

Поскольку f имеет тип a -> b, а тип c фиксирован на c, мы не можем написать Left (f c); и даже если бы могли, мы хотим оставить c в покое, чтобы вернуть (Either c) b. Аналогично, мы должны применить f к a, чтобы получить что-то типа b.

Именно поэтому ваш нижний пример не работает: у вас есть функция, которая должна работать для любого типа, применяемая только к фиксированному типу c, а тип, который вам нужен для преобразования, вы оставляете в покое. Давайте посмотрим на это, снова добавив сигнатуры типов:

instance Functor (Either c) where  
  fmap :: forall a b. (a -> b) -> (Either c) a -> (Either c) b
  fmap f (Left  (c :: c)) = Left  (f c)
  fmap f (Right (a :: a)) = Right a

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

В основном, проблема возникает из-за этого. Во-первых, обратите внимание, что f одинаково в двух пунктах определения функции, поэтому оно не может меняться между строками. Во-вторых, обратите внимание, что мы исправляем c и объявляем для экземпляра c. Это верно для любого c, но мы рассматриваем только одно за раз. Наконец, из-за этого аргумент Left не параметризован типом, который ожидает f; он гарантированно имеет некоторый фиксированный тип c. Это означает, что (а) вы не можете применить к нему f, и (б) вы должны применить его к аргументу Right, поскольку иначе вы не измените тип, который ожидается изменить.

Хорошо, вот еще одна очень простая попытка.

Вы спрашиваете, почему это не компилируется:

instance Functor (Either a) where
    fmap f (Right x) = Right (x)
    fmap f (Left x) = Left (f x)

Итак, давайте попробуем упростить проблему, попытавшись определить ту же функцию, не помещая ее как часть объявления экземпляра класса:

Это дает нам

foo f (Right x) = Right (x)
foo f (Left x) = Left (f x)

Который действительно компилируется. ghci сообщает нам сигнатуру типа:

*Main> :t foo
foo :: (t1 -> a) -> Either t1 t -> Either a t

Мы переименуем некоторые переменные, чтобы получить более единообразный вид:

foo :: (a -> b) -> Either a c -> Either b c

В этом есть смысл. Он берет функцию и применяет ее слева от любого.

Но какова сигнатура для fmap?

*Main> :t fmap
fmap :: (Functor f) => (a -> b) -> f a -> f b

Итак, давайте заменим Либо c вместо f в сигнатуре fmap (я переименовал Либо в ] Либо c , чтобы наши два разных a не перепутались):

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

Вы видите проблему? Ваша функция совершенно верна - просто у нее другой тип, чем у fmap для . Либо обязательно должен иметь .

Это своего рода прекрасная вещь о типах. Учитывая сигнатуру для fmap , на самом деле существует только одна значимая реализация для fmap на Либо a.

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

Edit : пытаюсь ответить на вопросы ниже.

1) Не происходит «композиции двух функций».Чтобы получить сигнатуру типа для fmap вместо Либо , просто пройдите через сигнатуру функции fmap , и везде, где вы видите f , замените это с Либо с . Мы бы назвали это «специализацией» сигнатуры типа fmap. Другими словами, он строго менее общий , чем обычный тип fmap - везде, где требуется функция более специализированного типа, вы можете без проблем передать что-то общего типа.

2) Ваша функция для отображения на левой стороне (которую я назвал «foo» в приведенных выше примерах) вполне подойдет. Он отлично работает, он делает то, что вы хотите. Вы просто не можете назвать его fmap и использовать в экземпляре Functor. Лично я бы назвал его примерно так onLeft или mapLeft .

Все следующее может быть проигнорировано / предназначено для информации, но не является предложением для будущего чтения в ближайшем будущем / фактического использования:

Если кто-то хочет получить очень техническую информацию, потому что вы можете нанести карту как на левую, так и на левую сторону. с правой стороны (хотя вы можете объявить Functor только для последнего), Either - это не только Functor, но и Bifunctor. Это предусмотрено, например, в библиотеке ekmett Category-Extras (см. http://hackage.haskell.org/packages/archive/category-extras/0.44.4/doc/html/Control-Bifunctor.html ]).

Есть много интересных вещей, связанных с вычислениями с помощью программ и "программированием оригами", которое более строго использует бифункторы. Вы можете прочитать об этом здесь: http://lambda-the-ultimate.org/node/1360 .Но вы, вероятно, не захотите этого, по крайней мере, до тех пор, пока не станете более знакомыми с Haskell. Это компьютерная наука, математика, исследовательская работа и очень круто, но совсем не обязательно для понимания идиоматического программирования на Haskell.

Хотите верьте, хотите нет, это не волшебство. Все это связано с типом Либо a b не является тем же типом, что и , либо b a . Вот определение Either из Prelude

data  Either a b  =  Left a | Right b

... Обратите внимание, что сначала идет переменная типа a, затем b, а также обратите внимание, что мы включаем только a в объявление функтора Either:

instance Functor (Either a) where  
    fmap f (Right x) = Right (f x)  
    fmap f (Left x) = Left x

Теперь давайте посмотрим на определение функтора Maybe

instance Functor Maybe where
    fmap = map

Здесь нет переменной типа, хотя Maybe принимает один параметр типа (например, Maybe Int ). Я пытаюсь понять, что типы - это не функторы, а конструкторы типов - это функторы (у функторов есть вид * -> * ).

Итак, пусть f :: b -> c , в версии Either Functor, которая работает, x из (Left x) имеет введите a , что нормально, поскольку это (Либо a) , который является функтором, x в (Right x) имеет Введите b , поэтому (Правый x) имеет тип ((Либо a) b) , а (Правый (fx)) - типа ((Либо a) c) , поэтому fmap имеет тип (b-> c) -> ((Либо a) b) -> ((Либо a) c) , как требуется.

В вашей версии, которая потерпела неудачу, мы имеем, что x в (Right (x)) не относится к типу a , а к типу b , поэтому (Right (x)) является не типа ((Either a) c) , что не соответствует типу fmap.

подведем итог: получается работающий fmap: (b -> c) -> (Либо a) b -> (Либо a) c , но выходит тот, который не работает: (b -> c) -> (Либо b) a -> (Либо c) a , и это не тот тип для fmap.

(Отредактируйте, чтобы попытаться лучше ответить на вопрос)

Определение Either:

data Either a b = Left a | Right b

Итак, «Either» принимает два аргумента типа. Между прочим, технически «Either» на самом деле не тип, а конструктор типа; для создания типа требуются аргументы типа.

Определение Functor:

class Functor f where
   fmap :: (p -> q) -> f p -> f q

Итак, в этом определении класса любой тип «f», который является экземпляром Functor, должен принимать аргумент типа. Это не декларируется; это выводится из «f p» и «f q»; поскольку здесь "f" задается параметр типа, он должен быть типом, который его принимает.

(Примечание: в исходном определении использовались «a» и «b» вместо «p» и «q». Я использую разные буквы, чтобы отличать слова от «Either ab», когда я перейду к этому позже)

В большинстве случаев «f» - это контейнерный тип, такой как список или дерево. Так, например, у вас есть

data Tree a = ...

instance Functor Tree where
   fmap func_a2b tree_of_a = ... --  tree of b.

. Однако «Либо» принимает два параметра типа, так как мы можем вписать его в эту схему? Ответ заключается в том, что типы могут иметь частичное применение, как и функции. Точно так же, как Я могу объявить функцию

foo x y = ...

, а затем сказать «foo 2», чтобы получить новую функцию, которая ожидает второй аргумент, поэтому я могу сказать «Либо a», чтобы получить новый тип, который ожидает второй аргумент типа.

Теперь посмотрим на исходный экземпляр:

instance Functor (Either a) where ....

Итак, здесь «Either a» - это конструктор типа, который ожидает еще один аргумент, точно так же, как Functor ожидает от своих экземпляров. Таким образом, тип «fmap» для «Either a» будет

fmap :: (p -> q) -> Either a p -> Either a q

Итак, теперь в предложении «where» вы должны дать определение «fmap», имеющее этот тип.Первый, который вы цитируете, имеет этот тип, потому что второй параметр типа используется для конструктора «Right», и именно к нему применяется функция. Второй не будет работать, потому что он будет иметь тип

fmap :: (p -> q) -> Either p a -> Either q a

. И это не то, что класс Functor утверждает, что он будет.

Top работает, потому что fmap: :( b -> c) -> Либо ab -> Либо ac и ваш -bottom- не работают, потому что это могло бы require fmap: :( a -> c) -> Либо ab -> Либо ac . Но это сработает, если вы измените Either на

data Either' a b = Left' b | Right' a deriving (Eq, Show)

instance Functor (Either' a) where  
    fmap f (Right' x) = Right' (x)  
    fmap f (Left' x) = Left' (f x)

Эм ... Как насчет "видов"? ..
Думаю, это может упростить понимание.
Помните, что такое карри. Т.е. в ghci:

Prelude> let f x y z = x + y * z
f :: (Num a) => a -> a -> a -> a
Prelude> :t f 1
f 1 :: (Num t) => t -> t -> t
Prelude> :t f 1 2
f 1 2 :: (Num t) => t -> t
Prelude> :t f 1 2 3
f 1 2 3 :: (Num t) => t

То же, что и с типами. Когда вы говорите Либо тип этого типа * -> * -> * (т.е. он принимает два типа и производит тип), либо когда вы говорите Либо kind является * -> * , а для Либо ab это * (кстати, Monad a и Functor a требует a должно быть вроде * -> * , насколько я помню). Итак, когда вы говорите type Либо a , что означает тип, который все еще является неполным (требуется привязка некоторого «аргумента»), поэтому fmap :: (a -> b) -> fa -> fb становится fmap :: (a -> b) -> (Либо c) a -> (Либо c) b , когда f заменяется на Либо c ].