Wie könnte ein echter Vektortyp in Haskell implementiert werden? Damit etwas ein Vektor ist, muss es nacheinander im Speicher gespeichert werden, mit O(1) wahlfreiem Zugriff. Aber Haskell verbirgt seine Speicherverwaltung und seine Datentypen beschreiben Bäume! Wie können Sie diese Art von Anforderung ausdrücken?
Kommentare
- Verwenden Sie die mathematischen Definitionen für echte Vektoren. Hier ' ist eine Vektorraumbibliothek für Sie hackage.haskell.org/package/vector-space-0.8.7/docs/ …
- Woher kommen diese Anforderungen für Vector? Ich kenne mehrere Definitionen des Begriffs ' vector ' und nur eine von ihnen hat solche Anforderungen (C ++ ' s
std::vector). - In einigen Fällen auf die gleiche Weise wie beim Speichern eines Werts im Register in beispielsweise C oder C ++, oder Sie geben frei Speicher in GC-Sprache – Der Compiler kann Daten neu anordnen, die Werte in ein Register eintragen usw. oder die Dinge durch (Erweiterungen) [ tinyurl.com/ovvxtqt weibl. / (Bibliotheken) verfügbar machen. [http://hackage.haskell.org/… an Programmierer, wenn sie diese wirklich benötigen – aber es wird davon ausgegangen, dass sie sich in den meisten Fällen nicht darum kümmern '. In ähnlicher Weise ist es Haskell-Programmierern ' in den meisten Fällen egal, ob die Daten in einen sequentiellen Speicherbereich gepackt werden, anstatt beispielsweise die Notwendigkeit einer Auswertung vollständig zu eliminieren.
Antwort
Nicht alle Datentypen in Haskell sind Bäume. Es gibt auch die eingebauten Typen wie Funktionen oder Int. Unter diesen finden Sie den Typ Array , mit dem Sie O (1) auf seine Elemente zugreifen können.
Einige Compiler wie GHC bieten ebenfalls Unboxed Arrays. Diese benötigen weniger Speicher und der Zugriff pro Element ist schneller, aber das ändert natürlich nichts an der Komplexität.
Auf diesen Arrays können Datentypen erstellt werden, die std::vector in C ++. Ein Beispiel ist die Vektorbibliothek .
Antwort
Sie sollten sich Data.Vector.Unboxed und Data.Vector.Mutable im Vektorpaket ansehen: