Resolução irregular do tipo de furo

105

Recentemente, descobri que os furos de tipo combinados com a correspondência de padrões nas provas fornecem uma experiência bastante agradável como a de Agda em Haskell. Por exemplo:

{-# 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 

O que é realmente bom é que posso substituir os lados direitos das Refl -> expconstruções por um tipo de buraco, e meus tipos de alvo de buraco são atualizados com a prova, quase como com a rewriteforma em Agda.

No entanto, às vezes o buraco simplesmente falha ao atualizar:

(+.) :: 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...

Além disso, mesmo que os tipos de alvo não estejam necessariamente alinhados dentro da prova, se eu colar tudo do Agda ainda verificará bem:

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

Você tem alguma ideia de por que isso acontece (ou como eu poderia fazer a reescrita da prova de uma forma robusta)?

András Kovács
fonte
8
Você não está esperando muito? A correspondência de padrões em uma prova de igualdade está estabelecendo uma igualdade (bidirecional). Não está claro onde e em que direção você deseja que seja aplicado ao tipo de destino. Por exemplo, você pode omitir as symchamadas mulDistL'e seu código ainda será verificado.
Kosmikus
1
Muito possivelmente, estou esperando muito. No entanto, em muitos casos, ele funciona exatamente como no Agda, então ainda seria útil descobrir as regularidades do comportamento. Não estou otimista, já que o assunto provavelmente está profundamente relacionado com as entranhas do verificador de tipos.
András Kovács
1
É um pouco ortogonal à sua pergunta, mas você pode obter essas provas usando um conjunto de combinadores de raciocínio equacional à la Agda. Cf. esta prova de conceito
gallais

Respostas:

1

Se quiser gerar todos esses valores possíveis, você pode escrever uma função para fazer isso, com os limites fornecidos ou especificados.

Pode muito bem ser possível usar Números de Igreja em nível de tipo ou algo parecido para forçar a criação deles, mas é quase definitivamente muito trabalhoso para o que você provavelmente quer / precisa.

Isso pode não ser o que você deseja (ou seja, "Exceto para usar apenas (x, y), pois z = 5 - x - y"), mas faz mais sentido do que tentar ter algum tipo de restrição imposta no nível de tipo para permitir valores.

Billykart
fonte
-3

Isso acontece porque os valores são determinados em tempo de execução. Pode provocar uma transformação de valores dependendo do que é inserido em tempo de execução, portanto, assume que o furo já está atualizado.

ajay
fonte
3
Claro que os valores são determinados em tempo de execução, mas isso não tem nada a ver com a questão. As informações necessárias já estão disponíveis na correspondência de padrões em um GADT.
int_index