[kadoban]

The key is that you can start with any immutable data structure you like and change it as much as you want until it stops performing as desired. If that's errors (inability to reason about it correctly) or some other issue, doesn't really matter.

The point is that this procedure applies to anything. Immutable data structures are a strict subset of mutable ones. Every immutable data structure is open to moving any number of steps, in any direction, in the space of data structures. It's _purely_ extra freedom that immutable data structures don't have.

If you want specific ones, first things that would come to mind for me is to start with any immutable tree impl, and start adding small mutable ~caching things on top. Batch up updates a bit to try to avoid repeated deep traversals maybe. You can do this without adding much complexity at all, and it's very flexibly for whatever operations or access patterns you want to improve.

[kephasp]

Look for actual examples in the wild that weren't error prone and I'd be surprised you'll find any.

I get that you can imagine it. I'm saying it wouldn't work in practice.

[kadoban]

Searching wide and far for a data structure that's that niche in implementation is not really sensible, I'd probably have to implement one myself. If the sketch above doesn't satisfy you, that's about the end for me. Have a good one.

[kephasp]

You need to sketch it and possibly implement it yourself because actual examples don't exist. QED