Lists, sets and dictionaries

Choose a list for an ordered sequence that can grow, a set for unique members, and a dictionary for values addressed by keys. Every collection has statically known types. A list cannot quietly change from integers to unrelated strings.

Lists

numbers = [3, 1, 2]
Append(BYREF numbers, 4)
PRINT numbers[0]
PRINT numbers[-1]
PRINT LEN(numbers)
ordered = Sorted(numbers)
PRINT ordered[0]
PRINT numbers[0]
Sort(BYREF numbers)
PRINT numbers[0]

List indices start at zero; -1 is the last element. Empty lists need a type context: DIM names AS LIST OF STRING = []. LIST() without context constructs an INTEGER list. List literals evaluate elements left to right.

Sort and Reverse mutate a list and require BYREF. Sorted and Reversed produce independent values. They also have string forms where applicable; strings do not have mutating Sort/Reverse overloads. Default sorting is stable. Custom comparison functions are covered in chapter 13.

Insert, RemoveAt and ExtractAt use checked positions. Pop removes and returns the last value, reporting EmptyCollection if empty. Remove removes the first equal value; Clear destroys contents while retaining capacity. Extend appends a sequence, and Concat returns a combined independent sequence. Do not pass the same list as both a BYREF destination and a borrowed source; explicitly copy the source if you need its snapshot.

Slices

values = [0, 1, 2, 3, 4]
middle = values[1:4]
PRINT JOIN([STR(middle[0]), STR(middle[-1])], ",")
backwards = values[::-1]
PRINT backwards[0]
values[1:3] = [8, 9, 10]
PRINT LEN(values)

Slices use a half-open start:finish interval, an optional stride, omitted bounds and negative indices. Copyable slices are independent values. List slice replacement can change length for a unit stride; extended-slice replacement must meet the reference’s length rules. A zero stride is invalid. STRING slices return text; STRING element/slice assignment is rejected.

Direct LIST indexing has a fatal bounds policy. Some named editing and slicing APIs report checked IndexError instead. Do not assume every out-of-range operation is catchable; choose the operation appropriate to your input validation policy.

Sets

DIM names AS SET OF STRING = SET()
PRINT Insert(BYREF names, "Ada")
PRINT Insert(BYREF names, "Ada")
PRINT Contains(names, "Ada")
PRINT LEN(names)

Insertion reports whether a new member was added. Sets retain insertion order for iteration, although set equality ignores order. Union, Intersection, Difference and SymmetricDifference create new sets. Removal followed by reinsertion places a member last. Resource members are not supported.

Dictionaries

DIM counts AS DICT OF STRING TO INTEGER = DICT()
counts["apples"] = 2
counts["apples"] += 1
PRINT Get(counts, "apples")
PRINT Get(counts, "oranges", 0)
IF LET count = Find(counts, "oranges") THEN
    PRINT count
ELSE
    PRINT "Not recorded"
END IF
FOR EACH name, count IN counts
    PRINT name; ":"; count
NEXT

Put or bracket assignment inserts/replaces a value. Replacement keeps the key’s position; removal/reinsertion moves it last. Get without a fallback reports MissingKey. Get with a fallback evaluates that fallback eagerly, even when the key exists, and does not insert. SetDefault inserts when missing. Find returns an optional and therefore distinguishes a missing key from a stored zero. Keys and Values return independent copyable snapshots. Extract removes an entry and returns its value in an optional; Remove destroys it.

Keys need coherent equality and hashing. NaN is rejected as a key/member, including inside derived composite keys; infinity is allowed and signed zeros hash equally. Resource dictionary values are supported, with ownership rules in chapter 10; resource keys are not.

Query collections with predicates

values = [1, 2, 3, 4]
PRINT Any(values, Even)
PRINT All(values, Even)
PRINT CountWhere(values, Even)
FOR EACH value IN Filter(values, Even)
    PRINT value
NEXT
FUNCTION Even(value AS INTEGER) AS BOOLEAN = value MOD 2 = 0

A predicate is a function returning BOOLEAN. Any stops on the first true result; All stops on the first false result. CountWhere visits all entries; Filter builds an independent result in source order. List searches also include IndexWhere, LastIndexWhere and FindWhere. Dictionary predicates receive key and value. These predicates must be infallible. Named functions, checked callable values and contextually typed lambdas are supported. The source stays protected while a callback runs, including if it suspends.

Choose a collection for the job

The prelude also supplies generic collection records. They need no import or application package dependency. Choose their types explicitly at empty construction: DIM jobs AS Queue[STRING] = NewQueue(). A later Enqueue cannot infer the type of an earlier untyped empty factory. Use Length for these records’ logical count; LEN remains the operation for core lists, sets, dictionaries and arrays.

Reset empties a collection without changing its configuration. Copies and copyable snapshots are independent. Insertion takes an owned BYVAL payload: borrowed copyable inputs are copied, fresh values are adopted, and named resources need TAKE. Resource Front/Peek/Lookup-style results borrow the stored owner; removal/extraction transfers it. The entire collection stays protected through consumption, including suspension. Snapshot operations that would copy resources are rejected.

Queues, deques and bounded histories

DIM jobs AS Deque[STRING] = NewDeque()
PushBack(BYREF jobs, "build")
PushFront(BYREF jobs, "check")
PRINT PopFront(BYREF jobs)
PRINT PopBack(BYREF jobs)
DIM queue AS Queue[INTEGER] = NewQueue()
Enqueue(BYREF queue, 10)
Enqueue(BYREF queue, 20)
PRINT Dequeue(BYREF queue)
PRINT Length(queue)

A deque uses a circular buffer, with amortized constant-time end operations. A queue exposes FIFO access over that storage. Empty reads/removals raise EmptyCollection. Snapshot returns the logical sequence, rather than physical buffer order, and requires copyable payloads.

A bounded deque has a positive capacity. Pushing into a full end returns the evicted value from the opposite end in SOME; a push without eviction returns NONE. Eviction hands ownership to your code, which can inspect it or let it clean up.

DIM recent AS BoundedDeque[STRING] = NewBoundedDeque(2)
PushBack(BYREF recent, "first")
PushBack(BYREF recent, "second")
IF LET evicted = PushBack(BYREF recent, "third") THEN
    PRINT "Evicted: "; evicted
END IF
PRINT Front(recent)
PRINT Capacity(recent)

Priority queues

DIM work AS PriorityQueue[STRING] = NewPriorityQueue()
Push(BYREF work, 20, "later")
Push(BYREF work, 5, "urgent")
PRINT PeekPriority(work)
PRINT PopPriority(BYREF work)
PRINT PopPriority(BYREF work)

This is a min-heap: smaller signed INTEGER priorities come first. Equal-priority order is unspecified, so add your own ordering policy if ties matter. Payloads need no comparison operation. Push/pop take logarithmic time; peeking takes constant time. Resource payloads move during sifting rather than being copied.

Sorted keys

DIM names AS SortedSet[STRING] = NewSortedSet()
InsertValue(BYREF names, "Grace")
InsertValue(BYREF names, "Ada")
PRINT At(names, 0)
DIM scores AS SortedDictionary[STRING,INTEGER] = NewSortedDictionary()
SetValue(BYREF scores, "Grace", 2)
SetValue(BYREF scores, "Ada", 3)
PRINT JOIN(KeySnapshot(scores), ",")
PRINT LookupRequired(scores, "Ada")

Core SET/DICT retain insertion order; these records keep keys sorted. NewOrderedSet and NewOrderedDictionary are contextual factories for the existing core types. Sorted lookup uses binary search; insertion/removal shifts a vector and is linear. Ranges are half-open and reversed ranges are empty. Lookup returns an optional; LookupRequired reports MissingKey. At uses a checked nonnegative index. Sorted sets also provide merging set algebra; sorted dictionaries provide independent key/value snapshots and a borrowed resource Values view.

Keys follow canonical equality/hash/order laws and reject structural NaNs. Sorted containers do not make an inconsistent custom comparison coherent.

Counters and multiple values per key

DIM counts AS Counter[STRING] = NewCounter()
Add(BYREF counts, "red", 3)
Add(BYREF counts, "blue")
PRINT Count(counts, "missing")
PRINT TotalCount(counts)
PRINT RemoveValue(BYREF counts, "red", 2)
PRINT Count(counts, "red")
DIM authors AS MultiMap[STRING,STRING] = NewMultiMap()
Add(BYREF authors, "manual", "Ada")
Add(BYREF authors, "manual", "Grace")
PRINT JOIN(GetAll(authors, "manual"), ",")
PRINT Length(authors)
PRINT TotalCount(authors)

Counter Length counts distinct keys; TotalCount counts occurrences. Missing counts are zero; reaching zero removes the key. Amounts must be nonnegative, and invalid amounts or overflow raise CollectionError before mutation. Removal reports the amount actually removed, bounded by the stored count.

MultiMap keeps duplicates in per-key insertion order. GetAll returns an independent copyable list, or empty when missing. Get raises MissingKey; Find returns optional presence. Resource buckets can be borrowed with Get/Find, extracted whole with Extract, or have one owner removed with ExtractAt. RemoveKey destroys its values; removing the last value also removes the key. RemoveOne uses equality and is copyable-only.

Bitsets

bits = NewBitSet(10)
Include(BYREF bits, 2)
Include(BYREF bits, 7)
Flip(BYREF bits, 2)
PRINT Has(bits, 2)
PRINT Has(bits, 7)
PRINT Length(bits)
FOR EACH index IN Members(bits)
    PRINT index
NEXT

A bitset represents integer membership in [0, size), packed into UINT64 words. Capacity is the universe size; Length counts set bits. Indices are nonnegative and checked with IndexError. Members lists them in ascending order. BitUnion, BitIntersection, BitDifference and BitSymmetricDifference require equal universes; Complement flips valid bits without exposing padding. Reset retains the universe.

Bounded caches: recency, expiry and weight

A cache evicts values to stay within a positive entry bound and, optionally, a weight bound. LRU means least recently used. A successful Find refreshes recency; Peek does not. An insertion result reports Inserted, Evicted and Expired counts.

DIM cache AS Cache[STRING,STRING] = NewCache(2)
CachePut(BYREF cache, "a", "alpha")
CachePut(BYREF cache, "b", "beta")
IF LET value = CacheFind(BYREF cache, "a") THEN
    PRINT value
END IF
result = CachePut(BYREF cache, "c", "gamma")
PRINT result.Evicted
IF LET value = CachePeek(cache, "b") THEN
    PRINT value
ELSE
    PRINT "b was evicted"
END IF

TTL means time to live, measured since the most recent write. Reads do not extend TTL. Policies are LRU, TTL and LRUWithTTL. TTL policies require a positive Duration; plain LRU forbids a TTL and reads no clock. Weights are caller-chosen accounting units, not measured bytes. maxWeight=0 disables that bound. A single write must satisfy the configured weight policy.

Use NewTimedCache and the At operations with samples from a caller-owned clock when expiry must be deterministic:

clock = NewTestClock(InstantFromUnixSeconds(0))
DIM cache AS Cache[STRING,STRING] = NewTimedCache(2, CachePolicy.TTL, Seconds(1), NowMonotonic(clock))
CachePutAt(BYREF cache, "key", "value", NowMonotonic(clock))
AdvanceTestClock(BYREF clock, Seconds(1))
PRINT ResidentCount(cache)
PRINT PruneExpiredAt(BYREF cache, NowMonotonic(clock))
PRINT ResidentCount(cache)

Expiry occurs at age greater than or equal to TTL. ResidentCount/ResidentWeight include expired entries not yet pruned; CacheCount prunes first. External samples must be from the accepted clock domain and mutating samples must not move backward. External caches require At calls; ordinary caches reject them. These mistakes are checked errors. Pruning can occur before a later write fails, so a failed edit is not a rollback transaction.

Caches are ordinary exclusive mutable values, with no implicit lock, timer task, loader or request coalescing. Resource Find/Peek results are loans and Extract transfers ownership. All these generic records hide their storage: serialize logical copyable snapshots or supply a concrete formatter, rather than expecting automatic JSON to expose private representation fields. See the collection-family reference for every operation, cost and checked failure.