haskell - teresa - julian assange wikileaks

''familia de tipo'' frente a ''familia de datos'', en resumen?

Question

Estoy confundido acerca de cómo elegir entre data family y type family . La página wiki en TypeFamilies entra en muchos detalles. Ocasionalmente se refiere informalmente a la data family de Haskell como una "familia tipográfica" en prosa, pero por supuesto también hay type family en Haskell.

Hay un ejemplo simple que muestra dónde se muestran dos versiones de código, que difieren solo en si se está declarando una data family o una type family :

-- BAD: f is too ambiguous, due to non-injectivity
-- type family F a

-- OK
data family F a 

f :: F a -> F a
f = undefined

g :: F Int -> F Int
g x = f x

type y los data tienen el mismo significado, pero la versión type family falla al verificar el tipo, mientras que la versión de la data family está bien, porque data family "crea nuevos tipos y por lo tanto son inyectivos" (dice la página wiki).

Lo que me lleva de todo esto es "probar data family para casos simples y, si no es lo suficientemente potente, intente type family ". Lo cual está bien, pero me gustaría entenderlo mejor. ¿Existe un diagrama de Venn o un árbol de decisión que pueda seguir para distinguir cuándo usarlo?

Answer 1

No creo que exista ningún árbol de decisión o diagrama de Venn porque las aplicaciones para las familias de tipos y datos son bastante amplias.

En general, ya ha resaltado las diferencias de diseño clave y estoy de acuerdo con su punto de partida para ver primero si puede salirse con la suya con data family .

Para mí, el punto clave es que cada instancia de una data family crea un nuevo tipo, que limita sustancialmente la potencia porque no se puede hacer lo que a menudo es lo más natural y hacer que un tipo existente sea la instancia.

Por ejemplo, el ejemplo de GMapKey en la página wiki de Haskell sobre "tipos indexados" es un ajuste razonablemente natural para las familias de datos:

class GMapKey k where
  data GMap k :: * -> *
  empty       :: GMap k v
  lookup      :: k -> GMap k v -> Maybe v
  insert      :: k -> v -> GMap k v -> GMap k v

El tipo de clave del mapa k es el argumento para la familia de datos y el tipo de mapa real es el resultado de la familia de datos ( GMap k ). Como usuario de una instancia de GMapKey , probablemente esté muy satisfecho de que el tipo de GMap k sea ​​abstracto para usted y simplemente lo manipule a través de las operaciones de mapa genéricas en la clase de tipo.

Por el contrario, el ejemplo de Collects en la misma página wiki es algo opuesto:

class Collects ce where
  type Elem ce
  empty  :: ce
  insert :: Elem ce -> ce -> ce
  member :: Elem ce -> ce -> Bool
  toList :: ce -> [Elem ce]

El tipo de argumento es la colección y el tipo de resultado es el elemento de la colección. En general, un usuario va a querer operar esos elementos directamente utilizando las operaciones normales de ese tipo. Por ejemplo, la colección podría ser IntSet y el elemento podría ser Int . Tener el Int envuelto en algún otro tipo sería bastante inconveniente.

Nota: estos dos ejemplos son con clases de tipo y, por lo tanto, no necesitan la palabra clave family porque declarar un tipo dentro de una clase type implica que debe ser una familia. Sin embargo, se aplican exactamente las mismas consideraciones que para las familias independientes, solo se trata de cómo se organiza la abstracción.

Answer 2

(Impulsar información útil de los comentarios en una respuesta).

Declaración independiente vs In-Class

Dos maneras sintácticamente diferentes de declarar un tipo familia y / o familia de datos , que son semánticamente equivalentes:

ser único:

type family Foo
data family Bar

o como parte de una clase de tipo:

class C where
   type Foo 
   data Bar 

ambos declaran una familia de tipos, pero dentro de una clase de tipos, la parte family está implícita en el contexto de class , por lo que GHC / Haskell abrevia la declaración.

"Tipo nuevo" frente a "Tipo sinónimo" / "Tipo alias"

data family F crea un nuevo tipo, similar a cómo los data F = ... crean un nuevo tipo.

type family F no crea un nuevo tipo, similar a cómo type F = Bar Baz no crea un nuevo tipo (simplemente crea un alias / sinónimo a un tipo existente).

Ejemplo de no-inyectividad de type family

Un ejemplo (ligeramente modificado) de Data.MonoTraversable.Element :

import Data.ByteString as S
import Data.ByteString.Lazy as L

-- Declare a family of type synonyms, called `Element` 
-- `Element` has kind `* -> *`; it takes one parameter, which we call `container`
type family Element container

-- ByteString is a container for Word8, so...
-- The Element of a `S.ByteString` is a `Word8`
type instance Element S.ByteString = Word8 

-- and the Element of a `L.ByteString` is also `Word8`
type instance Element L.ByteString = Word8  

En una familia de tipos, el lado derecho de las ecuaciones Word8 nombra un tipo existente; las cosas que están a la izquierda crean nuevos sinónimos: Element S.ByteString y Element L.ByteString

Tener un sinónimo significa que podemos intercambiar Element Data.ByteString con Word8 :

-- `w` is a Word8....
>let w = 0::Word8

-- ... and also an `Element L.ByteString`
>:t w :: Element L.ByteString
w :: Element L.ByteString :: Word8

-- ... and also an `Element S.ByteString`
>:t w :: Element S.ByteString
w :: Element S.ByteString :: Word8

-- but not an `Int`
>:t w :: Int
Couldn''t match expected type `Int'' with actual type `Word8''

Estos sinónimos de tipo son "no-inyectables" ("unidireccionales"), y por lo tanto no invertibles.

-- As before, `Word8` matches `Element L.ByteString` ...
>(0::Word8)::(Element L.ByteString)

-- .. but  GHC can''t infer which `a` is the `Element` of (`L.ByteString` or `S.ByteString` ?):

>(w)::(Element a)
Couldn''t match expected type `Element a''
            with actual type `Element a0''
NB: `Element'' is a type function, and may not be injective
The type variable `a0'' is ambiguous

Peor aún, ¡GHC ni siquiera puede resolver casos no ambiguos !:

type instance Element Int = Bool
> True::(Element a)
> NB: `Element'' is a type function, and may not be injective

Tenga en cuenta el uso de "puede no ser"! Creo que GHC es conservador y se niega a verificar si el Element es realmente inyectivo. (Tal vez porque un programador podría agregar otra type instance más tarde, después de importar un módulo precompilado, agregando ambigüedad.

Ejemplo de inyectividad de data family de data family

En contraste: en una familia de datos, cada lado derecho contiene un constructor único, por lo que las definiciones son ecuaciones inyectivas ("reversibles").

-- Declare a list-like data family
data family XList a

-- Declare a list-like instance for Char
data instance XList Char = XCons Char (XList Char) | XNil

-- Declare a number-like instance for ()
data instance XList () = XListUnit Int

-- ERROR: "Multiple declarations of `XListUnit''"
data instance XList () = XListUnit Bool
-- (Note: GHCI accepts this; the new declaration just replaces the previous one.)

Con data family , al ver el nombre del constructor a la derecha ( XCons o XListUnit ) es suficiente para que el tipo-inferencer sepa que debemos trabajar con XList () no con un XList Char . Como los nombres de los constructores son únicos, estas definiciones son inyectivas / reversibles.

Si el type "solo" declara un sinónimo, ¿por qué es semánticamente útil?

Por lo general, los sinónimos de type son solo abreviaturas, pero los sinónimos de familia type tienen mayor poder: pueden hacer que un tipo simple (kind * ) se convierta en sinónimo de "tipo con kind * -> * aplicado a un argumento":

type instance F A = B

hace que B coincida con F a . Esto se usa, por ejemplo, en Data.MonoTraversable para hacer un tipo simple de las funciones de concordancia de Word8 del tipo Element a -> a (El Element se define arriba).

Por ejemplo, (un poco tonto), supongamos que tenemos una versión de const que solo funciona con tipos "relacionados":

> class Const a where constE :: (Element a) -> a -> (Element a)
> instance Const S.ByteString where constE = const

> constE (0::Word8) undefined
ERROR: Couldn''t match expected type `Word8'' with actual type `Element a0''

-- By providing a match `a = S.ByteString`, `Word8` matches `(Element S.ByteString)`
> constE (0::Word8) (undefined::S.ByteString)  
0

-- impossible, since `Char` cannot match `Element a` under our current definitions.
> constF ''x'' undefined