haskell - que - como se forma un agujero negro

Resolución de tipo de agujero errático

Question

Recientemente descubrí que los agujeros de tipo combinados con la coincidencia de patrones en pruebas proporcionan una experiencia bastante agradable como la de Agda en Haskell. Por ejemplo:

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

Lo realmente bueno es que puedo reemplazar los lados derechos de las construcciones Refl -> exp por un agujero de tipo, y los tipos de objetivo de mi agujero se actualizan con la prueba, más o menos como con la forma de rewrite en Agda.

Sin embargo, a veces el agujero simplemente no se actualiza:

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

Además, aunque los tipos de destino no se alinean necesariamente dentro de la prueba, si pego todo desde Agda, todavía se comprueba bien:

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

¿Tiene alguna idea de por qué sucede esto (o cómo podría hacer la reescritura de pruebas de forma robusta)?

Answer 1

Si desea generar todos estos valores posibles, puede escribir una función para hacerlo, ya sea con límites proporcionados o especificados.

Es muy posible que sea posible utilizar Números de iglesia de nivel de tipo o algo así como para hacer cumplir la creación de estos, pero es casi seguro que es demasiado trabajo para lo que probablemente desee o necesite.

Puede que esto no sea lo que quiere (es decir, "excepto usar just (x, y) desde z = 5 - x - y") pero tiene más sentido que tratar de tener algún tipo de restricción forzada en el nivel de tipo para permitir la validez valores.

Answer 2

Sucede porque los valores se determinan en tiempo de ejecución. Puede provocar una transformación de valores en función de lo que se ingresa en el tiempo de ejecución, por lo tanto, supone que el agujero ya está actualizado.