Могу ли я статически отклонить разные экземпляры экзистенциального типа? - PullRequest
Новая
       29

Могу ли я статически отклонить разные экземпляры экзистенциального типа?

4 голосов
/ 27 сентября 2011

Первая попытка

Трудно сделать этот вопрос содержательным, но чтобы привести минимальный пример, предположим, что у меня есть этот тип: 

{-# LANGUAGE GADTs #-}
data Val where
  Val :: Eq a => a -> Val

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

l = [Val 5, Val True, Val "Hello!"]

Но, увы, когда я записываю Eq экземпляр, все идет не так: 

instance Eq Val where
  (Val x) == (Val y) = x == y -- type error

Ах, значит, мы Could not deduce (a1 ~ a).Совершенно верно;в определении нет ничего, что говорит, что x и y должны быть одного типа.Фактически, весь смысл состоял в том, чтобы допустить возможность того, что они различаются.

Вторая попытка

Давайте добавим Data.Typeable в микс и попробуем сравнить два, только если они одного типа: 

data Val2 where
  Val2 :: (Eq a, Typeable a) => a -> Val2

instance Eq Val2 where
  (Val2 x) == (Val2 y) = fromMaybe False $ (==) x <$> cast y

Это довольноотлично.Если x и y имеют одинаковый тип, он использует базовый экземпляр Eq.Если они отличаются, он просто возвращает False.Однако эта проверка откладывается до времени выполнения, что позволяет nonsense = Val2 True == Val2 "Hello" проверять тип без жалоб.

Вопрос

Я понимаю, что заигрываю с зависимыми типами здесь, но возможно ли это для типа Haskellсистема статически отклоняет что-то вроде выше nonsense, в то же время позволяя что-то вроде sensible = Val2 True == Val2 False вернуть False во время выполнения?

Чем больше я работаю с этой проблемой, тем больше, кажется, мне нужно принятьнекоторые методы HList для реализации операций, которые мне нужны как функции уровня типа.Тем не менее, я относительно новичок в использовании существующих и GADT, и мне любопытно узнать, есть ли решение, которое можно найти именно с ними.Поэтому, если ответ «нет», я был бы очень признателен за обсуждение того, где именно проблема достигает предела этих функций, а также за толчок к подходящим методам, HList или другим.

Ответы [ 2 ]

13 голосов
/ 27 сентября 2011

Чтобы принимать решения по проверке типов на основе содержащихся типов, нам нужно «запомнить» содержащийся тип, выставив его в качестве параметра типа. 

data Val a where
  Val :: Eq a => a -> Val a

Теперь Val Int и Val Bool это разные типы, поэтому мы можем легко обеспечить, чтобы разрешались только сравнения одного типа. 

instance Eq (Val a) where
  (Val x) == (Val y) = x == y

Однако, поскольку Val Int и Val Bool - это разные типы, мы не можем смешивать их вместе в спискебез дополнительного слоя, который снова «забывает» содержащийся тип. 

data AnyVal where
  AnyVal :: Val a -> AnyVal

-- For convenience
val :: Eq a => a -> AnyVal
val = AnyVal . Val

Теперь мы можем написать 

[val 5, val True, val "Hello!"] :: [AnyVal]

Надеемся, теперь уже ясно, что вы не можете выполнить оба требования содин тип данных, поскольку для этого потребуется одновременно «забыть» и «запомнить» содержащийся тип одновременно.

7 голосов
/ 27 сентября 2011

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

Val True == Val "bar"  --> type error

allSame [] = True
allSame (x:xs) = all (== x) xs

allSame [Val True, Val "bar"]  --> False

Но обязательно: 

(x == y) = allSame [x,y]

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

...