<h2>Background</h2>
<p>I have a problem designing a list structure for my language.</p>
<p>My language use explicitly mutability, that is, all mutability must be manually marked.</p>
<p>But when I marked the mutability of lists, I found that there are two kinds of mutability in lists.</p>
<ol>
<li>Whether the element can be modified.</li>
<li>Whether the length can be modified.</li>
</ol>
<p>Note that 2 is stronger than 1, you can get the ability to modify elements by truncating and splicing.</p>
<p>This problem can be expressed in rust as:</p>
<pre class="lang-rust prettyprint-override"><code>let mut list = &amp;mut Vec&lt;&amp;mut T&gt;&gt;
//  ^^^        ^^^^     ^^^^
//  |          |        | =&gt; Whether internal variables can be modified
//  |          | =&gt; Whether the list length can be modified
//  | =&gt; Whether the variable can be rebinded
</code></pre>
<hr />
<h2>Problem</h2>
<p>My dilemma is there are no pointers in my language, let alone the concept of mutable pointers.</p>
<p>If I use equivalent types, there are at least 4 cases for each collection type:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th style="text-align: left;">My Types</th>
<th style="text-align: left;">Rust Equivalent</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: left;"><code>List&lt;T&gt;</code></td>
<td style="text-align: left;"><code>&amp;mut [T]</code></td>
</tr>
<tr>
<td style="text-align: left;"><code>ListView&lt;covariant T&gt;</code></td>
<td style="text-align: left;"><code>&amp;[T]</code></td>
</tr>
<tr>
<td style="text-align: left;"><code>MutableList&lt;T&gt;</code></td>
<td style="text-align: left;"><code>&amp;mut [&amp;mut T]</code></td>
</tr>
<tr>
<td style="text-align: left;"><code>MutableListView&lt;T&gt;</code></td>
<td style="text-align: left;"><code>&amp;[&amp;mut T]</code></td>
</tr>
</tbody>
</table>
</div>
<p>Not only are there more types, but also more methods, at least <code>get</code> and <code>get_mut</code> must be prepared. The amount of code has increased significantly.</p>
<h2>Question</h2>
<p>I wonder if there's a flexible way to track different mutability so that</p>
<ul>
<li>Flexible marking of mutability capabilities, such as deletion, addition, modification of field values, modification to covariant types.</li>
<li>Don't need extra types and interfaces(no <code>List</code> vs <code>MutableList</code>, <code>get</code> vs <code>get_mut</code>, <code>iter</code> vs <code>iter_mut</code>, etc.).
<ul>
<li>The interface needs to be one for ffi, but other flags are allowed, such as <code>get(mut? self) -&gt; T</code>, <code>set(mut self, v: U) where T &lt;: U</code>.</li>
</ul>
</li>
<li>Trace the source of mutable for error reporting.
<ul>
<li>Since all values are immutable by default, then mutable values must have manually marked source.</li>
</ul>
</li>
</ul>

<language-design><mutability>
How do you design mutable lists?
CC BY-SA 4.0
2023-06-28T04:18:39.243Z
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).
Alexis King
CC BY-SA 4.0
2023-06-30T12:30:42.107Z
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.
BoppreH
CC BY-SA 4.0
2023-06-30T12:32:32.737Z
@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.
Aster
CC BY-SA 4.0
2023-06-30T18:27:59.860Z
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.)
Pablo H
<h2>Arrays for constant size lists, Lists for mutant size collections</h2>
<p>The mutability of size should be marked on a <code>List&lt;&gt;</code> interface or trait. Any <code>Array</code> interface would lack any size changing method.</p>
<p>Arrays will have a <code>const .Length</code> property, but collections will have a <code>.Length</code> method or calculated property.</p>
<p>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 <code>get</code> or <code>iter</code> will reflect that.</p>
<h2>ArrayReader, ArrayWriter and other (very) small interfaces</h2>
<p>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.</p>
<p>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 (<code>CollectionAdd</code>, <code>CollectionSet</code>) or even no method at all (see Marker interface pattern on <a href="https://en.wikipedia.org/wiki/Marker_interface_pattern" rel="nofollow noreferrer">Wikipedia</a>).</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Intersection_type" rel="nofollow noreferrer">intersection type syntax</a> to become easy to express.</p>

CC BY-SA 4.0
2023-06-29T16:04:39.843Z
2023-06-29T16:09:52.067Z
2023-06-29T16:09:52.067Z
André L F S Bacci
<h1>Swift: MutableCollection and RangeReplaceableCollection</h1>
<p>MutableCollection and RangeReplaceableCollection are a pair of traits in Swift that encapsulate different kinds of mutation.</p>
<p>Both of them require you to have the ability to set the value, so a property marked <code>{ get }</code> rather than <code>{ get set }</code>, or a local variable declared <code>let</code> rather than <code>var</code>, can only make use of their common supertype, Collection. This is because, with the exception of <a href="https://langdev.stackexchange.com/a/730/15"><code>set</code> and <code>_modify</code></a>, Swift does not distinguish mutating a value from reassigning it. Both require at least one of <code>set</code>/<code>_modify</code> to be present for computed properties, both trigger <code>didSet</code> listeners, and so on.</p>
<p>MutableCollection describes the ability to change elements in-place, i.e. <code>arr[3] = foo</code>. This could be implemented by a fixed-length array or a dynamic list, but probably not a hashtable, for example.</p>
<p>RangeReplaceableCollection describes the ability to insert and remove items, with methods like <code>append(_:)</code> and <code>removeAll(where:)</code>. This could be implemented by a dynamic list or hashtable, but not a fixed-length array.</p>

CC BY-SA 4.0
2023-06-27T11:46:44.883Z
2023-06-30T12:36:19.460Z
2023-06-30T12:36:19.460Z
Bbrk24
# How do you design mutable lists?
Posted by: username_0 on 2023-06-27
Background
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.

Whether the element can be modified.
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


Problem
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
&mut [T]


ListView
&[T]


MutableList
&mut [&mut T]


MutableListView
&[&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.
Question
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.
**Tags:** language-design mutability
> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_3**: 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.)  
---
## 2 answers
### Answer by username_4 on 2023-06-29. Score: 3
## 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](https://en.wikipedia.org/wiki/Marker_interface_pattern)).

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](https://en.wikipedia.org/wiki/Intersection_type) to become easy to express.
---
### Answer by username_5 on 2023-06-27. Score: 3
# 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`](https://langdev.stackexchange.com/a/730/15), 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.
---
