Collections: type hierarchy, mutability, Map/Set/Stack/Queue

[tmteam]

Collection type hierarchy and mutability

Currently NFun only has immutable T[] (arrays). Need mutable collections and new types.

Type hierarchy

T[]  (FixedArray — read-only, covariant, [i], .count)
 ↑
List[T]  (mutable, invariant, [i], [i]=x, .add, .remove)

Set[T]       # .add, .remove, .contains — no [i]
Stack[T]     # .push, .pop — no [i]
Queue[T]     # .enqueue, .dequeue — no [i]
Map[K,V]     # .getKey, .setValue, .removeKey — no [i]

Key design decisions:

• List[T] <: T[] — the only inheritance. A List IS-A read-only array. A function that takes T[] accepts both [1,2,3] and list(1,2,3).
• T[] stays read-only and covariant — int[] <: any[] safe for read operations.
• List[T] is invariant — List[int] is NOT List[any] (mutation safety).
• Stack/Queue have no [i] access — they expose only LIFO/FIFO interface. If you need [i], use List.
• All collections are iterable — for item in set, for entry in map, for item in stack all work.
• Tree, not graph — one inheritance arrow (List <: T[]), everything else is a root.

Type annotations

Annotation	Type	Mutability
int[]	FixedArray	read-only (current behavior)
list[of int]	List	mutable (.add, .remove, [i]=x)
set[of int]	Set	mutable (.add, .remove)
map[of text, int]	Map	mutable (.setValue, .removeKey)
stack[of int]	Stack	mutable (.push, .pop)
queue[of int]	Queue	mutable (.enqueue, .dequeue)

int[] = read-only array (FixedArray). This is unchanged from current behavior.

Since List <: T[], annotation x: int[] = list(1,2,3) is valid — List fits where T[] is expected. But .add() is not accessible through int[] annotation (type narrowed to read-only). To use mutable operations, annotate as x: list[of int] or let TIC infer.

Literal syntax

arr = [1, 2, 3]                    # T[] (FixedArray, read-only)
items = list(1, 2, 3)              # List[T] (mutable)
s = set(1, 2, 3)                   # Set[T]
m = map('a' => 1, 'b' => 2)       # Map[K,V]
st = stack()                       # Stack[T]
q = queue()                        # Queue[T]

[a,b,c] always creates T[] (immutable). Use list(a,b,c) for mutable.

Operations

T[] (read-only):

arr[0]                # index access
arr.count()           # length
arr.map(fun: it * 2)  # transformation
arr.filter(...)       # filtering
arr.fold(...)         # reduction

List[T] (all of T[] plus):

items[0] = 10         # index assignment
items.add(4)          # append
items.remove(2)       # remove first occurrence
items.removeAt(0)     # remove by index
items.clear()         # remove all

Set[T]:

s.add(4)
s.remove(2)
has = 2 in s
s.intersect(other)
s.union(other)

Map[K,V]:

v = m.getKey('a')           # oops if missing
v = m.tryGetKey('a')        # V? — none if missing
m.setValue('c', 3)
m.removeKey('a')
keys = m.keys()              # K[]
vals = m.values()            # V[]
has = m.containsKey('a')

Stack[T] / Queue[T]:

s.push(1)
top = s.pop()               # T? — none if empty

q.enqueue(1)
first = q.dequeue()         # T? — none if empty

TIC implications

• StateArray already exists — this is T[] (read-only, covariant)
• Add StateList as subtype of StateArray. One rule: StateList(T) <: StateArray(T)
• Set/Stack/Queue/Map — opaque types, TIC sees them through function signatures only. No new TIC states.
• .add() on T[] → compile error (immutable). .add() on List[T] → OK.
• Covariance: T[] covariant (read-only safe). List[T] invariant (mutation).

Implementation order

1. List[T] — new TIC state (StateList <: StateArray), list() constructor, .add(), .remove(), [i] = x
2. Map[K,V] — new opaque type, map() constructor, key/value operations
3. Set[T] — new opaque type, set() constructor, set operations
4. Stack / Queue — if needed
5. for iteration on all collection types