Пусть функции Хаскелла погружаются.

Ответ 1

Здесь класс функтора:

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

Обратите внимание, что "f" сам по себе является конструктором типа, поскольку он применяется к переменной типа в строке fmap. Вот несколько примеров, чтобы сделать это ясно:

Конструкторы типов:

IO
Maybe
Either String

Типы:

IO Char
Maybe a
Either String String

"Может быть," - это тип с одним конструктором типа ( "Может быть" ) и одной переменной типа ( "a" ). Это еще не что-то конкретное, но оно может использоваться в сигнатурах типов для полиморфных функций.

"Либо" - это конструктор типа, который принимает два аргумента типа, поэтому даже после его применения (например, Either String он все еще является конструктором типа, потому что он может принимать другой аргумент типа.

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

Когда вы пишете instance Functor (Either c), Either c заполняется для f везде в объявлении fmap. Это дает fmap следующий тип для этого экземпляра:

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

С помощью определения Either единственным полезным способом получить этот тип является применение значения Right к функции. Помните, что "Либо" имеет два возможных значения с разными типами. Здесь значение Left имеет тип "c", поэтому вы не можете применить его к функции (которая ожидает "a" ) [1], и результат также будет неправильным, потому что вы останетесь с Either b a, который не соответствует определению класса.

После замены "f" на "Либо c", чтобы получить указанную выше сигнатуру типа для fmap с экземпляром "Либо c", следующая запись реализации. Есть два случая, которые следует рассмотреть: левые и правые. Подпись типа говорит нам, что тип левой стороны, "c", не может измениться. У нас также нет способа изменить значение, потому что мы не знаем, какой тип он на самом деле. Все, что мы можем сделать, это оставить его в покое:

fmap f (Left rval) = Left rval

Для правой стороны подпись типа говорит о том, что мы должны перейти от значения с типом "a" к значению с типом "b". Первый аргумент - это функция, которая выполняет именно это, поэтому мы используем функцию с входным значением для получения нового вывода. Помещение двух вместе дает полное определение

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

Здесь более общий принцип работы, поэтому писать экземпляр Functor, который регулирует левую сторону, невозможно, по крайней мере, с определениями Prelude. Копирование кода выше:

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

instance Functor (Either c) where ...

Несмотря на то, что в определении экземпляра мы имеем переменную типа 'c', мы не можем использовать ее ни в одном из методов класса, потому что она не упоминается в определении класса. Поэтому вы не можете писать

leftMap :: (c -> d) -> Either c a -> Either d a
leftMap mapfunc (Left x) = Left (mapfunc x)
leftMap mapfunc (Right x) = Right x

instance Functor (Either c) where
  --fmap :: (c -> d) -> Either c a -> Either d a
  fmap = leftMap

Результат leftMap и, следовательно, fmap, теперь (Either d) a. (Either c) изменился на (Either d), но это не разрешено, потому что нет способа выразить его в классе Functor. Чтобы выразить это, вам понадобится класс с двумя переменными типа, например.

class BiFunctor f where
  lMap :: (a -> b) -> f a c -> f b c
  rMap :: (c -> d) -> f a c -> f a d
  biMap :: (a -> b) -> (c -> d) -> f a c -> f b d

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

instance BiFunctor Either where
  lMap = leftMap
  rMap = rightMap  --the same as the standard fmap definition
  biMap fl fr e = rMap fr (lMap fl e)

Хотя на практике люди обычно просто пишут "biMap" для класса BiFunctor и используют "id" для другой функции, если необходимо левое или правое отображение.

[1] Точнее, левое значение имеет тип "c", функция ожидает "a", но средство проверки типов не может объединить эти типы, потому что тип "c" не входит в область в классе определение.

Ответ 2

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

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)

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

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 являются независимыми произвольными типами.

Ответ 3

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

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

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

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

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

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

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

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

Изменить: попытка ответить на вопросы ниже.

1) Там нет "композиции из двух функций". Чтобы получить сигнатуру типа для fmap over Either a, просто просмотрите подпись функции fmap, и в каждом месте, где вы видите f, замените его на Either a. Мы будем называть это "специализацией" сигнатуры типа fmap. То есть он строго менее общий, чем обычный тип fmap - в любом месте, где требуется функция более специализированного типа, без каких-либо проблем вы можете передать что-то общее типа.

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

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

Если вы хотите получить очень технический, потому что вы можете отображать как левую, так и правую сторону (хотя вы можете объявить только Functor для последнего), либо это не только Functor, но и Bifunctor. Это представлено в, например, в библиотеке категории "Экстра" (см. 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.

Ответ 4

(Изменить, чтобы лучше ответить на вопрос)

Определение Либо:

data Either a b = Left a | Right b

Итак, "Либо" принимает два аргумента типа. Кстати, технически "Либо" на самом деле не тип, а конструктор типа; для создания типа он принимает аргументы типа.

Определение функтора:

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

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

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

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

data Tree a = ...

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

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

foo x y = ...

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

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

instance Functor (Either a) where ....

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

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

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

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

И это не то, о чем говорит класс Functor.

Ответ 5

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

Рассмотрим другой тип данных

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 -it не может. Что-то, что является экземпляром 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. Это означает, что (a) вы не можете применить к нему f, и (b) вы должны применить его к аргументу Right, так как в противном случае вы не измените тип, который вы ожидаете изменить.

Ответ 6

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

data  Either a b  =  Left a | Right b

... Примечание. Как сначала вводится переменная типа a, затем b, а также обратите внимание, что мы включаем только a в объявление любого из следующих:

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

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

instance Functor Maybe where
    fmap = map

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

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

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

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

Ответ 7

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

Во-первых, однако, некоторый фон:

1) Functor нуждается в "конструкторе типов", (а не типа типа per se,...), который "нуждается" в другом регулярном типе, который ему предоставляется, чтобы сформировать "полный тип", точно так же, как общий в Java/С++. Так, например, List - это Functor (это, кстати), или Array, потому что (среди прочего) полный тип не просто List, а List<A>. Так,: Функтор принимает "конструктор типов", неполный тип.

2) Either - это тип конструктора, который люди Хаскелла (читай: Эдвард Кемт и другие хорошо известные математически все звезды) называют бифунтером. Для этого требуется два типа, которые должны быть завершены. Например, полное использование Either: Either Integer String, что означает (да, да, "duh!" ) Это либо целое число (Left), либо строка (Right). Таким образом, это означает, что Either Integer является неполным типом, который является либо Left Integer, либо Right...b, когда вы решить, что такое "b".

Теперь, для забавной части!

Верхний файл работает, потому что fmap использует некоторый конструктор типов и использует его с функцией a -> b, чтобы сделать аналогичную функцию от f a до f b - пример любимого примера для этого в Haskell является таковой для списков, AKA map :: (a -> b) -> ([a] -> [b]), где Functor является частью [ ]. Теперь, используя что-то вроде Either a (отпустите и используйте Either Integer из ранее), подпись типа fmap выглядит следующим образом:

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

и два примера (из верхней части) показывают, что делает fmap с репрезентативными значениями этого типа Either Integer a, чтобы получить значение Either Integer b.

Теперь ваш -bottom- не работает, потому что:

• У вас есть функция f, которая принимает a до b s.
• Тип Left должен быть типом Целое число и остальное целое (или типа Float, и оставайтесь Float, что любой тип - это левая часть два типа типа Either вы используете).
• Тип Right должен быть независимо от того, что функция принимает ( "a" ) и переходит к типу что функция делает ( "b" ).

Он должен это сделать (но ваши вещи не работают - почему это не работает), потому что должен иметь тип, который должен иметь fmap. В частности, у вас есть следующие уравнения:

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

Ваши уравнения дают fmap типы:

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

который не только не подходит тем, что хочет fmap, но даже не согласуется между собой!

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

Ответ 8

Top работает, потому что fmap::(b -> c) -> Either a b -> Either a c и ваш -bottom- не работают, потому что для этого потребуется fmap::(a -> c) -> Either a b -> Either a c. Но это сработает, если вы изменили 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)

Ответ 9

Экземпляр, который вы пытаетесь написать, назовите его 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, которую я не вижу!)

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

Ответ 10

Эмм... Как насчет нескольких слов о "видах"?..
Возможно, это упростит понимание.
Помните, что такое карри. То есть в 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

То же самое, что у вас есть с типами. Когда вы говорите Either, тип этого типа * -> * -> * (т.е. Он принимает два типа и производит тип), и когда вы говорите Either a kind * -> * и для Either a b it * (btw Monad a и Functor a требует a быть добрым * -> *, как я помню). Поэтому, когда вы говорите, что тип Either a означает тип, который еще не завершен (требуется привязка некоторого "аргумента" ), поэтому fmap :: (a -> b) -> f a -> f b становится fmap :: (a -> b) -> (Either c) a -> (Either c) b, когда f заменяется на Either c.