tipos - imprimir en haskell

¿Cómo expresar tipos existenciales usando un polimorfismo de rango más alto(rango N)?

Question

Estamos acostumbrados a tener tipos universalmente cuantificados para funciones polimórficas. Los tipos cuantificados existencialmente se utilizan con mucha menos frecuencia. ¿Cómo podemos expresar tipos cuantificados existencialmente utilizando cuantificadores de tipo universal?

Answer 1

Encontré un anwer en Proofs and Types por Jean-Yves Girard, Yves Lafont y Paul Taylor .

Imaginemos que tenemos un tipo de argumento único t :: * -> * y construimos un tipo existencial que contiene ta para algunos a : exists a. ta exists a. ta . ¿Qué podemos hacer con ese tipo? Para calcular algo, necesitamos una función que pueda aceptar ta para arbitrario a , que significa una función de tipo para todo forall a. ta -> b forall a. ta -> b . Sabiendo esto, podemos codificar un tipo existencial simplemente como una función que toma funciones de tipo para todo forall a. ta -> b forall a. ta -> b , les proporciona el valor existencial y devuelve el resultado b :

{-# LANGUAGE RankNTypes #-}

newtype Exists t = Exists (forall b. (forall a. t a -> b) -> b)

Crear un valor existencial ahora es fácil:

exists :: t a -> Exists t
exists x = Exists (/f -> f x)

Y si queremos descomprimir el valor existencial, simplemente aplicamos su contenido a una función que produce el resultado:

unexists :: (forall a. t a -> b) -> Exists t -> b
unexists f (Exists e) = e f

Sin embargo, los tipos puramente existenciales son de muy poco uso. No podemos hacer nada razonable con un valor del que no sabemos nada. Más a menudo necesitamos un tipo existencial con una restricción de clase de tipo. El procedimiento es el mismo, solo agregamos una restricción de clase de tipo para a . Por ejemplo:

newtype ExistsShow t = ExistsShow (forall b. (forall a. Show a => t a -> b) -> b)

existsShow :: Show a => t a -> ExistsShow t
existsShow x = ExistsShow (/f -> f x)

unexistsShow :: (forall a. Show a => t a -> b) -> ExistsShow t -> b
unexistsShow f (ExistsShow e) = e f

Nota: Usar la cuantificación existencial en programas funcionales a menudo se considera un olor de código . Puede indicar que no nos hemos liberado de OO pensando.

Answer 2

Resulta que los tipos existenciales son solo un caso especial de tipos ((tipos sigma). ¿Qué son?

Tipos Sigma

Así como los tipos ((tipos pi) generalizan nuestros tipos de funciones ordinarias, permitiendo que el tipo resultante dependa del valor de su argumento, Σ-types generaliza pares, permitiendo que el tipo de segundo componente dependa del valor del primero.

En una sintaxis inventada tipo Haskell, el tipo would se vería así:

data Sigma (a :: *) (b :: a -> *)
    = SigmaIntro
        { fst :: a
        , snd :: b fst
        }

-- special case is a non-dependent pair
type Pair a b = Sigma a (/_ -> b)

Suponiendo * :: * (es decir, el Set : Set inconsistente Set : Set ), podemos definir exists a. a exists a. a como:

Sigma * (/a -> a)

El primer componente es un tipo y el segundo es un valor de ese tipo. Algunos ejemplos:

foo, bar :: Sigma * (/a -> a)
foo = SigmaIntro Int  4
bar = SigmaIntro Char ''a''

exists a. a exists a. a es bastante inútil, no tenemos idea de qué tipo está adentro, por lo que las únicas operaciones que pueden funcionar con él son funciones agnósticas como id o const . Vamos a extenderlo a que exists a. F a exists a. F a o incluso exists a. Show a => F a exists a. Show a => F a . Dado F :: * -> * , el primer caso es:

Sigma * F   -- or Sigma * (/a -> F a)

El segundo es un poco más complicado. No podemos simplemente tomar una instancia de Show a type class y ponerla en algún lugar dentro. Sin embargo, si se nos da un Show a dictionary (del tipo ShowDictionary a ), podemos empacarlo con el valor real:

Sigma * (/a -> (ShowDictionary a, F a))
-- inside is a pair of "F a" and "Show a" dictionary

Esto es un poco incómodo para trabajar y supone que tenemos un diccionario de Show , pero funciona. Empacar el diccionario es en realidad lo que hace GHC al compilar tipos existenciales, por lo que podríamos definir un atajo para que sea más conveniente, pero esa es otra historia. Como veremos muy pronto, la codificación en realidad no sufre este problema.

Digresión: gracias a los tipos de restricción, es posible reificar la clase de tipo en el tipo de datos concretos. Primero, necesitamos algunos pragmas de lenguaje y una importación:

{-# LANGUAGE ConstraintKinds, GADTs, KindSignatures  #-}
import GHC.Exts -- for Constraint

Los GADT ya nos dan la opción de empacar una clase de tipo junto con el constructor, por ejemplo:

data BST a where
    Nil  :: BST a
    Node :: Ord a => a -> BST a -> BST a -> BST a

Sin embargo, podemos dar un paso más:

data Dict :: Constraint -> * where
    D :: ctx => Dict ctx

Funciona muy parecido al ejemplo BST anterior: la coincidencia de patrones en D :: Dict ctx nos da acceso a todo el contexto ctx :

show'' :: Dict (Show a) -> a -> String
show'' D = show

(.+) :: Dict (Num a) -> a -> a -> a
(.+) D = (+)

También obtenemos una generalización bastante natural para los tipos existenciales que cuantifican más variables de tipo, como exists a b. F ab exists a b. F ab .

Sigma * (/a -> Sigma * (/b -> F a b))
-- or we could use Sigma just once
Sigma (*, *) (/(a, b) -> F a b)
-- though this looks a bit strange

La codificación

Ahora, la pregunta es: ¿podemos codificar tipos with con solo Π tipos? Si es así, entonces la codificación de tipo existencial es solo un caso especial. En toda la gloria, te presento la codificación real:

newtype SigmaEncoded (a :: *) (b :: a -> *)
    = SigmaEncoded (forall r. ((x :: a) -> b x -> r) -> r)

Hay algunos paralelos interesantes. Como los pares dependientes representan la cuantificación existencial y de la lógica clásica, sabemos que:

(∃x)R(x) ⇔ ¬(∀x)¬R(x) ⇔ (∀x)(R(x) → ⊥) → ⊥

forall r. r forall r. r es casi ⊥ , así que con un poco de reescritura obtenemos:

(∀x)(R(x) → r) → r

Y finalmente, representando la cuantificación universal como una función dependiente:

forall r. ((x :: a) -> R x -> r) -> r

Además, echemos un vistazo al tipo de pares codificados por Church. Obtenemos un tipo de aspecto muy similar:

Pair a b  ~  forall r. (a -> b -> r) -> r

Solo tenemos que expresar el hecho de que b puede depender del valor de a , lo que podemos hacer usando la función dependiente. Y de nuevo, obtenemos el mismo tipo.

Las funciones de codificación / descodificación correspondientes son:

encode :: Sigma a b -> SigmaEncoded a b
encode (SigmaIntro a b) = SigmaEncoded (/f -> f a b)

decode :: SigmaEncoded a b -> Sigma a b
decode (SigmaEncoded f) = f SigmaIntro
-- recall that SigmaIntro is a constructor

El caso especial realmente simplifica las cosas lo suficiente como para que se pueda expresar en Haskell, echemos un vistazo:

newtype ExistsEncoded (F :: * -> *)
    = ExistsEncoded (forall r. ((x :: *) -> (ShowDictionary x, F x) -> r) -> r)
    -- simplify a bit
    = ExistsEncoded (forall r. (forall x. (ShowDictionary x, F x) -> r) -> r)
    -- curry (ShowDictionary x, F x) -> r
    = ExistsEncoded (forall r. (forall x. ShowDictionary x -> F x -> r) -> r)
    -- and use the actual type class
    = ExistsEncoded (forall r. (forall x. Show x => F x -> r) -> r)

Tenga en cuenta que podemos ver f :: (x :: *) -> x -> x como f :: forall x. x -> x f :: forall x. x -> x . Es decir, una función con argumento extra * comporta como una función polimórfica.

Y algunos ejemplos:

showEx :: ExistsEncoded [] -> String
showEx (ExistsEncoded f) = f show

someList :: ExistsEncoded []
someList = ExistsEncoded $ /f -> f [1]

showEx someList == "[1]"

Tenga en cuenta que someList se construye a través de encode , pero descartamos el argumento a. Eso es porque Haskell inferirá qué x en el forall x. parte que realmente quieres decir.

De Π a Σ?

Curiosamente (aunque fuera del alcance de esta pregunta), puede codificar tipos via a través de tipos function y tipos de funciones regulares:

newtype PiEncoded (a :: *) (b :: a -> *)
    = PiEncoded (forall r. Sigma a (/x -> b x -> r) -> r)
-- /x -> is lambda introduction, b x -> r is a function type
-- a bit confusing, I know

encode :: ((x :: a) -> b x) -> PiEncoded a b
encode f = PiEncoded $ /sigma -> case sigma of
    SigmaIntro a bToR -> bToR (f a)

decode :: PiEncoded a b -> (x :: a) -> b x
decode (PiEncoded f) x = f (SigmaIntro x (/b -> b))