En Haskell, ¿por qué no hay un TypeClass para cosas que pueden actuar como listas?

Question

estoy leyendo Learn You a Haskell y me pregunto por qué tantas cosas están actuando como una lista, y nada en el preámbulo es el uso de la instalación nativa de las clases de tipos instalar esto:

"La versión de cadena de bytes de: se llama contras Toma un byte y una longitud de bytes y pone el byte al principio. Sin embargo, es flojo, por lo que creará un nuevo fragmento incluso si el primer fragmento en la cadena de bytes no está lleno. Por eso es mejor usarlo. la versión estricta de contras, contras 'si vas a insertar muchos bytes al comienzo de una cadena de bytes'.

Por qué no hay una clase de tipos susceptible de listarse o algo que ofrece la función de unificar :Data.ByteString, Data.List, Data.ByteString.Lazy, etc? ¿Hay alguna razón para esto o es solo un elemento heredado de Haskell? Usando : como un ejemplo es una especie de un eufemismo, también de Lyah:

De lo contrario, los módulos de cadena de bytes tienen una carga de funciones que son análogos a los Data.List, incluyendo, pero no limitado a, cabeza, cola, init, null, longitud, mapa, revertir, foldl, foldr, concat, takeWhile, filtro, etc.

Answer 1

que ofrece la: función de unificar Data.ByteString, Data.List, Data.ByteString .Lazy, etc.?

Ha habido intentos para llegar a una buena a) interfaz de secuencia, y b) la interfaz de contenedores, sin embargo, los tipos de datos unificadores de diferentes tipos, con diferentes restricciones de tipo, se ha hecho generalmente los resultados lo suficientemente no estándar que es difícil imaginar ponerlos en la biblioteca base. De forma similar para matrices, aunque el paquete Vector ahora tiene una interfaz bastante general (basada en tipos de datos asociados).

Hay un par de proyectos para unificar estos diversos tipos de datos semi relacionados con una sola interfaz, por lo que espero que veamos un resultado pronto. Del mismo modo para los tipos de contenedores. El resultado no será trivial sin embargo.

Answer 2

El paquete ListLike parece proporcionar lo que estás buscando. Nunca entendí por qué no es más popular.

ListLike aparte, una razón por la que esto no está implementado en el Preludio es porque no es posible hacerlo bien sin invocar algunas extensiones de lenguaje (clases de tipo multi-param y fundeps o tipos asociados). Hay tres tipos de recipientes a considerar:

1. Los envases que no se preocupan por sus elementos en todo (por ejemplo, [])
2. contenedores que sólo se implementan para elementos específicos (por ejemplo, cadenas de bytes)
3. Contenedores que son elementos polimórficos sobre pero requieren un contexto (por ejemplo, Data.Vector.Storable, que contendrá cualquier tipo con una instancia almacenable).

Aquí es una clase muy básica de estilo ListLike sin necesidad de utilizar ninguna extensión:

class Listable container where 
    head :: container a -> a 

instance Listable [] where 
    head (x:xs) = x 

instance Listable ByteString where --compiler error, wrong kind 

instance Listable SV.Vector where 
    head v = SV.head --compiler error, can't deduce context (Storable a) 

Aquí tiene container tipo *->*. Esto no funcionará para las cadenas de bytes porque no permiten un tipo arbitrario; tienen el tipo *. Tampoco funcionará para un vector Data.Vector.Storable, porque la clase no incluye el contexto (la restricción Storable).

Puede solucionar este problema, ya sea cambiando su definición de clase a

class ListableMPTC container elem | container -> elem where 

o

class ListableAT container where 
    type Elem container :: * 

Ahora tiene container tipo *; es un constructor de tipos totalmente aplicado. Es decir, sus instancias se ven como

instance ListableMPTC [a] a where 

pero ya no es Haskell98.

Es por eso que incluso una simple interfaz de tipo Listable no es trivial; se vuelve un poco más difícil cuando se tiene en cuenta una semántica de colección diferente (por ejemplo, colas). El otro gran desafío son los datos mutables frente a los inmutables. Hasta el momento, cada intento que he visto (excepto uno) se basa en ese problema al crear una interfaz mutable e inmutable. La única interfaz que conozco que unificó los dos fue alucinante, invocó un montón de extensiones y tuvo un rendimiento bastante pobre.

Adición: cadenas de bytes

totalmente conjetura de mi parte, pero creo que estamos atascados con cadenas de bytes como un producto de la evolución. Es decir, fueron la primera solución para las operaciones de E/S de bajo rendimiento, y tenía sentido usar Ptr Word8 para interactuar con las llamadas al sistema IO. Las operaciones en punteros requieren Storable, y lo más probable es que las extensiones necesarias (como se describió anteriormente) para hacer que el polimorfismo no esté disponible. Ahora es difícil superar su impulso. Un contenedor similar con polimorfismo es ciertamente posible, el paquete storablevector implementa esto, pero no es ni de lejos tan popular.

¿Pueden las cadenas de bytes ser polimórficas sin ninguna restricción en los elementos? Creo que el Haskell más cercano tiene este es el tipo de matriz. Esto no es tan bueno como una cadena de bytes para IO de bajo nivel porque los datos deben desempaquetarse desde el puntero al formato interno de la matriz. Además, los datos están encuadrados, lo que agrega una sobrecarga de espacio significativa. Si desea un almacenamiento sin caja (menos espacio) y una interfaz eficiente con C, los indicadores son el camino a seguir. Una vez que tiene un Ptr, necesita Storable, y luego necesita incluir el tipo de elemento en la clase de tipo, por lo que le quedan extensiones que requieren.

Dicho esto, creo que con las extensiones adecuadas disponibles esto es esencialmente un problema resuelto para cualquier implementación de contenedor único (módulo mutable/inmutable API). La parte más difícil ahora es crear un conjunto sensato de clases que se puedan usar para muchos tipos diferentes de estructuras (listas, matrices, colas, etc.) y que sea lo suficientemente flexible como para ser útil. Personalmente, espero que esto sea relativamente sencillo, pero podría estar equivocado.

Answer 3

ByteString no es un tipo genérico.

En otros idiomas, hay algo así como Sequence para todas las estructuras de datos similares a listas. Creo que esto funciona, con extensiones correctas:

class Seq a b | a -> b where 
    head :: a -> b 
    isTail :: a -> Bool 

# ([a]) is a sequence of a's 
instance Seq [a] a where 
    head (x:xs) = x 
    isTail = (== []) 

# ByteString is a sequence of chars 
instance Seq ByteString Char 

O probar esto?

type BS a = ByteString 
instance List BS 

Answer 4

No hay mucho valor para tener una clase de tipo para la lista de datos en Haskell. ¿Por qué? Debido a la pereza. Puede simplemente escribir una función que convierta sus datos a una lista, y luego usar esa lista. La lista solo se construirá a medida que se demanden sus sublistas y elementos, y su memoria será elegible para la recopilación tan pronto como no queden referencias a los prefijos.

Existe un valor para una clase de tipo que proporciona una función genérica toList; sin embargo, eso ya existe en Data.Foldable.

Básicamente, la solución es implementar Data.Foldable y usar su función toList.

Answer 5

El principal problema de esta clase es que, incluso si existiera, solo ofrecería una similitud superficial.

Las asintóticas del mismo algoritmo construido con diferentes estructuras variarían tremendamente.

En el caso de las cadenas de bytes estrictas compilándolas con cons es terrible, porque terminas copiando toda la cadena cada vez que agregas otro Char. Esta operación O (1) en una lista lo convierte en una operación O (n) en una Bytestring.

Esto lleva a O (n^2) comportamiento cuando se implementa el primer algoritmo que podría venir a la mente, mapa, mientras que la creación de una lista o Data.Sequence.Seq con contras es el tiempo lineal y puede ser implementado en O (n) para cadenas de bytes o vectores, así como con un poco de reflexión.

Resulta que la utilidad de tal clase a la luz de esto es más superficial que real.

No estoy diciendo que un buen diseño no se puede encontrar, pero tal diseño sería difícil de utilizar y optimizar para y probablemente una versión utilizable del diseño no terminaría siendo Haskell 98.

He obtenido porciones de este espacio de diseño en mi paquete de claves, que proporciona muchas funciones para indexar en contenedores, etc., pero he evitado deliberadamente proporcionar una API tipo lista como a) porque se ha hecho antes de poco éxito yb) debido a las preocupaciones asintóticas anteriores.

tl; dr Por lo general, desea implementar algoritmos de manera muy diferente cuando cambian las características asintóticas de las operaciones subyacentes.

Answer 6

Existen las dos clases de tipos llamadas Foldable y Traversable que intentan abstraer algunos comportamientos common1 de listas y otras estructuras de datos secuenciales. Sin embargo, no todas las estructuras de datos tienen instancias de estas, y no sé si son lo suficientemente transparentes para el compilador, de modo que aún pueda realizar la optimización en ellas (¿alguien sabe algo al respecto?)

Fuente: Foldable and Traversable
Véase también la respuesta a esta Why is Haskell missing “obvious” Typeclasses