¿Cómo se declara un tipo de contenedor de datos abstracto en Haskell?

Question

leí William Cook "En Abstracción de datos, Revisited", y volver a leer Ralf Laemmel de "La expresión lema" para tratar de comprender cómo aplicar las ideas de la antigua de papel en Haskell. Entonces, estoy tratando de entender cómo podría implementar, por ejemplo, una función de unión establecida, en Haskell sin especificar los tipos.

Answer 1

Hay múltiples maneras, dependiendo de la versión de "tipos de datos abstractos" que está buscando.

• tipos de hormigón, pero opacos: Ha pasado un tiempo desde que leí el papel precioso de Cook, pero mirando hacia atrás sobre ella Creo que esto es más parecido a lo que está hablando como los ADT. La forma estándar de hacer esto en Haskell es exportar un tipo sin sus constructores; lo que esto significa en Haskell:

  • Sin patrón de coincidencia en los valores del tipo abstracto

  • No hay valores de la construcción del tipo, excepto el uso de las funciones exportadas de su módulo

  Cómo esto se relaciona con el documento de Cook:

  • Independencia de representación: Desde el exterior, la representación es inaccesible.

  • Inspección de varias representaciones: Dentro del módulo de ADT, las representaciones se pueden inspeccionar libremente.

  • Implementaciones/módulos únicos: Diferentes implementaciones pueden ser proporcionadas por diferentes módulos, pero los tipos no pueden interoperar excepto por medios normales. No puede usar Data.IntMap.null para ver si Data.Map.Map Int a está vacío.

  Esta técnica se usa ampliamente en las bibliotecas estándar Haskell, en particular para los tipos de datos que necesitan para mantener algún tipo de invariante o de otra manera restringir la capacidad de construir valores. Así pues, en este caso, la mejor manera de poner en práctica el ADT conjunto del artículo es el siguiente código:

  import qualified Data.Set as S 
  

  Aunque esto es quizás no tan poderoso medio de la abstracción como podría ser en un idioma con una más expresiva sistema de módulos.

• cuantificación existencial y la interfaz: Haskell no tiene realmente una palabra clave exists como tal, pero el término "existencial" se utiliza en diversas circunstancias para describir ciertos tipos de tipos polimórficos. La idea general en cada caso es combinar un valor con una colección de funciones que operan en él, de modo que el resultado sea polimórfico en el tipo del valor.Considere esta función firma:

  foo :: (a, a -> Bool) -> Bool 
  

  A pesar de que recibe un valor de tipo a, porque a es totalmente polimórfico la única cosa que posiblemente puede hacer con ese valor es aplicar la función a ella. Entonces, en cierto sentido, dentro de esta función, la primera mitad de la tupla es un "tipo de datos abstracto", mientras que la segunda mitad es una "interfaz" para trabajar con ese tipo. Podemos hacer que esta idea explícita, y aplicarlo fuera de una sola función, usando un tipo de datos existencial:

  data FooADT = forall a. FooADT a (a -> Bool) 
  
  foo :: FooADT -> Bool 
  

  Ahora, cada vez que tenemos un valor de tipo FooADT, todo lo que sabemos es que existe algún tipo a de modo que podamos aplicar el segundo argumento de FooADT al primero.

  La misma idea se aplica a los tipos polimórficos con restricciones de clase; la única diferencia es que las funciones que operan en el tipo son provistas implícitamente por la clase de tipo, en lugar de ser incluidas explícitamente con el valor.

  Ahora, ¿qué significa esto en términos del artículo de Cook?

  • independencia Representación sigue siendo válida.

  • Aislamiento total: A diferencia de antes, el conocimiento del tipo cuantificado existencialmente se pierde para siempre. Nada puede inspeccionar la representación excepto la interfaz que proporciona.

  • Implementaciones arbitrarias: No solo las implementaciones no son necesariamente únicas, ¡no hay forma de limitarlas en absoluto! Cualquier cosa que pueda proporcionar la misma interfaz puede envolverse dentro de un elemento existencial y ser indistinguible de otros valores.

  En resumen, esto es muy similar a la descripción de objetos de Cook. Para obtener más información sobre los ADT existenciales, el documento Unfolding Abstract Datatypes no es un mal lugar para comenzar; pero tenga en cuenta que lo que discute no es fundamentalmente lo que Cook llama un ADT.

---

Y un corto adición: Después de haber ido a todos los problemas anteriormente para describir las abstracciones de tipo existencial, me gustaría destacar algo sobre el tipo FooADT: Porque todo lo que puede hacer con él es aplicar el función para obtener un resultado Bool, no hay diferencia entre entre FooADT y Bool, excepto que el primero ofusca su código y requiere extensiones de GHC. Recomiendo encarecidamente reading this blog post antes de establecer el uso de tipos existenciales en el código Haskell.

Answer 2

Usted puede requerir una función de comparación que debe facilitarse o requerir los tipos a haber casos de la ecuación. Ver nub y nubBy para ejemplos de esta técnica:

nub :: (Eq a) => [a] -> [a] 
nubBy :: (a -> a -> Bool) -> [a] -> [a]