Приключения с типами в Haskell: GADT: почему следующие typechecks?

Question

Я следую за this lecture Саймон Пейтон-Джонс на GADT's. Там, следующие данные-тип объявлен:

data T a where 
    T0 :: Bool -> T Bool 
    T1 :: T a 

И тогда вопрос, который задают, что тип следующей функции:

f x y = case x of 
      T0 _ -> True 
      T1 -> y 

Для меня, кажется, единственно возможный тип это:

f :: T a -> Bool -> Bool 

Однако следующий тип:

f :: T a -> a -> a 

также действителен! И действительно, вы могли бы использовать f следующим образом:

f (T1) "hello" 

Мой вопрос, почему это второй тип подписи для f действительным?

Answer 1

Обычно, чтобы ввести проверить

case e of 
    K1 ... -> e1 
    K2 ... -> e2 
    ... 

требуется, чтобы все выражения ei имеют общий тип.

Это еще актуально при использовании GADTs, за исключением того, что в каждой отрасли конструктор обеспечивает некоторый тип равенства уравнений T ~ T' которые известнаят в этой отрасли. Следовательно, при проверке того, что все ei имеют общий тип, мы больше не требуем, чтобы их типы были идентичными, но только чтобы быть равными, когда сохраняются уравнения типа.

В частности:

f :: T a -> a -> a 
f x y = -- we know x :: T a , y :: a 
    case x of 
     T0 _ -> -- provides a ~ Bool 
       True -- has type Bool 
     T1 -> -- provides a ~ a (useless) 
       y  -- has type a 

Здесь нам нужно проверить Bool ~ a, которое было бы ложным в целом, но здесь становится истинным, потому что нам нужно только проверить это при условии равенства a ~ Bool. И в таком случае это становится правдой!

(Честно говоря, система типа делает что-то немного другое, проверку вместо этого, если обе ветви равны типа, объявленного в подписи (под их известными равенствами.) - но позвольте мне сохранить его простым для GADT сопоставления с образцом такой подписи всегда требуется в той или иной форме)

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

Answer 2

Есть два случая, в определении f и оба соответствуют вашей второй сигнатуре типа:

T0 _ -> True 

Здесь ваш аргумент был типа T Bool и ваш результат является Bool. Таким образом, это соответствует вашей тиковой сигнатуре для a ~ Bool.

T1 -> y 

Здесь ваш аргумент был тип T a и ваш результат y, который имеет тип a. Таким образом, это соответствует сигнатуре для любого a.

Чтобы понять, почему это типобезопасное, просто задайте себе следующий вопрос: Есть ли способ, что вы могли бы назвать f, так что результат не будет соответствовать сигнатуре типа? Как вы могли бы вернуть что-либо, кроме a, если вы прошли в T a и a?

И ответ: Нет, нет. Если вы перешли в T0 (то есть a - Bool), вы получите Bool. Если вы перешли в T1, вы вернете второй аргумент, который также будет иметь тип a. Если вы попытаетесь назвать его f (T1 :: T Int) "notAnInt", он не будет компилироваться, потому что типы не совпадают. Другими словами: Любое применение функции, которая соответствует сигнатуре типа, приведет к получению правильного типа результата в соответствии с сигнатурой. Поэтому f является безопасным по типу.