ejercicio - listas intensionales haskell

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

Estoy leyendo Learn You a Haskell y me pregunto por qué tantas cosas actúan como una lista, y nada en el Prelude está utilizando la facilidad nativa de las clases de tipos para configurar esto:

"La versión de bytes de: se llama cons. Toma un byte y una cadena de bytes y pone el byte al principio. Sin embargo, es un elemento vago, por lo que creará un nuevo fragmento incluso si el primer fragmento en la cadena de bytes no está completo. es mejor usar la versión estricta de contras, contras ''si vas a insertar muchos bytes al principio de una cadena de bytes''.

¿Por qué no hay un TypeClass enumerable o algo que ofrece la función : para unificar Data.ByteString , Data.List , Data.ByteString.Lazy , etc.? ¿Hay alguna razón para esto o es solo un elemento heredado de Haskell? Usar : como ejemplo es una especie de subestimación, también de LYAH:

De lo contrario, los módulos de cadena de bytes tienen una carga de funciones que son análogas a las de Data.List, que incluyen, entre otros, cabeza, cola, init, nulo, longitud, mapa, inversión, foldl, foldr, concat, takeWhile, filtro , etc.

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

Se han intentado crear una buena interfaz de secuencia, yb) la interfaz de contenedores, sin embargo, la unificación de tipos de datos de diferentes tipos, con diferentes restricciones de tipo, generalmente ha hecho que los resultados no sean lo suficientemente estándar como para que sea difícil de 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 única interfaz, por lo que espero ver un resultado pronto. Del mismo modo para los tipos de contenedores. El resultado no será trivial sin embargo.

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 las 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 prueba esto?

type BS a = ByteString instance List BS

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 se implementa 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 contenedores a considerar:

Contenedores a los que no les importan sus elementos (p. Ej. [])
Contenedores que solo se implementan para elementos específicos (p. Ej. Cadenas de bytes)
Contenedores que son polimórficos sobre elementos pero requieren un contexto (por ejemplo, Data.Vector.Storable, que contendrá cualquier tipo con una instancia almacenable).

Aquí hay una clase de estilo ListLike muy básica sin usar 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í el container tiene kind *->* . Esto no funcionará para las cadenas de bytes porque no permiten un tipo arbitrario; tienen clase * . Tampoco funcionará para un vector Data.Vector.Storable, porque la clase no incluye el contexto (la restricción Storable).

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

class ListableMPTC container elem | container -> elem where

class ListableAT container where type Elem container :: *

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

instance ListableMPTC [a] a where

pero ya no eres Haskell98.

Es por eso que incluso una interfaz simple de tipo Listable no es trivial; se vuelve un poco más difícil cuando tienes que contar con 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 conjeturas de mi parte, pero creo que estamos atrapados con las 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 utilizar 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 restricciones 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.

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

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

En el caso de cadenas de bytes estrictas, crearlas con contras 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 un comportamiento O (n ^ 2) cuando implementa el primer algoritmo que podría pensarse, mapear, mientras que construir una lista o Data.Sequence.Seq con cons es tiempo lineal y puede implementarse en O (n) para cadenas de bytes o vectores también con un poco de pensamiento.

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

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

He sacado 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) porque se ha hecho antes para poco éxito yb) debido a las preocupaciones asintóticas anteriores.

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

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

Fuente: Plegable y Traversable
Ver también esta respuesta a ¿Por qué Haskell no tiene las clases de tipos "obvias"?

No tiene mucho valor tener una clase de tipo para los datos de tipo lista en Haskell. ¿Por qué? Por 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 .

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