I have a problem designing a list structure for my language.

My language use explicitly mutability, that is, all mutability must be manually marked.

But when I marked the mutability of lists, I found that there are two kinds of mutability in lists.

  1. Whether the element can be modified.
  2. Whether the length can be modified.

Note that 2 is stronger than 1, you can get the ability to modify elements by truncating and splicing.

This problem can be expressed in rust as:

let mut list = &mut Vec<&mut T>>
//  ^^^        ^^^^     ^^^^
//  |          |        | => Whether internal variables can be modified
//  |          | => Whether the list length can be modified
//  | => Whether the variable can be rebinded


My dilemma is there are no pointers in my language, let alone the concept of mutable pointers.

If I use equivalent types, there are at least 4 cases for each collection type:

My Types Rust Equivalent
List<T> &mut [T]
ListView<covariant T> &[T]
MutableList<T> &mut [&mut T]
MutableListView<T> &[&mut T]

Not only are there more types, but also more methods, at least get and get_mut must be prepared. The amount of code has increased significantly.


I wonder if there's a flexible way to track different mutability so that

  • Flexible marking of mutability capabilities, such as deletion, addition, modification of field values, modification to covariant types.
  • Don't need extra types and interfaces(no List vs MutableList, get vs get_mut, iter vs iter_mut, etc.).
    • The interface needs to be one for ffi, but other flags are allowed, such as get(mut? self) -> T, set(mut self, v: U) where T <: U.
  • Trace the source of mutable for error reporting.
    • Since all values are immutable by default, then mutable values must have manually marked source.
  • $\begingroup$ I think this question is arguably an open research problem. There is no consensus answer, and systems in this direction have a high complexity cost (and can make things like type inference enormously more difficult). $\endgroup$
    – Alexis King
    Jun 28, 2023 at 4:18
  • $\begingroup$ Are you also considering mutability of other collections, like HashMap? I can think of a few scenarios where I want functions to be able to update values, but not add or remove keys. $\endgroup$
    – BoppreH
    Jun 30, 2023 at 12:30
  • $\begingroup$ @BoppreH I thought about it, but I found that it involves more complicated issues, the key is generally contravariant, and the value contravariance and value covariance are different maps. $\endgroup$
    – Aster
    Jun 30, 2023 at 12:32
  • $\begingroup$ I think you're missing one mutation case in your list, in the case of elements of composite types: modifying one list "position" by replacing it with something else, instead of modifying a part of the element. (Perhaps this doesn't make sense for your language. E.g. element is of a reference type.) $\endgroup$
    – Pablo H
    Jun 30, 2023 at 18:27

2 Answers 2


Arrays for constant size lists, Lists for mutant size collections

The mutability of size should be marked on a List<> interface or trait. Any Array interface would lack any size changing method.

Arrays will have a const .Length property, but collections will have a .Length method or calculated property.

The mutability of a container's contents is defined in these interfaces, but the mutability of container's itens is defined on the container's generic type, so any get or iter will reflect that.

ArrayReader, ArrayWriter and other (very) small interfaces

Separating interfaces for reading and writing array's elements may be seen as over-engineering, but will come handy when building library code where array (in)mutating is relevant.

The same concept may be applied on collections interfaces or traits, where concepts may be factored in very small interfaces, down to having one method only (CollectionAdd, CollectionSet) or even no method at all (see Marker interface pattern on Wikipedia).

This will come handy when developing library code where some algorithms will be available to some arrays or collections depending only if they have the required interfaces, but will require some form of intersection type syntax to become easy to express.


Swift: MutableCollection and RangeReplaceableCollection

MutableCollection and RangeReplaceableCollection are a pair of traits in Swift that encapsulate different kinds of mutation.

Both of them require you to have the ability to set the value, so a property marked { get } rather than { get set }, or a local variable declared let rather than var, can only make use of their common supertype, Collection. This is because, with the exception of set and _modify, Swift does not distinguish mutating a value from reassigning it. Both require at least one of set/_modify to be present for computed properties, both trigger didSet listeners, and so on.

MutableCollection describes the ability to change elements in-place, i.e. arr[3] = foo. This could be implemented by a fixed-length array or a dynamic list, but probably not a hashtable, for example.

RangeReplaceableCollection describes the ability to insert and remove items, with methods like append(_:) and removeAll(where:). This could be implemented by a dynamic list or hashtable, but not a fixed-length array.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .