При вводе конструкции case (будь то явное выражение case или неявное определение функции на основе шаблона) при отсутствии GADT, отдельные альтернативы:
pattern -> body
можно объединить, набрав все шаблоны и объединив их с типом проверяемого, затем набрав все тела и объединив их с типом выражения case в целом. Таким образом, в простом примере, таком как:
data U = UA | UB | UC
isA1 u = case u of
UA -> True
UB -> False
x -> False
, мы можем изначально набирать шаблоны UA :: U, UB :: U, x :: a, объединять их, используя равенство типов a ~ U, чтобы вывести тип scrutinee u :: U и аналогичным образом унифицируют True :: Bool и оба False :: Bool с типом общего выражения регистра Bool, объединяя его с типом isA для получения isA :: U -> Bool.
Обратите внимание, что процесс унификации может специализироваться на типах. Здесь тип шаблона x :: a был общим, но к концу процесса объединения он был специализирован для x :: U. Это может случиться и с телами тоже. Например:
len mstr = case mstr of
Nothing -> 0
Just str -> length str
Здесь 0 :: Num a => a - это полиморф c, а потому что length возвращает Int, к концу процесса, тела (и, таким образом, все выражение case) ) были объединены в тип Int.
В целом, через объединение общий, объединенный тип всех тел (и, следовательно, тип общего выражения падежа) будет «наиболее общим» / «наименее ограничительный» тип, типы тел которого являются обобщениями. В некоторых случаях этот тип может быть типом одного из тел, но в целом все тела могут быть более общими, чем «наиболее общий» унифицированный тип, но ни одно тело не может быть более ограничительным .
Ситуация меняется в присутствии ГАДЦ. Когда конструкции случая проверки типа с помощью GADT, шаблоны в альтернативе могут вводить «уточнение типа», набор дополнительных привязок переменных типа, которые будут использоваться при проверке типа тела альтернативы. (Это то, что делает ГАДЦ полезными в первую очередь.)
Поскольку тела разных альтернатив набираются с разными уточнениями, наивное объединение невозможно. Например, рассмотрим крошечный типизированный DSL и его интерпретатор:
data Term a where
Lit :: Int -> Term Int
IsZ :: Term Int -> Term Bool
If :: Term Bool -> Term a -> Term a -> Term a
eval :: Term a -> a
eval t = case t of
Lit n -> n
IsZ t -> eval t == 0
If b t e -> if eval b then eval t else eval e
Если бы мы наивно унифицировали тела n :: Int, eval t == 0 :: Bool и if eval b then eval t else eval e :: a, программа не провела бы проверку типа ( наиболее очевидно, потому что Int и Bool не объединяются!).
В общем, поскольку уточнения типов позволяют вычисленным типам тел альтернатив быть больше конкретизировать c, чем последний тип, нет очевидного «наиболее общего» / «наименее ограничительного» типа, к которому можно объединить все тела, как это было для выражения case без GADT.
Вместо этого нам обычно нужно сделать доступным тип «target» для общего выражения case (например, для eval, тип возврата a в сигнатуре типа), а затем определить, вводится ли при каждом уточнении конструктор (например, IsZ вводит уточнение a ~ Bool), тело eval t == 0 :: Bool имеет в качестве типа связанный уточнение из a.
Если целевой тип явно не указан, то лучшее, что мы можем сделать - в общем случае - это использование переменной типа fre sh p в качестве цели и попытка проверить каждый уточненный тип по этому.
Это означает, что, учитывая следующее определение без сигнатуры типа для isA2:
data P t where
PA :: P Int
PB :: P Double
PC :: P Char
isA2 = \p -> case p of
PA -> True
PB -> False
PC -> False
то, что пытается сделать GH C, это тип isA2 :: P t -> p. Для альтернативы:
PA -> True
он набирает PA :: P t, давая уточнение t ~ Int, и при этом уточнении пытается набрать True :: p. К сожалению, p не является Bool ни при каком уточнении, связанном с несвязанной переменной типа a, и мы получаем ошибку. Аналогичные ошибки генерируются и для других альтернатив.
На самом деле, есть еще одна вещь, которую мы можем сделать. Если есть альтернативы, которые не вводят уточнение типа, то вычисленные типы их тел на NOT более конкретны c, чем окончательный тип. Таким образом, если мы унифицируем типы тела для «неопределяемых» альтернатив, результирующий тип обеспечивает законную цель объединения для уточненных альтернатив.
Это означает, что, например,
isA3 = \p -> case p of
PA -> True
x -> False
вторая альтернатива:
x -> False
набирается путем сопоставления с шаблоном x :: P t, который не вводит уточнения типа. Неопределенный тип тела - Bool, и этот тип является подходящей целью для объединения других альтернатив.
В частности, первая альтернатива:
PA -> True
соответствует типу уточнение a ~ Int. При этом уточнении фактический тип тела True :: Bool соответствует «уточнению» целевого типа Bool (который «уточнен» до Bool), и определено, что альтернатива имеет действительный тип.
Таким образом, интуиция заключается в том, что без альтернативы с подстановочными символами предполагаемый тип для выражения case является переменной произвольного типа p, которая является слишком общей, чтобы ее можно было объединить с альтернативами уточнения типа. Однако при добавлении альтернативы подстановочного знака _ -> False в процесс объединения вводится более ограничительный тип тела Bool, который, будучи выведенным без какого-либо уточнения типа шаблоном _, может информировать алгоритм объединения, предоставляя более ограничительный тип Bool, к которому могут быть унифицированы другие, уточненные альтернативы типа.
Выше я сделал это звучит так, как будто существует какой-то двухфазный подход, где «не уточняющие» альтернативы сначала исследуются для определения целевого типа, а затем проверяются альтернативы уточнения.
Фактически, происходит то, что процесс уточнения вводит переменные fre sh в процесс объединения, который, даже когда они объединены, не влияют на контекст большего типа. Таким образом, все альтернативы объединяются одновременно, но объединение нерафинированных альтернатив влияет на более широкий контекст типа, в то время как унификация уточненных альтернатив влияет на кучу переменных fre sh, давая тот же конечный результат, как если бы нерафинированные и уточненные альтернативы были обрабатывается отдельно.