Haskell, определяющий экземпляр Functor для альтернативного типа данных Either - PullRequest
5 голосов
/ 26 марта 2019

Прохождение Typeclassopedia для получения некоторой маршрутизации, работающей с классами типов. Я хочу сделать альтернативу Either экземпляру Functor, но даже изучение определения Either как экземпляра Functor продолжает вызывать у меня проблемы. Имейте это, но не скомпилируете.

data Alt a b = Success a | Failure b deriving (Show, Eq, Ord) 

instance Functor (Alt a) where 
  fmap _ (Failure a) = Failure a
  fmap f (Success x) = Success (f x)  

    • Couldn't match expected type ‘a1’ with actual type ‘a’
      ‘a1’ is a rigid type variable bound by
        the type signature for:
          fmap :: forall a1 b. (a1 -> b) -> Alt a a1 -> Alt a b
        at Brenty_tcop.hs:25:3-6
      ‘a’ is a rigid type variable bound by
        the instance declaration
        at Brenty_tcop.hs:24:10-24
    • In the first argument of ‘f’, namely ‘x’
      In the first argument of ‘Success’, namely ‘(f x)’
      In the expression: Success (f x)
    • Relevant bindings include
        x :: a (bound at Brenty_tcop.hs:26:19)
        f :: a1 -> b (bound at Brenty_tcop.hs:26:8)
        fmap :: (a1 -> b) -> Alt a a1 -> Alt a b
          (bound at Brenty_tcop.hs:25:3)
   |
26 |   fmap f (Success x) = Success (f x) 

1 Ответ

10 голосов
/ 27 марта 2019

Как говорит @chepner в комментариях , ваш код будет компилироваться, если вы переключите порядок параметров типа,

data Alt b a = Success a | Failure b

или, альтернативно, переключите , означающее экземпляра Functor, чтобы он отображался поверх Failure и оставлял Success в одиночку.

instance Functor (Alt a) where
    fmap f (Success x) = Success x
    fmap f (Failure x) = Failure (f x)

По сути, класс типа Functor знает только то, как отобразить последний тип типапараметр.Поэтому нам пришлось перенастроить все, чтобы мы применили функцию f к вхождению этого последнего параметра типа.


Почему вы можете отобразить только самый правый параметр,очень глубокий и интересный вопрос.Чтобы понять это, вы должны понимать types , которые являются расширенной функцией системы типов Haskell.

Вы можете думать о типах как о «следующем уровне» типов, в некотором смысле.Типы классифицируют значения;виды классифицируют типы.Так что "foo" - это String, а String - это тип.В Хаскеле «тип» произносится как *.

-- :t in ghci asks for the type of a value-level expression
ghci> :t "foo"
"foo" :: String

-- :k asks for the kind of a type-level expression
ghci> :k String
String :: *

Все обычные типы - те, которые могут иметь значения - имеют вид *.Итак, String :: *, Int :: *, Bool :: * и т. Д.

Все становится интересным, когда вы начинаете думать о параметризованных типах.Maybe сам по себе не является типом - вы не можете иметь значения типа Maybe, но вы можете иметь Maybe Int, Maybe String и т. Д. Так что Maybe - это своего рода функция - она ​​принимает типв качестве аргумента, и он производит тип.(Maybe - это конструктор типа , если использовать технический термин.)

-- Maybe is a function...
ghci> :k Maybe
Maybe :: * -> *

-- and you can apply it to an argument to get a type
ghci> :k Maybe Int
Maybe Int :: *

Alt - это функция с двумя параметрами.Функции типов в Haskell каррируются, как и обычные функции значений, поэтому Alt имеет тип * -> * -> * (что на самом деле означает * -> (* -> *)).

ghci> :k Alt
Alt :: * -> * -> *

Теперь Functor - это *Функция типа 1057 * высшего порядка .Он принимает аргумент f, который сам является функцией типа.Functor само по себе не является допустимым ограничением класса типов, но Functor f является.

ghci> :k Functor
Functor :: (* -> *) -> Constraint

Это означает, что Maybe само по себе, с видом * -> *, является допустимым аргументомдля функции типа Functor.Но Int :: * не является и не Maybe Int :: *, и не является Alt :: * -> * -> *.Сообщения об ошибках сообщают вам о несоответствии типов:

ghci> :k Functor Int
<interactive>:1:9: error:
    • Expected kind ‘* -> *’, but ‘Int’ has kind ‘*’
    • In the first argument of ‘Functor’, namely ‘Int’
      In the type ‘Functor Int’

ghci> :k Functor Alt
<interactive>:1:9: error:
    • Expecting one more argument to ‘Alt’
      Expected kind ‘* -> *’, but ‘Alt’ has kind ‘* -> * -> *’
    • In the first argument of ‘Functor’, namely ‘Alt’
      In the type ‘Functor Alt’

Система типов предназначена для предотвращения формирования недопустимых типов, подобно тому, как система типов предотвращает запись недопустимых значений.Если бы не было доброй системы, и нам было разрешено писать instance Functor Alt, то для fmap был бы получен следующий (бессмысленный) тип:

-- `Alt a` is not a valid type, because its second argument is missing!
fmap :: (a -> b) -> Alt a -> Alt b

Так что нам нужно превратить Alt :: * -> * -> * во что-тотипа * -> *, чтобы иметь действительный аргумент для Functor.Alt - это функция типа с карри, поэтому если мы передадим ей аргумент одного типа, мы получим функцию типа обратно!

ghci> :k Functor (Alt Int)
Functor (Alt Int) :: Constraint

Вот почему объявление instance говорит: instance Functor (Alt x) - этодолжен дать Alt аргумент (и в этом случае аргумент может быть любого типа x, пока его тип *).Теперь у нас есть fmap :: (a -> b) -> Alt x a -> Alt x b, которое является допустимым выражением типа.

Итак, в общем, рецепт создания экземпляра Functor должен начинаться с предоставления аргументов вашему типу, пока у него не останется только один параметр.Вот почему Functor знает, как отобразить самый правый параметр типа.В качестве упражнения вы можете попробовать определить класс Functor, который сопоставляется с параметром типа second -to-last.

Это большая тема, так что, надеюсь, я не пошел слишком быстро,Это нормально, чтобы не понимать виды сразу - это заняло у меня несколько попыток!Дайте мне знать в комментариях, если вы хотите, чтобы я объяснил вам что-то еще.

...