Неустойчивое разрешение типа отверстия

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

{-# LANGUAGE
    DataKinds, PolyKinds, TypeFamilies, 
    UndecidableInstances, GADTs, TypeOperators #-}

data (==) :: k -> k -> * where
    Refl :: x == x

sym :: a == b -> b == a
sym Refl = Refl 

data Nat = Zero | Succ Nat

data SNat :: Nat -> * where
    SZero :: SNat Zero
    SSucc :: SNat n -> SNat (Succ n)

type family a + b where
    Zero   + b = b
    Succ a + b = Succ (a + b)

addAssoc :: SNat a -> SNat b -> SNat c -> (a + (b + c)) == ((a + b) + c)
addAssoc SZero b c = Refl
addAssoc (SSucc a) b c = case addAssoc a b c of Refl -> Refl

addComm :: SNat a -> SNat b -> (a + b) == (b + a)
addComm SZero SZero = Refl
addComm (SSucc a) SZero = case addComm a SZero of Refl -> Refl
addComm SZero (SSucc b) = case addComm SZero b of Refl -> Refl
addComm sa@(SSucc a) sb@(SSucc b) =
    case addComm a sb of
        Refl -> case addComm b sa of
            Refl -> case addComm a b of
                Refl -> Refl 

На самом деле приятно то, что я могу заменить правые части конструкций Refl -> exp на типовое отверстие, а мои целевые типы отверстий обновляются с помощью доказательства, почти так же, как с формой rewrite в Agda.

Однако иногда дыра просто не обновляется:

(+.) :: SNat a -> SNat b -> SNat (a + b)
SZero   +. b = b
SSucc a +. b = SSucc (a +. b)
infixl 5 +.

type family a * b where
    Zero   * b = Zero
    Succ a * b = b + (a * b)

(*.) :: SNat a -> SNat b -> SNat (a * b)
SZero   *. b = SZero
SSucc a *. b = b +. (a *. b)
infixl 6 *.

mulDistL :: SNat a -> SNat b -> SNat c -> (a * (b + c)) == ((a * b) + (a * c))
mulDistL SZero b c = Refl
mulDistL (SSucc a) b c = 
    case sym $ addAssoc b (a *. b) (c +. a *. c) of
        -- At this point the target type is
        -- ((b + c) + (n * (b + c))) == (b + ((n * b) + (c + (n * c))))
        -- The next step would be to update the RHS of the equivalence:
        Refl -> case addAssoc (a *. b) c (a *. c) of
            Refl -> _ -- but the type of this hole remains unchanged...

Кроме того, хотя целевые типы не обязательно совпадают внутри доказательства, если я вставляю все это из Agda, он все равно проверяет нормально:

mulDistL' :: SNat a -> SNat b -> SNat c -> (a * (b + c)) == ((a * b) + (a * c))
mulDistL' SZero b c = Refl
mulDistL' (SSucc a) b c = case
    (sym $ addAssoc b (a *. b) (c +. a *. c),
    addAssoc (a *. b) c (a *. c),
    addComm (a *. b) c,
    sym $ addAssoc c (a *. b) (a *. c),
    addAssoc b c (a *. b +. a *. c),
    mulDistL' a b c
    ) of (Refl, Refl, Refl, Refl, Refl, Refl) -> Refl

У вас есть идеи, почему это происходит (или как я могу надежно переписать корректуру)?


person András Kovács    schedule 27.02.2014    source источник
comment
Разве вы не ожидаете многого? Сопоставление с образцом в доказательстве равенства устанавливает (двунаправленное) равенство. Совершенно не ясно, где и в каком направлении вы хотите применить его к целевому типу. Например, вы можете опустить sym вызовы в mulDistL', и ваш код все равно будет проверять.   -  person kosmikus    schedule 28.02.2014
comment
Вполне возможно, я слишком многого жду. Однако во многих случаях он работает так же, как в Agda, поэтому было бы полезно выяснить закономерности поведения. Однако я не оптимистичен, поскольку дело, скорее всего, глубоко связано с недрами типографа.   -  person András Kovács    schedule 28.02.2014
comment
Это немного ортогонально вашему вопросу, но вы можете получить эти доказательства, используя набор комбинаторов рассуждений по уравнениям а-ля Agda. Ср. это доказательство концепции   -  person gallais    schedule 13.10.2017


Ответы (2)


Если вы хотите сгенерировать все возможные такие значения, вы можете написать для этого функцию с предоставленными или указанными границами.

Вполне возможно, что можно будет использовать церковные цифры уровня типа или что-то подобное, чтобы принудительно создать их, но это почти определенно слишком много работы для того, что вы, вероятно, хотите / нужно.

Это может быть не то, что вы хотите (например, «За исключением использования только (x, y), поскольку z = 5 - x - y»), но это имеет больше смысла, чем попытки иметь какое-то принудительное ограничение на уровне типа для разрешения допустимых ценности.

person Billykart    schedule 02.01.2018

Это происходит потому, что значения определяются во время выполнения. Он может вызвать преобразование значений в зависимости от того, что вводится во время выполнения, поэтому предполагается, что отверстие уже обновлено.

person ajay    schedule 20.05.2014
comment
Конечно, значения определяются во время выполнения, но это не имеет никакого отношения к вопросу. Необходимая информация уже доступна из сопоставления с образцом в GADT. - person int_index; 23.03.2016