Use regions and `MutList` in the implementation of `flatMap` on some data structures (e.g. `List`)

[magnus-madsen]

@JonathanStarup Does this apply to all flatMaps or just some?

[JonathanStarup]

@JonathanStarup Does this apply to all flatMaps or just some?

the speed increase?

[magnus-madsen]

@JonathanStarup Does this apply to all flatMaps or just some?

the speed increase?

No, can all flatMaps be implemented this way?

[JonathanStarup]

Yes

• List
• DelayList (I'm not sure because of the lazyness, but current implementation looks quadratic)

No

• Option (one element)
• Result (one element)
• Choice (one element)
• Array (append is done by index in the implementation, thus linear time)
• Chain (append is O(1), thus linear time)
• Nec (uses Chain)
• Nel (uses List)
• Iterator (on-demand)

---

In conclusion: We can do it for List and possibly Array. These same considerations apply to flatten. It seems no mutable structures have flatten/flatMap?