Takie struktury są niezbędne w przypadku aplikacji czasu rzeczywistego - na przykład interfejsów użytkownika. (Użytkownicy nie przejmują się tym, że kliknięcie przycisku zajmuje 0.1s lub 0.2s, ale zależy im na tym, aby 100 kliknięcie wymusiło znakomite obliczenia leniwe i trwa 10s.)

Czytałem tezę OkasakiCzysto funkcjonalne struktury danych i opisuje interesującą ogólną metodę przekształcania leniwych struktur danych z amortyzowanymi granicami w struktury z tym samymnajgorsze granicekażdy operacja. Chodzi o to, aby dystrybuować obliczenia tak, aby przy każdej aktualizacji wymuszana była pewna część nieocenionych gromów.

Ciekawe, czy istnieje taka implementacja standardowych kolekcji (Map, Setitd.) w Haskell?

Thepojemniki pakiet mówi

Deklarowany koszt każdej operacji jest albo najgorszy, albo amortyzowany, ale pozostaje ważny, nawet jeśli struktury są współdzielone.

więc nie ma gwarancji na najgorsze granice dla pojedynczej operacji. Istnieją ścisłe wariantyData.Map.Strict, ale są ścisłe w swoich kluczach i wartościach:

Argumenty klucza i wartości są oceniane na WHNF; Klucze i wartości są oceniane na WHNF, zanim zostaną zapisane na mapie.

nie ma nic o (możliwej) surowości jego struktury.