pattern opciones imprimir hacer funciones ejemplos como basico haskell types metaprogramming type-systems hindley-milner

opciones - let haskell



Anotaciones de tipo programático en Haskell (3)

Desea una función que elija un tipo diferente de valores para devolver en función de los datos de tiempo de ejecución. Bien, excelente. Pero el propósito de un tipo es decirte qué operaciones se pueden realizar en un valor. Cuando no sabe qué tipo será devuelto por una función, ¿qué hace con los valores que devuelve? ¿Qué operaciones puedes realizar en ellas? Hay dos opciones:

  • Desea leer el tipo y realizar algún comportamiento según el tipo que sea. En este caso, solo puede atender una lista finita de tipos conocidos de antemano, esencialmente probando "¿es este tipo? Entonces hacemos esta operación ...". Esto es fácilmente posible en el marco Dynamic actual: simplemente devuelva los objetos Dynamic , usando dynTypeRep para filtrarlos, y deje la aplicación fromDynamic a quien quiera consumir su resultado. Además, podría ser posible sin Dynamic , si no le importa establecer la lista finita de tipos en su código de productor, en lugar de su código de consumidor: simplemente use un ADT con un constructor para cada tipo, data Thing = Thing1 Int | Thing2 String | Thing3 (Thing,Thing) data Thing = Thing1 Int | Thing2 String | Thing3 (Thing,Thing) data Thing = Thing1 Int | Thing2 String | Thing3 (Thing,Thing) . Esta última opción es de lejos la mejor si es posible.
  • Desea realizar alguna operación que funcione en una familia de tipos, potencialmente algunos de los cuales aún no conoce, por ejemplo, mediante el uso de operaciones de clase de tipo. Esto es más complicado, y también es complicado conceptualmente, porque su programa no puede cambiar el comportamiento en función de si existe o no una instancia de clase de tipo; es una propiedad importante del sistema de clase de tipo que la introducción de una nueva instancia puede hacer una El tipo de programa lo comprueba o lo detiene de la verificación de tipos, pero no puede cambiar el comportamiento de un programa. Por lo tanto, no puede lanzar un error si su lista de entrada contiene tipos inadecuados, por lo que no estoy seguro de que haya algo que pueda hacer que no implique volver a la primera solución en algún momento.

Cuando se metaprograma, puede ser útil (o necesario) transmitir la información del sistema de tipos de Haskell sobre los tipos conocidos en su programa, pero no deducibles en Hindley-Milner. ¿Existe una biblioteca (o extensión de lenguaje, etc.) que proporcione facilidades para hacerlo, es decir, anotaciones de tipo programático, en Haskell?

Considere una situación en la que esté trabajando con una lista heterogénea (implementada utilizando la biblioteca Data.Dynamic o la cuantificación existencial, por ejemplo) y desee filtrar la lista a una lista Haskell homogéneamente tipificada en un pantano. Puedes escribir una función como

import Data.Dynamic import Data.Typeable dynListToList :: (Typeable a) => [Dynamic] -> [a] dynListToList = (map fromJust) . (filter isJust) . (map fromDynamic)

y llámalo con una anotación de tipo manual. Por ejemplo,

foo :: [Int] foo = dynListToList [ toDyn (1 :: Int) , toDyn (2 :: Int) , toDyn ("foo" :: String) ]

Aquí foo es la lista [1, 2] :: [Int] ; eso funciona bien y estás de nuevo en terreno firme donde el sistema de tipos de Haskell puede hacer su trabajo.

Ahora imagina que quieres hacer más o menos lo mismo pero (a) en el momento de escribir el código, no sabes cuál es el tipo de lista producida por una llamada a dynListToList , pero (b) tu programa sí contiene la información necesaria para resolver esto, solo (c) no está en una forma accesible para el sistema de tipo.

Por ejemplo, supongamos que ha seleccionado aleatoriamente un elemento de su lista heterogénea y desea filtrar la lista por ese tipo. Usando las facilidades de verificación de tipo provistas por Data.Typeable , su programa tiene toda la información que necesita para hacer esto, pero por lo que puedo decir, esta es la esencia de la pregunta, no hay forma de pasarlo al tipo sistema. Aquí hay un pseudo Haskell que muestra lo que quiero decir:

import Data.Dynamic import Data.Typeable randList :: (Typeable a) => [Dynamic] -> IO [a] randList dl = do tr <- randItem $ map dynTypeRep dl return (dynListToList dl :: [<tr>]) -- This thing should have the type -- represented by `tr`

(Supongamos que randItem selecciona un elemento aleatorio de una lista).

Sin una anotación de tipo sobre el argumento de return , el compilador le dirá que tiene un "tipo ambiguo" y le pedirá que proporcione uno. Pero no puede proporcionar una anotación de tipo manual porque el tipo no se conoce en el momento de la escritura (y puede variar); sin embargo, el tipo se conoce en tiempo de ejecución, aunque en una forma que el sistema de tipo no puede usar (aquí, el tipo necesario se representa con el valor tr , un TypeRep -ver Data.Typeable para más detalles).

El pseudo-código :: [<tr>] es la magia que quiero que suceda. ¿Hay alguna manera de proporcionar el tipo de sistema con información de tipo programáticamente? es decir, ¿con información de tipo contenida en un valor en su programa?

Básicamente estoy buscando una función con (pseudo-) tipo ??? -> TypeRep -> a ??? -> TypeRep -> a que toma un valor de un tipo desconocido para el sistema de tipos de Haskell y TypeRep y dice: "Créeme, compilador, sé lo que estoy haciendo. Esto tiene el valor representado por este TypeRep ". (Tenga en cuenta que esto no es lo que unsafeCoerce hace).

¿O hay algo completamente diferente que me lleva al mismo lugar? Por ejemplo, puedo imaginar una extensión de idioma que permita la asignación de variables de tipo, como una versión trucada de la extensión que permite variables de tipo de ámbito.

(Si esto es imposible o poco práctico, por ejemplo, se requiere empaquetar un intérprete completo similar a GHCi en el archivo ejecutable, intente explicar por qué).

Lo que estás observando es que el tipo TypeRep realidad no lleva ninguna información de nivel de tipo junto con él; solo información a nivel de término. Es una pena, pero podemos hacerlo mejor cuando conocemos a todos los constructores de tipos que nos importan. Por ejemplo, supongamos que solo nos importan las Int , las listas y los tipos de funciones.

{-# LANGUAGE GADTs, TypeOperators #-} import Control.Monad data a :=: b where Refl :: a :=: a data Dynamic where Dynamic :: TypeRep a -> a -> Dynamic data TypeRep a where Int :: TypeRep Int List :: TypeRep a -> TypeRep [a] Arrow :: TypeRep a -> TypeRep b -> TypeRep (a -> b) class Typeable a where typeOf :: TypeRep a instance Typeable Int where typeOf = Int instance Typeable a => Typeable [a] where typeOf = List typeOf instance (Typeable a, Typeable b) => Typeable (a -> b) where typeOf = Arrow typeOf typeOf congArrow :: from :=: from'' -> to :=: to'' -> (from -> to) :=: (from'' -> to'') congArrow Refl Refl = Refl congList :: a :=: b -> [a] :=: [b] congList Refl = Refl eq :: TypeRep a -> TypeRep b -> Maybe (a :=: b) eq Int Int = Just Refl eq (Arrow from to) (Arrow from'' to'') = liftM2 congArrow (eq from from'') (eq to to'') eq (List t) (List t'') = liftM congList (eq t t'') eq _ _ = Nothing eqTypeable :: (Typeable a, Typeable b) => Maybe (a :=: b) eqTypeable = eq typeOf typeOf toDynamic :: Typeable a => a -> Dynamic toDynamic a = Dynamic typeOf a -- look ma, no unsafeCoerce! fromDynamic_ :: TypeRep a -> Dynamic -> Maybe a fromDynamic_ rep (Dynamic rep'' a) = case eq rep rep'' of Just Refl -> Just a Nothing -> Nothing fromDynamic :: Typeable a => Dynamic -> Maybe a fromDynamic = fromDynamic_ typeOf

Todo lo anterior es bastante estándar. Para obtener más información sobre la estrategia de diseño, querrá leer sobre los GADT y los tipos de singleton. Ahora, la función que desea escribir sigue; el tipo va a parecer un poco tonto, pero tengan paciencia conmigo.

-- extract only the elements of the list whose type match the head firstOnly :: [Dynamic] -> Dynamic firstOnly [] = Dynamic (List Int) [] firstOnly (Dynamic rep v:xs) = Dynamic (List rep) (v:go xs) where go [] = [] go (Dynamic rep'' v:xs) = case eq rep rep'' of Just Refl -> v : go xs Nothing -> go xs

Aquí seleccionamos un elemento aleatorio (rodé un dado, y salió 1) y extraje solo los elementos que tienen un tipo coincidente de la lista de valores dinámicos. Ahora, podríamos haber hecho lo mismo con aburridos viejos Dynamic de las bibliotecas estándar; sin embargo, lo que no podríamos haber hecho es usar TypeRep de una manera significativa. Ahora demuestro que podemos hacerlo: emparejaremos el patrón en TypeRep , y luego usaremos el valor adjunto en el tipo específico que TypeRep nos dice que es.

use :: Dynamic -> [Int] use (Dynamic (List (Arrow Int Int)) fs) = zipWith ($) fs [1..] use (Dynamic (List Int) vs) = vs use (Dynamic Int v) = [v] use (Dynamic (Arrow (List Int) (List (List Int))) f) = concat (f [0..5]) use _ = []

Tenga en cuenta que en el lado derecho de estas ecuaciones, estamos usando el valor envuelto en diferentes tipos de concreto ; la coincidencia de patrones en TypeRep realmente está introduciendo información de nivel de tipo.

No, no puedes hacer esto. En resumidas cuentas, intentas escribir una función de tipo dependiente y Haskell no es un lenguaje dependiente; no puede elevar su valor TypeRep a un tipo verdadero, por lo que no hay forma de escribir el tipo de función que desea. Para explicar esto con un poco más de detalle, primero voy a mostrar por qué la forma en que ha redactado el tipo de randList realmente no tiene sentido. Entonces, voy a explicar por qué no puedes hacer lo que quieres. Finalmente, mencionaré brevemente un par de pensamientos sobre qué hacer realmente.

Existenciales

Su firma de tipo para randList no puede significar lo que quiere que signifique. Recordando que todas las variables de tipo en Haskell se cuantifican universalmente, se lee

randList :: forall a. Typeable a => [Dynamic] -> IO [a]

Por lo tanto, tengo derecho a llamarlo como, por ejemplo, randList dyns :: IO [Int] cualquier lugar que desee; Debo ser capaz de proporcionar un valor de retorno para todos los a , no simplemente para algunos a . Pensando en esto como un juego, es uno donde la persona que llama puede elegir a , no la función en sí misma. Lo que quieres decir (esto no es una sintaxis Haskell válida, aunque puedes traducirlo a Haskell válido usando un tipo de datos existenciales 1 ) es algo parecido a

randList :: [Dynamic] -> (exists a. Typeable a => IO [a])

Esto promete que los elementos de la lista son de algún tipo a , que es una instancia de Typeable , pero no necesariamente de ese tipo. Pero incluso con esto, tendrás dos problemas. En primer lugar, incluso si pudiera construir una lista de ese tipo, ¿qué podría hacer con ella? Y segundo, resulta que ni siquiera puedes construirlo en primer lugar.

Como todo lo que sabes sobre los elementos de la lista existencial es que son ejemplos de Typeable , ¿qué puedes hacer con ellos? Al observar la documentación , vemos que solo hay dos funciones 2 que toman instancias de Typeable :

Por lo tanto, todo lo que sabes sobre el tipo de elementos en la lista es que puedes llamar a typeOf y cast sobre ellos. Como nunca podremos hacer nada útil con ellos, nuestro ser existencial también podría ser (de nuevo, no es válido Haskell)

randList :: [Dynamic] -> IO [(TypeRep, forall b. Typeable b => Maybe b)]

Esto es lo que obtenemos si aplicamos typeOf y lo typeOf a cada elemento de nuestra lista, almacenamos los resultados y desechamos el ahora inútil valor original de tipo existencial. Claramente, la parte TypeRep de esta lista no es útil. Y la segunda mitad de la lista tampoco. Desde que volvimos a un tipo de cuantificación universal, la persona que llama de randList vuelve a tener derecho a solicitar que obtenga un Maybe Int , un Maybe Bool o un Maybe b para cualquier b de su elección. (De hecho, tienen un poco más de poder que antes, ya que pueden crear instancias de diferentes elementos de la lista en diferentes tipos). Pero no pueden descubrir de qué tipo están convirtiendo a menos que ya lo sepan, todavía perdió la información tipo que estabas tratando de mantener.

E incluso dejando de lado el hecho de que no son útiles, simplemente no se puede construir el tipo existencial deseado aquí. El error surge cuando intentas devolver la lista existencialmente escrita ( return $ dynListToList dl ). ¿A qué tipo específico llamas a dynListToList ? Recuerde que dynListToList :: forall a. Typeable a => [Dynamic] -> [a] dynListToList :: forall a. Typeable a => [Dynamic] -> [a] ; por lo tanto, randList es responsable de elegir qué dynListToList va a utilizar. Pero no sabe cuál elegir; nuevamente, esa es la fuente de la pregunta! Entonces, el tipo que intenta devolver no está especificado y, por lo tanto, es ambiguo. 3

Tipos dependientes

OK, entonces, ¿qué haría útil este existencial (y posible)? Bueno, en realidad tenemos un poco más de información: no solo sabemos que hay algunos a , sino que tenemos TypeRep . Entonces quizás podamos empaquetar eso:

randList :: [Dynamic] -> (exists a. Typeable a => IO (TypeRep,[a]))

Aunque esto no es lo suficientemente bueno; el TypeRep y el [a] no están vinculados en absoluto. Y eso es exactamente lo que intentas expresar: una forma de vincular TypeRep y a .

Básicamente, tu objetivo es escribir algo como

toType :: TypeRep -> *

Aquí, * es el tipo de todos los tipos; si no ha visto tipos antes, ellos deben especificar qué tipos son para los valores. * clasifica tipos, * -> * clasifica constructores de tipo de argumento único, etc. (Por ejemplo, Int :: * , Maybe :: * -> * , Either :: * -> * -> * , y Maybe Int :: * )

Con esto, podrías escribir (una vez más, este código no es válido Haskell, de hecho, realmente solo tiene un parecido pasajero con Haskell, ya que no hay forma de que puedas escribirlo o algo así dentro del sistema de tipos de Haskell):

randList :: [Dynamic] -> (exists (tr :: TypeRep). Typeable (toType tr) => IO (tr, [toType tr])) randList dl = do tr <- randItem $ map dynTypeRep dl return (tr, dynListToList dl :: [toType tr]) -- In fact, in an ideal world, the `:: [toType tr]` signature would be -- inferable.

Ahora, prometes lo correcto: no es que exista algún tipo que clasifique los elementos de la lista, sino que exista algún TypeRep tal que su tipo correspondiente clasifique los elementos de la lista. Si solo pudieras hacer esto, estarías listo. Pero escribir en toType :: TypeRep -> * es completamente imposible en Haskell: hacer esto requiere un lenguaje de tipo dependiente, ya que toType tr es un tipo que depende de un valor.

¿Qué significa esto? En Haskell, es perfectamente aceptable que los valores dependan de otros valores; esto es lo que es una función El valor de la head "abc" , por ejemplo, depende del valor "abc" . Del mismo modo, tenemos constructores de tipos, por lo que es aceptable que los tipos dependan de otros tipos; considere Maybe Int , y cómo depende de Int . ¡Incluso podemos tener valores que dependen de los tipos! Considera id :: a -> a . Esta es realmente una familia de funciones: id_Int :: Int -> Int , id_Bool :: Bool -> Bool , etc. La que tenemos depende del tipo de a . (Entonces realmente, id = /(a :: *) (x :: a) -> x ; aunque no podemos escribir esto en Haskell, hay idiomas donde podemos).

Crucialmente, sin embargo, nunca podemos tener un tipo que dependa de un valor. Es posible que deseemos algo así: imagina Vec 7 Int , el tipo de longitud-7 listas de enteros. Aquí, Vec :: Nat -> * -> * : un tipo cuyo primer argumento debe ser un valor de tipo Nat . Pero no podemos escribir este tipo de cosas en Haskell. 4 Los idiomas que admiten esto se denominan de tipo dependiente (y nos permitirán escribir el id como lo hicimos anteriormente); ejemplos incluyen Coq y Agda . (Tales idiomas a menudo funcionan como asistentes de pruebas, y generalmente se usan para trabajos de investigación en lugar de escribir códigos reales. Los tipos dependientes son difíciles, y hacerlos útiles para la programación diaria es un área activa de investigación).

Por lo tanto, en Haskell, primero podemos verificar todo sobre nuestros tipos, desechar toda esa información y luego compilar algo que se refiera solo a los valores. De hecho, esto es exactamente lo que hace GHC; ya que nunca podemos verificar tipos en tiempo de ejecución en Haskell, GHC borra todos los tipos en tiempo de compilación sin cambiar el comportamiento del tiempo de ejecución del programa. Esta es la razón unsafeCoerce cual unsafeCoerce es fácil de implementar (operacionalmente) y completamente inseguro: en tiempo de ejecución, no funciona, pero depende del sistema de tipos. En consecuencia, algo como toType es completamente imposible de implementar en el sistema de tipo Haskell.

De hecho, como unsafeCoerce notado, ni siquiera puedes escribir el tipo deseado y usar unsafeCoerce . Para algunos problemas, puedes salirte con la tuya; podemos escribir el tipo de la función, pero solo implementarla haciendo trampa. Así es exactamente desde fromDynamic funciona. Pero como vimos anteriormente, ni siquiera hay un buen tipo para dar a este problema dentro de Haskell. La función de toType imaginario toType permite darle un tipo al programa, ¡pero ni siquiera puede escribir en el tipo de Tipo!

¿Ahora que?

Entonces, no puedes hacer esto. ¿Qué deberías hacer? Supongo que su arquitectura general no es ideal para Haskell, aunque no la he visto; Typeable y Dynamic no aparecen realmente en los programas de Haskell. (Tal vez esté hablando "Haskell con acento de Python", como dicen). Si solo tiene un conjunto finito de tipos de datos para tratar, en su lugar, puede agrupar los elementos en un tipo de datos algebraico antiguo simple:

data MyType = MTInt Int | MTBool Bool | MTString String

Luego puede escribir isMTInt , y solo usar filter isMTInt , o filter (isSameMTAs randomMT) .

Aunque no sé de qué se trata, es probable que exista una forma en la que no se pueda unsafeCoerce . unsafeCoerce su camino a través de este problema. Pero francamente, esa no es una buena idea a menos que realmente, realmente, realmente, realmente, realmente sepas lo que estás haciendo. E incluso entonces, probablemente no lo sea. Si necesita unsafeCoerce , sabrá que no será solo una unsafeCoerce conveniencia.

Estoy realmente de acuerdo con el comentario de Daniel Wagner : probablemente querrás replantear tu enfoque desde cero. De nuevo, sin embargo, dado que no he visto tu arquitectura, no puedo decir lo que eso significará. Tal vez haya otra pregunta de Desbordamiento de pila allí, si puede extraer una dificultad concreta.

1 que se parece a lo siguiente:

{-# LANGUAGE ExistentialQuantification #-} data TypeableList = forall a. Typeable a => TypeableList [a] randList :: [Dynamic] -> IO TypeableList

Sin embargo, dado que nada de este código compila de todos modos, creo que escribirlo con exists es más claro.

2 Técnicamente, hay algunas otras funciones que parecen relevantes, como toDyn :: Typeable a => a -> Dynamic y fromDyn :: Typeable a => Dynamic -> a -> a . Sin embargo, Dynamic es más o menos un envoltorio existencial alrededor de Typeable s, confiando en typeOf y TypeRep s para saber cuándo unsafeCoerce (GHC usa algunos tipos específicos de implementación y unsafeCoerce , pero puedes hacerlo de esta manera, con la posible excepción de dynApply / dynApp ), entonces toDyn no hace nada nuevo. Y desde fromDyn realmente no espera su argumento de tipo a ; es solo una envoltura alrededor del cast . Estas funciones, y las otras similares, no proporcionan ningún poder adicional que no esté disponible con solo typeOf y cast . (Por ejemplo, volver a una Dynamic no es muy útil para su problema!)

3 Para ver el error en acción, puede intentar compilar el siguiente programa Haskell completo:

{-# LANGUAGE ExistentialQuantification #-} import Data.Dynamic import Data.Typeable import Data.Maybe randItem :: [a] -> IO a randItem = return . head -- Good enough for a short and non-compiling example dynListToList :: Typeable a => [Dynamic] -> [a] dynListToList = mapMaybe fromDynamic data TypeableList = forall a. Typeable a => TypeableList [a] randList :: [Dynamic] -> IO TypeableList randList dl = do tr <- randItem $ map dynTypeRep dl return . TypeableList $ dynListToList dl -- Error! Ambiguous type variable.

Efectivamente, si intenta compilar esto, obtendrá el error:

SO12273982.hs:17:27: Ambiguous type variable `a0'' in the constraint: (Typeable a0) arising from a use of `dynListToList'' Probable fix: add a type signature that fixes these type variable(s) In the second argument of `($)'', namely `dynListToList dl'' In a stmt of a ''do'' block: return . TypeableList $ dynListToList dl In the expression: do { tr <- randItem $ map dynTypeRep dl; return . TypeableList $ dynListToList dl }

Pero como es todo el tema de la pregunta, no puede "agregar una firma de tipo que corrige estas variables de tipo" porque no sabe qué tipo desea.

4 Mayormente. GHC 7.4 tiene soporte para levantar tipos a clases y para polimorfismo bueno; ver la sección 7.8, "Polimorfismo bueno y promoción", en el manual de usuario de GHC 7.4 . Esto no hace que Haskell escriba de manera dependiente, algo así como TypeRep -> * ejemplo todavía está fuera 5 - pero usted podrá escribir Vec usando tipos muy expresivos que parecen valores.

5 Técnicamente, ahora puede escribir algo que parece que tiene el tipo deseado: type family ToType :: TypeRep -> * . Sin embargo, esto toma un tipo del TypeRep tipo TypeRep , y no un valor del tipo TypeRep ; y además, aún no podrías implementarlo. (Al menos no lo creo, y no puedo ver cómo lo harías, pero no soy un experto en esto). Pero en este punto, estamos bastante lejos.