30 votos

lo que no "existe" significa en Haskell tipo de sistema?

Yo estoy luchando para entender la exists palabra clave en relación con el sistema de tipos de Haskell. Hasta donde yo sé, no existe esa palabra clave en Haskell por defecto, pero:

  • Hay extensiones que agregan, en declaraciones como estas, data Accum a = exists s. MkAccum s (a -> s -> s) (s -> a)
  • He visto un artículo sobre ellos, y si recuerdo correctamente) declaró que exists de palabras clave es necesario para el tipo de sistema, ya que puede ser generalizado por forall

Pero ni siquiera puedo entender lo exists medios.

Cuando digo, forall a . a -> Int, significa que (a mi entender, el uno incorrecto, supongo) "para cada (tipo) a, no es una función de un tipo a -> Int":

myF1 :: forall a . a -> Int
myF1 _ = 123
-- okay, that function (`a -> Int`) does exist for any `a`
-- because we have just defined it

Cuando digo exists a . a -> Int, lo que puede incluso significar? "Hay al menos un tipo a para los que existe una función de un tipo a -> Int"? Por qué uno podría escribir una declaración como esa? Cuál es el propósito? La semántica? Compilador de comportamiento?

myF2 :: exists a . a -> Int
myF2 _ = 123
-- okay, there is at least one type `a` for which there is such function
-- because, in fact, we have just defined it for any type
-- and there is at least one type...
-- so these two lines are equivalent to the two lines above

Por favor nota no pretende ser un código real que se puede compilar, sólo un ejemplo de lo que me estoy imaginando, a continuación, he oído acerca de estos cuantificadores.

Traté de leer docs pero mis pobres conocimientos de inglés y pobres habilidades Matemáticas en el camino, supongo.

Que parece un gran malentendido... por Favor me ayude a hacerlo bien


P. S. yo no soy exactamente un novato total en Haskell (tal vez como un estudiante de segundo grado), pero mis Matemáticas fundamentos de estas cosas faltan, así que si usted sabe de un bien (tal vez complicado, pero bueno y comprensible sin PhD) o libro de papel o guía, por favor, háblame de ti

19voto

rampion Puntos 38697

Un uso existencial de los tipos de los que me he topado es con mi código para la mediación de un juego de Pista.

Mi mediación código de tipo de actos como un distribuidor. No importa lo que los tipos de los jugadores son - lo único que le preocupa es que todos los jugadores implementar los ganchos dado en la Player typeclass.

class Player p m where
  -- deal them in to a particular game
  dealIn :: TotalPlayers -> PlayerPosition -> [Card] -> StateT p m ()

  -- let them know what another player does
  notify :: Event -> StateT p m ()

  -- ask them to make a suggestion
  suggest :: StateT p m (Maybe Scenario)

  -- ask them to make an accusation
  accuse :: StateT p m (Maybe Scenario)

  -- ask them to reveal a card to invalidate a suggestion
  reveal :: (PlayerPosition, Scenario) -> StateT p m Card

Ahora, el distribuidor puede mantener una lista de los jugadores de tipo Player p m => [p], pero que se contraen todos los jugadores sean del mismo tipo.

Eso es demasiado restrictiva. Lo que si quiero tener diferentes tipos de jugadores, cada implementado de manera diferente, y ejecutar el uno contra el otro?

Así que aprovecho ExistentialTypes a crear un contenedor para los jugadores:

-- wrapper for storing a player within a given monad
data WpPlayer m = forall p. Player p m => WpPlayer p

Ahora puedo mantener una heterogénea lista de jugadores. La banca todavía puede interactuar fácilmente con el los jugadores que usen la interfaz especificada por el Player typeclass.

Tener en cuenta el tipo de el constructor WpPlayer.

    WpPlayer :: forall p. Player p m  => p -> WpPlayer m

Otro de los forall en la parte delantera, esto es bastante estándar haskell. Para todos los tipos de p que cumple el contrato Player p m, el constructor WpPlayer asigna un valor de tipo p a un valor de tipo WpPlayer m.

La parte interesante viene con un deconstructor:

    unWpPlayer (WpPlayer p) = p

¿Cuál es el tipo de unWpPlayer? Hace este trabajo?

    unWpPlayer :: forall p. Player p m => WpPlayer m -> p

No, realmente no. Un montón de diferentes tipos de p podría satisfacer la Player p mcontrato con un tipo particular m. Y nos dio la WpPlayer constructor de un particular tipo p, por lo que debe devolver el mismo tipo. Así que no podemos usar forall.

Todo lo que podemos decir es que no existe algún tipo p, que satisface la Player p mcontrato con el tipo m.

    unWpPlayer :: exists p. Player p m => WpPlayer m -> p

12voto

mokus Puntos 2365

Cuando digo, forall una . a -> Int, significa que (a mi entender, el uno incorrecto, supongo) "para cada (tipo), no es una función de una tipo a -> Int":

Cerca, pero no del todo. Significa "para todo tipo a, esta función puede ser considerado como tipo a -> Int". Por lo a puede ser especializado para cualquier tipo de la persona que llama de la elección.

En el "existe" caso, tenemos: "hay algunos (específicos, pero se desconoce) escriba un ejemplo de que esta función tiene el tipo a -> Int". Por lo a debe ser de un tipo específico, pero la persona que llama no sé qué.

Tenga en cuenta que esto significa que este tipo particular (exists a. a -> Int) no es muy interesante - no hay manera útil para llamar a esa función, excepto para pasar un "fondo" como valor de undefined o let x = x in x. Una forma más útil de la firma podría ser exists a. Foo a => Int -> a. Se dice que la función devuelve un tipo específico a, pero no se sabe de qué tipo. Pero usted sabe que es una instancia de Foo - por lo que usted puede hacer algo útil con ella a pesar de no saber su "verdadero".

5voto

Edward Z. Yang Puntos 13760

Significa, precisamente, "existe un tipo a de lo que me puede proporcionar los valores de los siguientes tipos en mi constructor". Tenga en cuenta que esto es diferente de decir "el valor de a es Int en mi constructor"; en este último caso, sé de qué tipo es, y podría usar mi propia función que toma Ints como argumentos para hacer algo más a los valores del tipo de datos.

Por lo tanto, desde la perspectiva pragmática, existencial tipos le permiten ocultar el tipo subyacente en una estructura de datos, obligando al programador a utilizar sólo las operaciones que se definen en ella. Representa la encapsulación.

Es por esta razón que el siguiente tipo no es muy útil:

data Useless = exists s. Useless s

Porque no hay nada que yo pueda hacer para el valor (que no es del todo cierto, yo podría seq ); yo no sé nada acerca de su tipo.

3voto

sclv Puntos 25335

UHC implementa existe la palabra clave. He aquí un ejemplo de su documentación

x2 :: exists a . (a, a -> Int)
x2 = (3 :: Int, id)

xapp :: (exists b . (b,b -> a)) -> a
xapp (v,f) = f v

x2app = xapp x2

Y otro:

mkx :: Bool -> exists a . (a, a -> Int)
mkx b = if b then x2 else ('a',ord)

y1 = mkx True -- y1 :: (C_3_225_0_0,C_3_225_0_0 -> Int)
y2 = mkx False -- y2 :: (C_3_245_0_0,C_3_245_0_0 -> Int)

mixy = let (v1,f1) = y1
            (v2,f2) = y2
       in f1 v2

"mixy provoca un error de tipo. Sin embargo, podemos usar y1 y y2 perfectamente:"

main :: IO ()
main = do putStrLn (show (xapp y1))
          putStrLn (show (xapp y2))

ezyang también escribió en su blog sobre esto: http://blog.ezyang.com/2010/10/existential-type-curry/

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X