Haskell-Sammlungen mit garantierten Worst-Case-Grenzen für jede einzelne Operation?

Solche Strukturen werden für Echtzeitanwendungen benötigt - zum Beispiel für Benutzeroberflächen. (Benutzer interessieren sich nicht dafür, ob das Klicken auf eine Schaltfläche 0,1s oder 0,2s dauert, sie kümmern sich jedoch darum, ob das 100. Klicken eine hervorragende verzögerte Berechnung erzwingt und 10s benötigt, um fortzufahren.)

Ich habe Okasakis These gelesenRein funktionale Datenstrukturen und er beschreibt eine interessante allgemeine Methode zum Umwandeln fauler Datenstrukturen mit amortisierten Grenzen in Strukturen mit denselbenWorst-Case-Grenzen fürjeden Operation. Die Idee ist, Berechnungen so zu verteilen, dass bei jeder Aktualisierung ein Teil der nicht bewerteten Thunks gezwungen wird.

Ich frage mich, ob es eine solche Implementierung von Standardsammlungen gibt (Map, Setusw.) in Haskell?

DasBehälter Paket sagt

Die angegebenen Kosten für jede Operation sind entweder im schlimmsten Fall oder amortisiert, gelten jedoch auch dann, wenn Strukturen gemeinsam genutzt werden.

Es gibt also keine Garantie für die Worst-Case-Schranken für eine einzelne Operation. Es gibt strenge Varianten wieData.Map.Strict, aber sie sind streng in ihren Schlüsseln und Werten:

Schlüssel- und Wertargumente werden zu WHNF ausgewertet; Schlüssel und Werte werden vor dem Speichern in der Karte als WHNF ausgewertet.

es gibt nichts über (mögliche) Strenge seiner Struktur.

Antworten auf die Frage(1)

Ihre Antwort auf die Frage