Почему система типов отказывается от моей, казалось бы, действительно действующей программы?

Обратите внимание на эту программу:

class Convert a b where
    convert :: a -> b

data A = A deriving Show
data B = B deriving Show
data C = C deriving Show
data D = DA A | DB B | DC C deriving Show

instance Convert A A where convert A = A
instance Convert A B where convert A = B
instance Convert A C where convert A = C
instance Convert B A where convert B = A
instance Convert B B where convert B = B
instance Convert B C where convert B = C
-- There is no way to convert from C to A
instance Convert C B where convert C = B
instance Convert C C where convert C = C

get (DA x) = convert x
get (DB x) = convert x
get (DC x) = convert x

main = do
    print (get (DC C) :: B) -- Up to this line, code compiles fine.
    print (get (DB B) :: A) -- Add this line and it doesn't, regardless of having a way to convert from B to A!

Существуют экземпляры для преобразования из C в B и от B до A. Тем не менее, GHC typechecks первый, но не подходит для последнего. При проверке кажется, что он не может вывести достаточно общий тип для get:

get :: (Convert A b, Convert B b, Convert C b) => D -> b

Я хочу выразить: get:: (Convert a_contained_by_D b) = > D → b, что кажется невозможным. Есть ли способ реализовать и скомпилировать функцию, которая делает то, что делает мой get, без изменения остальной части настройки?

Ответ 1

Если ваша программа действительно показалась вам действительной, тогда вы сможете написать тип get, который выполняет задание, которое вы хотите в Haskell, а не в ручном режиме. Позвольте мне помочь вам улучшить вашу руку и раскрыть причину, по которой вы просите луну на палочке.

Я хочу выразить: get :: (Convert a_contained_by_D b) => D -> b, что кажется невозможным.

Как сказано, это не так точно, как вам нужно. Действительно, это то, что Хаскелл дает вам сейчас, в том, что

get :: (Convert A b, Convert B b, Convert C b) => D -> b

любой a, который может содержаться в D, требуется по одному за раз, чтобы быть конвертируемым в это b. И вот почему вы получаете классическую логику системного администратора: no D разрешено получать, если только они не могут b.

Проблема заключается в том, что вам нужно знать статус не того типа, который может содержаться в любом старом D, а скорее типа, содержащегося в конкретном D, который вы получаете в качестве ввода. Правильно? Вы хотите

print (get (DB B) :: A)  -- this to work
print (get (DC C) :: A)  -- this to fail

но DB B и DC C - это всего лишь два разных элемента D, и что касается системы типов Haskell, то в каждом типе все разные те же. Если вы хотите различать элементы D, вам нужен тип D -pendent. Вот как я напишу его в ручном режиме.

DInner :: D -> *
DInner (DA a) = A
DInner (DB b) = B
DInner (DC c) = C

get :: forall x. pi (d :: D) -> (Convert (DInner d) x) => x
get (DA x) = convert x
get (DB x) = convert x
get (DC x) = convert x

где pi - это форма привязки для данных, которые передаются во время выполнения (в отличие от forall), но от которых могут зависеть типы (в отличие от ->). Теперь ограничение говорит не о произвольном D, а о самом d :: D в вашей руке, и ограничение может точно вычислить, что нужно, проверив его DInner.

Нет ничего, что можно сказать, что он уйдет, но мой pi.

К сожалению, пока pi быстро спускается с неба, он еще не приземлился. Тем не менее, в отличие от луны, его можно достичь палкой. Несомненно, вы будете жаловаться на то, что я меняю настройку, но на самом деле я просто переводил вашу программу из Haskell примерно в 2017 году в Haskell в 2015 году. Вы вернетесь к ней, когда-нибудь, с тем же типом, что и с рук.

Вы ничего не можете сказать, но можете петь.

Шаг 1. Включите DataKinds и KindSignatures и создайте синглтоны для ваших типов (или попросите Ричарда Эйзенберга сделать это за вас).

data A = A deriving Show
data Aey :: A -> * where  -- think of "-ey" as an adjectival suffix
  Aey :: Aey 'A           -- as in "tomatoey"

data B = B deriving Show
data Bey :: B -> * where
  Bey :: Bey 'B

data C = C deriving Show
data Cey :: C -> * where
  Cey :: Cey 'C

data D = DA A | DB B | DC C deriving Show
data Dey :: D -> * where
  DAey :: Aey a -> Dey (DA a)
  DBey :: Bey b -> Dey (DB b)
  DCey :: Cey c -> Dey (DC c)

Идея состоит в том, что (i) типы данных становятся видами и (ii) что синглеты характеризуют данные на уровне типа, которые имеют представление времени выполнения. Таким образом, тип уровня DA a существует во время выполнения, если a does и т.д.

Шаг 2. Угадайте, кто придет к DInner. Включить TypeFamilies.

type family DInner (d :: D) :: * where
  DInner (DA a) = A
  DInner (DB b) = B
  DInner (DC c) = C

Шаг 3. Получите несколько RankNTypes, и теперь вы можете написать

get :: forall x. forall d. Dey d -> (Convert (DInner d) x) => x
--               ^^^^^^^^^^^^^^^^^^
-- this is a plausible fake of pi (d :: D) ->

Шаг 4. Попробуйте написать get и завинтить. Нам приходится сопоставлять доказательства времени выполнения, что тип уровня D является представимым. Нам нужно это, чтобы получить уровень типа D, специализированный в вычислении DInner. Если бы у нас был правильный pi, мы могли бы сопоставлять значение D, которое обслуживает двойной долг, но на данный момент вместо этого следует сопоставлять Dey d.

get (DAey x) = convert x   -- have x :: Aey a, need x :: A
get (DBey x) = convert x   -- and so on
get (DCey x) = convert x   -- and so forth

Безусловно, наши x es теперь являются одноточечными, где, <<245 > , нам нужны базовые данные. Нам нужно больше одноэлементного устройства.

Шаг 5. Внедрите и создайте экземпляр класса singleton, чтобы "понизить уровень" значения уровня уровня (если мы знаем их представителей времени выполнения). Опять же, библиотека Ричарда Эйзенберга singletons может использовать Template-Haskell для этого шаблона, но давайте посмотрим, что происходит

class Sing (s :: k -> *) where   -- s is the singleton family for some k
  type Sung s :: *               -- Sung s is the type-level version of k
  sung :: s x -> Sung s          -- sung is the demotion function

instance Sing Aey where
  type Sung Aey = A
  sung Aey = A

instance Sing Bey where
  type Sung Bey = B
  sung Bey = B

instance Sing Cey where
  type Sung Cey = C
  sung Cey = C

instance Sing Dey where
  type Sung Dey = D
  sung (DAey aey) = DA (sung aey)
  sung (DBey bey) = DB (sung bey)
  sung (DCey cey) = DC (sung cey)

Шаг 6. Сделайте это.

get :: forall x. forall d. Dey d -> (Convert (DInner d) x) => x
get (DAey x) = convert (sung x)
get (DBey x) = convert (sung x)
get (DCey x) = convert (sung x)

Будьте уверены, что если у нас есть правильный pi, те DAey будут действительными DA, а те x больше не будут sung. Мой тип ручной работы для get будет Haskell, а ваш код для get будет в порядке. Но тем временем

main = do
  print (get (DCey Cey) :: B)
  print (get (DBey Bey) :: A)

typechecks просто отлично. Это означает, что ваша программа (плюс DInner и правильный тип для get) выглядит как действительный Dependent Haskell, и мы почти там.

Ответ 2

Чтобы этот код работал, он должен был работать с любым аргументом того же типа. То есть, если

get (DB B) :: A

работает тогда

get anyValueOfTypeD :: A

должен работать, включая

get (DC C) :: A

который не может работать из-за отсутствующего экземпляра с C на A.

Первая строка

get anyValueOfTypeD :: B

работает, потому что у нас есть все три экземпляра для преобразования A, B, C в B.

Я не думаю, что есть обходное решение, позволяющее оставить тип D таким, какой он есть. Если вы можете изменить это, вы можете использовать, например,

data D a = DA a | DB a | DC a

(помните, что он сильно отличается от оригинала) или даже GADT

data D x where
  DA :: A -> D A
  DB :: B -> D B
  DC :: C -> D C