Wie kann ich einen Vektor haben, der in seinen Werten streng ist, wie ein normaler Typ mit Pony (!)?

Question

Einige gemeinsame performance advice in Haskell ist eine schnelle Datenstrukturen „Wirbelsäule streng“, so dass die Struktur, aber nicht unbedingt den Inhalt zu machen, ausgewertet wird vollständig, wie es erstellt wird. Dadurch können wir mehr arbeiten, wenn wir einen Wert einfügen, und die Struktur befindet sich im Cache, anstatt sie abzulegen, bis wir einen Wert nach oben sehen.

Bei einem normalen Datentyp, wie das binäre Trie von Data.IntMap kann diese strenge, indem sie die entsprechenden Felder in der Datenstruktur erreicht werden: (. Auszug aus dem Data.IntMap.Base Quelle)

data IntMap a = Bin {- ... -} !(IntMap a) !(IntMap a) 
       | {- ... -} 

Wie kann ich das gleiche Verhalten erreichen, wenn ich die Kinder in einem Vektor statt direkt als Felder von Bin speichern möchte?

data IntMap a = Bin {- ... -} (Vector (IntMap a)) 
       | {- ... -} 

Answer 1

Zuerst werde ich eine einfache Variante der Frage beantworten: Wenn Ihr Datentyp unboxable ist, z.B. Sie wollen einen strikten Vektor von Int s, verwenden Data.Vector.Unboxed. Als kostenlosen Bonus, die Implementierung ermöglicht es Ihnen, "Struktur von Arrays", (Vector a, Vector b), auch die Schnittstelle ist weniger fehleranfällig "Array von Strukturen", Vector (a, b). Siehe Wikipedia on AOS and SOA.

---

Doch in der Frage, OPs, wollen wir IntMap a in Vector haften, und IntMap ist nicht unboxable (oder speicherbar oder primitive).

Die verschiedenen Optionen laufen auf die gleiche Idee hinaus: Sie müssen seq Werte selbst eingeben. Ob Sie sich für Data.Primitive.Array gehen oder eigene Data.Vector.Strict oben auf Data.Vector Umsetzung (Anmerkung: basicClear kann no-op sein als es für unboxed Vektoren ist, oder Sie unsafeCoerce() als Dummy-Wert verwenden können), Sie werden seq Werte. So wird Data.Map.Strict oben der gleichen faulen Struktur wie Data.Map.Lazy implementiert.

Zum Beispiel map Data.Map.Strict als implementiert:

map :: (a -> b) -> Map k a -> Map k b 
map f = go 
    where 
    go Tip = Tip 
    go (Bin sx kx x l r) = let !x' = f x in Bin sx kx x' (go l) (go r) 

Vergleichen Sie das mit Data.Map.Lazy.map:

map :: (a -> b) -> Map k a -> Map k b 
map f = go where 
    go Tip = Tip 
    go (Bin sx kx x l r) = Bin sx kx (f x) (go l) (go r)