Estas estructuras son necesarias para las aplicaciones en tiempo real, por ejemplo, las interfaces de usuario. (A los usuarios no les importa si hacer clic en un botón toma 0.1s o 0.2s, pero sí les importa si el clic número 100 obliga a un cálculo perezoso sobresaliente y toma 10s para continuar).

Estaba leyendo la tesis de OkasakiEstructuras de datos puramente funcionales. y describe un método general interesante para convertir estructuras de datos perezosos con límites amortizados en estructuras con el mismolímites del peor caso paracada operación. La idea es distribuir los cálculos de modo que en cada actualización se obligue a una parte de los thunks no evaluados.

Me pregunto, ¿existe tal implementación de colecciones estándar (Map, Set, etc.) en Haskell?

loscontenedores paquete dice

El costo declarado de cada operación es el peor de los casos o se amortiza, pero sigue siendo válido incluso si las estructuras se comparten.

por lo tanto, no hay garantía de los límites del caso más desfavorable para una sola operación. Existen variantes estrictas comoData.Map.Strict, pero son estrictos en sus claves y valores:

Los argumentos clave y de valor se evalúan a WHNF; Las claves y los valores se evalúan en WHNF antes de que se almacenen en el mapa.

No hay nada de (posible) rigor de su estructura.