Crear una concatenación completamente dependiente

10

Un buen hecho verdadero sobre la concatenación es que si conozco dos variables en la ecuación:

a ++ b = c

Entonces sé el tercero.

Me gustaría capturar esta idea en mi propia concat, así que uso una dependencia funcional.

{-# Language DataKinds, GADTs, FlexibleContexts, FlexibleInstances, FunctionalDependencies, KindSignatures, PolyKinds, TypeOperators, UndecidableInstances #-}
import Data.Kind (Type)

class Concatable
   (m  :: k -> Type)
   (as :: k)
   (bs :: k)
   (cs :: k)
   | as bs -> cs
   , as cs -> bs
   , bs cs -> as
   where
     concat' :: m as -> m bs -> m cs

Ahora conjuro una lista heterogénea así:

data HList ( as :: [ Type ] ) where
  HEmpty :: HList '[]
  HCons  :: a -> HList as -> HList (a ': as)

Pero cuando trato de declarar esto ya Concatableque tengo un problema

instance Concatable HList '[] bs bs where
  concat' HEmpty bs = bs
instance
  ( Concatable HList as bs cs
  )
    => Concatable HList (a ': as) bs (a ': cs)
  where
    concat' (HCons head tail) bs = HCons head (concat' tail bs)

No satisfago mi tercera dependencia funcional. O más bien, el compilador cree que nosotros no. Esto se debe a que el compilador cree que en nuestra segunda instancia podría ser el caso bs ~ (a ': cs). Y podría ser el caso si Concatable as (a ': cs) cs.

¿Cómo puedo ajustar mis instancias para que se satisfagan las tres dependencias?

Sriotchilism O'Zaic
fuente
1
El problema clave parece ser bs cs -> as, porque necesitamos información no local sobre bsy csdecidir si asdebería ser una desventaja o no. Necesitamos descubrir cómo representar esta información; ¿Qué contexto agregaríamos a una firma de tipo para garantizarla cuando no se puede deducir directamente?
luqui
3
Para ampliar lo que dijo luqui: imagina que sabemos bsy csqueremos explotar el fundep, es decir, queremos reconstruir as. Para hacerlo de una manera determinista, esperamos poder comprometernos con una sola instancia y seguir esa receta. Concretamente, asumir bs = (Int ': bs2)y cs = (Int ': cs2). ¿Qué instancia elegimos? Es posible que tal Inten csproviene de bs(y asestá vacía). También es posible que provenga de (no vacío) asy que Intvuelva a aparecer más csadelante. Necesitamos profundizar cspara saber y GHC no lo hará.
chi
1
En términos generales, GHC aceptará fundeps que pueden probarse utilizando una forma simple de inducción de las instancias. Aquí, uno de ellos requiere un tipo de doble inducción para ser probado (o eso parece), y el compilador no llegará tan lejos.
chi

Respuestas:

10

Entonces, como sugieren los comentarios, GHC no lo resolverá por sí solo, pero podemos ayudarlo con un poco de programación a nivel de tipo. Vamos a presentar algunos TypeFamilies. Todas estas funciones son traducciones bastante sencillas de manipulación de listas elevadas al nivel de tipo:

-- | This will produce the suffix of `cs` without `as`
type family DropPrefix (as :: [Type]) (cs :: [Type]) where
  DropPrefix '[] cs = cs
  DropPrefix (a ': as) (a ': cs) = DropPrefix as cs

-- Similar to the logic in the question itself: list concatenation. 
type family Concat (as :: [Type]) (bs :: [Type]) where
  Concat '[] bs = bs
  Concat (head ': tail) bs = head ': Concat tail bs

-- | Naive list reversal with help of concatenation.
type family Reverse (xs :: [Type]) where
  Reverse '[] = '[]
  Reverse (x ': xs) = Concat (Reverse xs) '[x]

-- | This will produce the prefix of `cs` without `bs`
type family DropSuffix (bs :: [Type]) (cs :: [Type]) where
  DropSuffix bs cs = Reverse (DropPrefix (Reverse bs) (Reverse cs))

-- | Same definition of `HList` as in the question
data HList (as :: [Type]) where
  HEmpty :: HList '[]
  HCons :: a -> HList as -> HList (a ': as)

-- | Definition of concatenation at the value level
concatHList :: (cs ~ Concat as bs) => HList as -> HList bs -> HList cs
concatHList HEmpty bs = bs
concatHList (HCons head tail) bs = HCons head (concatHList tail bs)

Con estas herramientas a nuestra disposición, podemos llegar al objetivo por hora, pero primero definamos una función con las propiedades deseadas:

  • Capacidad para deducir csa partir de asybs
  • Capacidad para deducir asa partir de bsycs
  • Capacidad para deducir bsa partir de asycs

Voila

concatH ::
     (cs ~ Concat as bs, bs ~ DropPrefix as cs, as ~ DropSuffix bs cs)
  => HList as
  -> HList bs
  -> HList cs
concatH = concatHList

Probémoslo:

foo :: HList '[Char, Bool]
foo = HCons 'a' (HCons True HEmpty)

bar :: HList '[Int]
bar = HCons (1 :: Int) HEmpty
λ> :t concatH foo bar
concatH foo bar :: HList '[Char, Bool, Int]
λ> :t concatH bar foo
concatH bar foo :: HList '[Int, Char, Bool]

Y finalmente el objetivo final:

class Concatable (m :: k -> Type) (as :: k) (bs :: k) (cs :: k)
  | as bs -> cs
  , as cs -> bs
  , bs cs -> as
  where
  concat' :: m as -> m bs -> m cs

instance (cs ~ Concat as bs, bs ~ DropPrefix as cs, as ~ DropSuffix bs cs) =>
         Concatable HList as bs cs where
  concat' = concatH
λ> :t concat' HEmpty bar
concat' HEmpty bar :: HList '[Int]
λ> :t concat' foo bar
concat' foo bar :: HList '[Char, Bool, Int]
λ> :t concat' bar foo
concat' bar foo :: HList '[Int, Char, Bool]
lehins
fuente
3
¡Bien hecho! Incluso sospeché que esto podría ser imposible, pero lo resolvió de manera transparente y elegante.
luqui
Gracias, @luqui
lehins