Comment peut-on déclarer un type de conteneur de données abstrait dans Haskell?

Question

Je lis « de l'abstraction de données, revisité » de William Cook, et relisez Ralf Laemmel « The lemme d'expression » pour essayer de comprendre comment appliquer les idées de l'ancien papier dans Haskell. Donc, je suis en train de comprendre comment pourriez-vous mettre en œuvre, par exemple, une fonction syndicale définie, dans Haskell sans spécifier les types?

Answer 1

Il y a plusieurs façons, selon la version de « types de données abstraites » vous êtes après.

• Béton mais les types opaques : Cela fait un petit moment que je lis beau papier de Cook, mais en regardant en arrière sur ce que je pense que c'est le plus proche de ce qu'il parle comme ADTs. La méthode standard pour le faire dans Haskell est d'exporter un type sans ses constructeurs; ce que cela signifie Haskell:

  • Non correspondance de motif sur les valeurs du type abstrait

  • Pas de la construction des valeurs du type, à l'exception d'utiliser les fonctions exportées de son module

  Comment cela se rapporte au papier de cuisson:

  • indépendance de représentation:. De l'extérieur, la représentation est inaccessible

  • Contrôle des représentations multiples: A l'intérieur du module d'ADT, les représentations peuvent être librement inspectée

  .

  • implémentations uniques / modules: Différentes mises en œuvre peuvent être fournis par différents modules, mais les types ne peuvent pas interopérer sauf par des moyens normaux. Vous ne pouvez pas utiliser Data.IntMap.null pour voir si un Data.Map.Map Int a est vide.

  Cette technique est largement utilisée dans les bibliothèques standard Haskell, en particulier pour les types de données qui doivent maintenir une sorte d'invariant ou autrement limiter la capacité de construire des valeurs. Donc dans ce cas, la meilleure façon de mettre en œuvre l'ADT ensemble du papier est le code suivant:

  import qualified Data.Set as S
  

  Bien que ce soit peut-être pas aussi puissant moyen d'une de l'abstraction comme il pourrait être dans une langue avec un système de module plus expressif.

• quantification existentialistes et l'interface : Haskell n'a pas en fait un mot-clé exists en tant que tel, mais le terme « existentiel » est utilisé dans diverses circonstances pour décrire certains types de types polymorphes. L'idée générale dans chaque cas est de combiner une valeur avec une collection de fonctions d'exploitation sur elle, de sorte que le résultat est polymorphes dans le type de la valeur. Considérez cette signature de la fonction:

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

  Bien qu'il reçoit une valeur de type a, car a est entièrement polymorphes la seule chose qu'il peut éventuellement faire avec cette valeur est d'appliquer la fonction à lui. Donc, dans un sens, dans cette fonction, la première moitié du tuple est un « type de données abstrait », alors que la seconde est une « interface » pour travailler avec ce type. Nous pouvons faire cette idée explicite, et l'appliquer en dehors d'une seule fonction, en utilisant un type de données existentielles :

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

  Maintenant, chaque fois que nous avons une valeur de type FooADT, tout ce que nous savons est que il existe certains a de type tel que nous pouvons appliquer le deuxième argument de FooADT à son premier.

  La même idée s'applique aux types polymorphes avec contraintes de classe; la seule différence est que les fonctions d'exploitation du type sont fournis implicitement par la classe de type, plutôt que explicitement livré avec la valeur.

  Maintenant, qu'est-ce que cela signifie en termes de papier de Cook?

  • indépendance de représentation toujours applique.

  • isolement total: Contrairement à avant, la connaissance du type existentiellement quantifié est perdu à jamais. Rien ne peut inspecter la représentation à l'exception de l'interface elle-même fournit.

  • implémentations arbitraires: Non seulement sont pas nécessairement mises en œuvre uniques, il n'y a aucun moyen de les limiter du tout! Tout ce qui peut fournir la même interface peut être enroulé à l'intérieur d'une existentielle et être impossibles à distinguer des autres valeurs.

  En bref, ce qui est très similaire à la description de Cook d'objets. Pour en savoir plus ADTs existentielles, le papier dépliage Résumé Datatypes ISN « t un mauvais endroit pour commencer; mais Keep à l'esprit que ce qu'il discute est fondamentalement pas ce que Cook appelle un ADT.

---

Et un supplément court: étant allé à tous les problèmes ci-dessus pour décrire les abstractions de type existentiel, je voudrais souligner quelque chose au sujet du type de FooADT: Parce que tout ce que vous pouvez faire avec elle est d'appliquer la fonction pour obtenir un résultat de Bool, il est fondamentalement aucune différence entre FooADT et Bool , sauf que les anciens obscurcit votre code et nécessite des extensions GHC. Je vous encourage fortement la lecture de ce billet de blog avant cadre out utiliser les types existentiels dans le code Haskell.

Answer 2

Vous pouvez soit besoin d'une fonction de comparaison à fournir ou exiger des types comme cas de l'équation. Voir nub et nubBy des exemples de cette technique:

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