Несоответствие подписи типа в определении экземпляра Bifunctor

Question

Я изучаю Haskell, работая над книгой Программирование на Haskell от First Principles, Allen & Moronuki .

В упражнениях к главе «Трансформаторы монад, функтор и аппликативная композиция», он просит читателя написать экземпляр Bifunctor для следующего типа

data SemiDrei a b c = SemiDrei a

Моя первая попытка (которая компилируется) была

instance Bifunctor (SemiDrei a) where
    bimap f g (SemiDrei a) = SemiDrei a

Но, глядя на это, мне показалось, чтоЯ должен быть в состоянии написать bimap f g = id, потому что последний аргумент получен без изменений, или написать bimap f g x = x. Оба дали мне ошибки компиляции, и я надеюсь, что кто-то может объяснить мне, почему я не могу выразить bimap с этими более короткими альтернативами, то есть, почему я должен указать (SemiDrei a).

Я выполнилэто на Haskell 8.6.5 (в случае необходимости)

попытка: id

instance Bifunctor (SemiDrei a) where
    bimap f g = id

-- compile error message:
• Couldn't match type ‘a1’ with ‘b’
  ‘a1’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  ‘b’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  Expected type: SemiDrei a a1 c -> SemiDrei a b d
    Actual type: SemiDrei a b d -> SemiDrei a b d
• In the expression: id
  In an equation for ‘bimap’: bimap f g = id
  In the instance declaration for ‘Bifunctor (SemiDrei a)’
• Relevant bindings include
    f :: a1 -> b (bound at src/Main.hs:69:11)
    bimap :: (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
      (bound at src/Main.hs:69:5)
   |
69 |     bimap f g = id
   |                 ^^

попытка: fgx = x

instance Bifunctor (SemiDrei a) where
    bimap f g x = x

-- compile error message:
• Couldn't match type ‘a1’ with ‘b’
  ‘a1’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  ‘b’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  Expected type: SemiDrei a b d
    Actual type: SemiDrei a a1 c
• In the expression: x
  In an equation for ‘bimap’: bimap f g x = x
  In the instance declaration for ‘Bifunctor (SemiDrei a)’
• Relevant bindings include
    x :: SemiDrei a a1 c (bound at src/Main.hs:69:15)
    f :: a1 -> b (bound at src/Main.hs:69:11)
    bimap :: (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
      (bound at src/Main.hs:69:5)
   |
69 |     bimap f g x = x
   |                   ^

Answer 1

Там последний аргумент фактически не остается неизменным: его тип меняется. Входные данные SemiDrei a x y, а выходные данные SemiDrei a p q, где f :: x -> p и g :: y -> q.

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

Но ваша интуиция верна: два значения имеют одинаковое представление в памяти. И GHC может вывести этот факт, и когда он это сделает, он автоматически разрешит для вас ограничение Coercible, что означает, что вы можете использовать функцию coerce для преобразования одного в другое:

 bimap _ _ = coerce

Answer 2

Это показывает ту же проблему в более простом случае:

data T a = K

foo :: T a -> T b
foo K = K  -- type checks

bar :: T a -> T b
bar x = x  -- type error

-- bar = id would also be a type error, for the same reason

Проблема здесь в том, что два значения K in foo скрывают свои параметры типа. Более точное определение было бы

-- pseudo code
foo (K @a) = K @b

Здесь вы можете видеть, что аргумент неявного типа изменяется. GHC автоматически выводит эти аргументы типа для нас, когда мы пишем K в определении foo. Поскольку они неявные, они выглядят , как если бы они были одинаковыми K s, но они не относятся к средству проверки типов.

Вместо этого, когда мы используем x в определениииз bar, нет никаких неявных аргументов типа для вывода. У нас есть это x :: T a и все. Мы не можем использовать x и утверждать, что он имеет другой тип T b.

Наконец, обратите внимание, что, используя «безопасные принуждения», мы можем выполнить интуитивно правильный вид - id, который превращает один K (в одном типе) в другой K другого типа:

import Data.Coerce

baz :: T a -> T b
baz = coerce

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

Answer 3

Ключ к этому находится в сигнатуре типа bimap:

bimap :: Bifunctor p => (a -> b) -> (c -> d) -> p a c -> p b d

В этом конкретном случае, если мы специализируемся p на SemiDrei a и переименовываем переменные типа, чтобы избежать путаницы счто a, мы получаем:

bimap :: (b -> c) -> (d -> e) -> SemiDrei a b d -> SemiDrei a c e

Итак, когда вы пытаетесь реализовать это:

bimap f g = ...

Функции f и g полностью произвольны, а не только вих реализация, но также и в их типах ввода и возврата. f имеет тип b -> c, где b и c могут быть абсолютно любыми - аналогично для g. Определение, которое вы даете, должно работать абсолютно для любых типов и функций, которые предоставляет вызывающая сторона - это то, что означает (параметрически) полиморфное.

Если мы теперь посмотрим на ваши три определения в этих терминах, мы можем решитькажущаяся тайна:

Первый:

bimap f g (SemiDrei a) = SemiDrei a

это совершенно нормально, как вы видели. SemiDrei a имеет тип SemiDrei a b c, где указывается только a. Это означает, что он может принимать любой тип, например SemiDrei a Int String, SemiDrei [Bool] (Char, [Double]) или любой другой. SemiDrei a сам по себе полиморфный, он может быть любого совместимого типа. Это означает, что, в частности, он может действовать как SemiDrei a b c и SemiDrei a c e в вышеуказанной подписи bimap.

Сравните с другими вашими попытками:

bimap f g = id

проблема здесь в том, что id, хотя и полиморфный, но не полиморфный достаточно для этой цели. Его тип a -> a (для любого a), который, в частности, может быть специализирован для SemiDrei a b c -> SemiDrei a b c. Но он не может быть специализирован для типа SemiDrei a b d -> SemiDrei a c e, как требуется, потому что b, c, d и e в общем случае будут совершенно разными типами. Вспомните, что вызывающий абонент из bimap может выбирать, какие типы - они могут легко выбирать функции f и g, где b и c, например, разные типы, итогда id не может принять от SemiDrei a b d до SemiDrei a c e, потому что это разные типы.

На этом этапе вы можете возразить, что значение SemiDrei a может быть значением всехтакие типы. Это совершенно верно, но это не имеет отношения к выводу типов - компилятор заботится только о типах, а не о том, какие значения могут их содержать. Следует учитывать, что разные типы имеют совершенно разные непересекающиеся значения. И, скажем, SemiDrei a Int String и SemiDrei a Bool Char на самом деле разные типы. Опять же, компилятор не знает, что Int и т. Д. На самом деле не используются ни одним из значений типа. Именно поэтому такие «фантомные типы» (типы, которые появляются в определении типа, но не в любом из их конструкторов данных) используются на практике - чтобы компилятор мог различать их по типу, даже если во время выполненияпредставление может быть полностью эквивалентным.

Что касается вашей третьей попытки, bimap f g x = x, это в точности то же самое, что и предыдущая - она ​​ограничивает bimap f g тем, что ее тип вывода совпадает с ее вводом. (На самом деле это полностью эквивалентно bimap f g = id.)

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