[noctune]

And persistent memory structures also tends to have a cost. For example, persistent maps are usually O(lg n) lookup and insert rather than O(1) usually seen in mutable maps.

If I remember correctly this is a pretty fundamental limitation of persistent structures, so it's not like there is a better persistent map data structure out there waiting.

[consilient]

Lazy structures can usually get the log(n) back when you amortize over many operations.

[noctune]

Sure, but for some structures it amortizes to log(n) where mutable structures can amortize to O(1).