Wie deklariert man einen abstrakten Datencontainertyp in Haskell?

Question

Ich las William Cooks "On Data Abstraction, Revisited" und las erneut Ralf Laemmels "The Expression Lemma", um zu versuchen zu verstehen, wie man die Ideen des früheren Papiers in Haskell anwendet. Also, ich versuche zu verstehen, wie Sie in Haskell beispielsweise eine Set-Union-Funktion implementieren könnten, ohne die Typen anzugeben?

Answer 1

es mehr Möglichkeiten gibt, je nachdem, welche Version von „abstrakten Datentypen“ sind Sie nach.

• Betons aber undurchsichtiger Typ: Es ist schon eine Weile, da ich Cook schönes Papier lesen, aber wieder darüber denke ich Streif dies am nächsten ist, was er über als ADTs sprechen. Die Standardmethode in Haskell besteht darin, einen Typ ohne seine Konstruktoren zu exportieren. was das bedeutet in Haskell:

  • Kein Muster

  • Keine Konstruktion Werte des Typs auf Werte der abstrahierten Typ passend, mit Ausnahme von seinem Modul exportierten Funktionen mit

  Wie diese bezieht sich auf Cooks Papier:

  • Repräsentationsunabhängigkeit: Von außen ist die Darstellung nicht zugänglich.

  • Überprüfung mehrerer Darstellungen: Innerhalb des ADT-Moduls können Darstellungen frei geprüft werden.

  • Einzigartige Implementierungen/Module: Unterschiedliche Implementierungen können durch verschiedene Module zur Verfügung gestellt werden, aber die Typen außer mit normalen Mitteln nicht zusammenarbeiten können. Sie können Data.IntMap.null nicht verwenden, um zu sehen, ob eine Data.Map.Map Int a leer ist.

  Diese Technik wird ausführlich in den Haskell Standardbibliotheken verwendet werden, insbesondere für die Datentypen, die irgendeine Art von Invarianten oder auf andere Weise beschränken die Fähigkeit, Werte zu konstruieren pflegen müssen. Also in diesem Fall, ist der beste Weg, um die Set ADT aus dem Papier zu implementieren, ist der folgende Code:

  import qualified Data.Set as S 
  

  Obwohl dies vielleicht nicht so mächtig ein Mittel der Abstraktion, wie sie in einer Sprache mit einem ausdrucksvollen sein könnten Modulsystem.

• Existentielle Quantifizierung und Schnittstelle: Haskell nicht wirklich ein exists Stichwort als solche, aber der Begriff „Existenz“ wird unter verschiedenen Umständen verwendet, um bestimmte Arten von polymorphen Typen zu beschreiben. Die allgemeine Idee ist in jedem Fall, einen Wert mit einer Sammlung von Funktionen zu kombinieren, so dass das Ergebnis im Werttyp polymorph ist.Betrachten Sie diese Funktion Unterschrift:

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

  Obwohl es einen Wert vom Typ empfängt a, weil a vollständig polymorph ist das einzige, was es möglicherweise mit diesem Wert tun kann, ist die Funktion für sie gelten. In diesem Sinne ist die erste Hälfte des Tupels gewissermaßen ein "abstrakter Datentyp", während die zweite Hälfte eine "Schnittstelle" für die Arbeit mit diesem Typ ist. Wir können diese Idee explizit machen, und es außerhalb einer einzigen Funktion anwenden, einen existentieller Datentyp:

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

  Nun wird jedes Mal, wenn wir einen Wert vom Typ haben FooADT, alles, was wir wissen ist, dass existiert irgendein Typ a so, dass wir FooADTs zweites Argument zu seinem ersten anwenden können.

  Dieselbe Idee gilt für polymorphe Typen mit Klassenbeschränkungen; Der einzige Unterschied besteht darin, dass die Funktionen, die auf dem Typ ausgeführt werden, implizit von der Typklasse bereitgestellt werden und nicht explizit mit dem Wert gebündelt werden.

  Nun, was bedeutet dies in Bezug auf Cooks Papier?

  • Darstellung Unabhängigkeit gilt nach wie vor.

  • Gesamtisolation: Im Gegensatz zu früher ist die Kenntnis des existentiell quantifizierten Typs für immer verloren. Nichts kann die Repräsentation überprüfen, außer der Schnittstelle, die sie selbst bereitstellt.

  • Beliebige Implementierungen: Nicht nur sind Implementierungen nicht unbedingt einzigartig, es gibt keine Möglichkeit, sie überhaupt zu begrenzen! Alles, was die gleiche Schnittstelle zur Verfügung stellen kann, kann in ein existenzielles eingebettet werden und von anderen Werten nicht zu unterscheiden sein.

  Kurz gesagt, das ist Cooks Beschreibung von Objekten sehr ähnlich. Für weitere existenzielle ADTs ist das Papier Unfolding Abstract Datatypes kein schlechter Startpunkt; aber bedenken Sie, dass das, was es diskutiert, grundsätzlich nicht das ist, was Cook eine ADT nennt.

---

Und ein kurzer Nachtrag: Nach oben zu all der Mühe gemacht existenzielle Art Abstraktionen zu beschreiben, würde Ich mag etwas über den FooADT Typen markieren: Weil alles, was Sie tun können, damit das ist anzuwenden Funktion, um ein Bool Ergebnis zu erhalten, gibt es grundsätzlich keinen Unterschied zwischen FooADT und Bool, außer dass der ehemalige verschleiert Ihren Code und erfordert GHC-Erweiterungen. Ich ermutige dringend reading this blog post, bevor Sie existentielle Typen im Haskell-Code verwenden.

Answer 2

Sie können entweder eine Vergleichsfunktion anfordern oder die Typen als Instanzen von Gl. Siehe nub und nubBy für Beispiele für diese Technik:

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