haskell - semánticas - Tipos asociados y elementos contenedores.

semantica html5

Question

Creo que quizás haya preguntado esto en Haskell-Cafe en algún momento, pero maldita sea si puedo encontrar la respuesta ahora ... Así que lo estoy pidiendo nuevamente aquí, así que espero que en el futuro pueda encontrar la respuesta

Haskell es fantástico en el tratamiento del polimorfismo paramétrico. Pero el problema es que no todo es paramétrico. Como ejemplo trivial, supongamos que queremos obtener el primer elemento de datos de un contenedor. Para un tipo paramétrico, eso es trivial:

class HasFirst c where first :: c x -> Maybe x instance HasFirst [] where first [] = Nothing first (x:_) = Just x

Ahora intenta y escribe una instancia para ByteString . Usted no puede Su tipo no menciona el tipo de elemento. Tampoco puede escribir una instancia para Set , porque requiere una restricción Ord , pero el jefe de clase no menciona el tipo de elemento, por lo que no puede restringirlo.

Los tipos asociados proporcionan una forma ordenada de solucionar completamente estos problemas:

class HasFirst c where type Element c :: * first :: c -> Maybe (Element c) instance HasFirst [x] where type Element [x] = x first [] = Nothing first (x:_) = Just x instance HasFirst ByteString where type Element ByteString = Word8 first b = b ! 0 instance Ord x => HasFirst (Set x) where type Element (Set x) = x first s = findMin s

Ahora tenemos un nuevo problema, sin embargo. Considere intentar "corregir" el Functor para que funcione con todos los tipos de contenedores:

class Functor f where type Element f :: * fmap :: (Functor f2) => (Element f -> Element f2) -> f -> f2

Esto no funciona en absoluto. Dice que si tenemos una función desde el tipo de elemento f hasta el tipo de elemento f2 , entonces podemos convertir una f en un f2 . Hasta ahora tan bueno. Sin embargo, aparentemente no hay forma de exigir que f y f2 sean del mismo tipo de contenedor.

Bajo la definición de Functor existente, tenemos

fmap :: (x -> y) -> [x] -> [y] fmap :: (x -> y) -> Seq x -> Seq y fmap :: (x -> y) -> IO x -> IO y

Pero no tenemos fmap :: (x -> y) -> IO x -> [y] . Eso es bastante imposible. Pero la definición de clase anterior lo permite.

¿Alguien sabe cómo explicar al sistema de tipos lo que realmente quería decir?

Editar

Lo anterior funciona al definir una forma de calcular un tipo de elemento a partir de un tipo de contenedor. ¿Qué pasa si intentas hacerlo al revés? ¿Definir una función para calcular un tipo de contenedor a partir de un tipo de elemento? ¿Eso funciona más fácil?

Answer 1

Bueno, el problema es que no está claro qué se supone que significa el Functor revisado. Por ejemplo, considere ByteString . Un ByteString solo se puede asignar al reemplazar cada elemento de Word8 con un elemento del mismo tipo . Pero Functor es para estructuras paramétricas mapeables. Realmente hay dos nociones conflictivas de mapeo aquí:

• Mapeo rígido (es decir, transformar cada elemento de una estructura sin cambiar su tipo)
• Mapeo paramétrico (es decir, transformando cada elemento de una estructura a cualquier tipo)

Entonces, en este caso, no puedes explicar al sistema de tipos lo que quisiste decir, porque no tiene mucho sentido. Puedes, sin embargo, cambiar lo que quieres decir :)

El mapeo rígido es fácil de expresar con familias de tipos:

class RigidMap f where
  type Element f :: *
  rigidMap :: (Element f -> Element f) -> f -> f

En cuanto al mapeo paramétrico, hay múltiples formas de hacerlo. La forma más sencilla sería conservar el Functor actual como está. Juntas, estas clases cubren estructuras como ByteString , [] , Seq , etc. Sin embargo, todos caen en Set y Map , debido a la restricción Ord de los valores. Afortunadamente, la extensión de tipos de restricciones que viene en GHC 7.4 nos permite solucionar este problema:

class RFunctor f where
  type Element f a :: Constraint
  type Element f a = ()  -- default empty constraint
  fmap :: (Element f a, Element f b) => (a -> b) -> f a -> f b

Aquí, estamos diciendo que cada instancia debe tener una restricción de clase de tipo asociada. Por ejemplo, la instancia de Set tendrá el Element Set a = Ord a , para indicar que los Set s solo se pueden construir si una instancia de Ord está disponible para el tipo. Cualquier cosa que pueda aparecer en la mano izquierda de => es aceptada. Podemos definir nuestras instancias anteriores exactamente como eran, pero también podemos hacer Set y Map :

instance RFunctor Set where
  type Element Set a = Ord a
  fmap = Set.map

instance RFunctor Map where
  type Element Map a = Ord a
  fmap = Map.map

Sin embargo, es bastante molesto tener que usar dos interfaces separadas para la asignación rígida y la asignación paramétrica restringida. De hecho, ¿no es esta última una generalización de la primera? Considere la diferencia entre Set , que solo puede contener instancias de Ord , y ByteString , que solo puede contener Word8 s. ¿Seguramente podemos expresarlo como otra restricción?

Aplicamos el mismo truco hecho a HasFirst (es decir, damos instancias para toda la estructura y usamos una familia de tipos para exponer el tipo de elemento), e introducimos una nueva familia de restricciones asociada:

class Mappable f where
  type Element f :: *
  type Result f a r :: Constraint
  map :: (Result f a r) => (Element f -> a) -> f -> r

La idea aquí es que el Result far expresa en gran Result far las restricciones que necesita en el tipo de valor (como Ord a ), y también restringe el tipo de contenedor resultante como sea necesario; presumiblemente, para asegurarse de que tenga el tipo de un mismo tipo de contenedor de a s. Por ejemplo, el Result [a] br probablemente requerirá que r sea [b] , y el Result ByteString br requerirá que b sea Word8 , r sea ByteString .

Las familias de tipos ya nos dan lo que necesitamos para expresar "es" aquí: una restricción de igualdad de tipos. Podemos decir (a ~ b) => ... para exigir que a y b sean del mismo tipo. Podemos, por supuesto, usar esto en las definiciones de familias de restricción. Entonces, tenemos todo lo que necesitamos; a las instancias:

instance Mappable [a] where
  type Element [a] = a
  type Result [a] b r = r ~ [b]
  -- The type in this case works out as:
  --   map :: (r ~ [b]) => (a -> b) -> [a] -> r
  -- which simplifies to:
  --   map :: (a -> b) -> [a] -> [b]
  map = Prelude.map

instance Mappable ByteString where
  type Element ByteString = Word8
  type Result ByteString a r = (a ~ Word8, r ~ ByteString)
  -- The type is:
  --   map :: (b ~ Word8, r ~ ByteString) => (Word8 -> b) -> ByteString -> r
  -- which simplifies to:
  --   map :: (Word8 -> Word8) -> ByteString -> ByteString
  map = ByteString.map

instance (Ord a) => Mappable (Set a) where
  type Element (Set a) = a
  type Result (Set a) b r = (Ord b, r ~ Set b)
  -- The type is:
  --   map :: (Ord a, Ord b, r ~ Set b) => (a -> b) -> Set a -> r
  -- (note the (Ord a) constraint from the instance head)
  -- which simplifies to:
  --   map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
  map = Set.map

¡Perfecto! Podemos definir instancias para cualquier tipo de contenedor que queramos, rígido, paramétrico o paramétrico, pero restringido, y los tipos funcionan perfectamente.

Descargo de responsabilidad: no he probado GHC 7.4 todavía, así que no sé si algo de esto realmente compila o funciona, pero creo que las ideas básicas son sólidas.

Answer 2

Desea tipos de restricción , disponibles en ghc 7.4.