title: Does SML provide an efficient immutable list implementation for very large collections, or should arrays and mutation be used for this optimization?
body: <p>Every time we do cons and destructuring and similar operations on lists, we create copies of the original lists. This can become a performance issue with very large collections.</p>
  <p>It's my understanding that to improve this situation, some programming languages implement lists as data structures that can be copied much more efficiently. Is there something like this in SML? Perhaps in the language definition, or as a feature that is implementation dependent?</p>
  <p>If there's no such data structure, are arrays and mutability one pattern that optimizes on large lists? As long as the state is local to the function, can the function still be considered pure?</p>
  <p>SML is multi-paradigm, but idiomatic SML is also functional-first, so both &quot;lists with efficient copying&quot; and &quot;mutable arrays&quot; approaches should make sense, depending on what the core language offers.</p>
  <p>Is there an immutable data structure that is more efficient than the normal singly linked list for very large collections? If not, is there a native purely functional data structure that can optimize this scenario? Or should mutability and arrays be used internally?</p>