Collections¶

Every Zazr collection is immutable. An operation returns a new collection and shares what it can with the old one, which is never modified.

Each type declares its own methods, with its own return types, and every method whose cost depends on the size documents it. The complexity page lists them all.

Which one to choose¶

You need	Choose	Because
a sequence, by default	`Vector`	effectively O(1) `get`, `update`, `append`, `prepend`, `take`, `drop`
a sequence that has at least one element	`NonEmptyVector`	`head`, `max`, `reduce` cannot fail
to take a sequence apart head first, or a stack	`List`	O(1) `prepend`, `head`, `tail`; pattern matching on `Cons` and `Nil`
first in, first out	`Queue`	O(1) `enqueue`, amortised O(1) `dequeue`
a sequence computed on demand, possibly infinite	`LazyList`	each element computed once, when first read
a set, by default	`HashSet`	effectively O(1) `contains`, `add`, `remove`
a set in insertion order	`LinkedHashSet`	a `HashSet` plus the insertion order, with positional methods
a sorted set	`TreeSet`	O(log n) lookups and updates, positional methods in comparator order
a set that has at least one element	`NonEmptySet`, `NonEmptySortedSet`	`max`, `reduce` (and `head` on the sorted one) cannot fail
a map, by default	`HashMap`	effectively O(1) `get`, `put`, `remove`
a map in insertion order	`LinkedHashMap`	a `HashMap` plus the insertion order, with positional methods
a sorted map	`TreeMap`	O(log n) lookups and updates, positional methods in key order
a map that has at least one entry	`NonEmptyMap`, `NonEmptySortedMap`	`keySet` and `values` stay non-empty, `max` and `reduce` cannot fail

Where they come from¶

Several structures are ported from the Scala 2.13 collections library, which Scala 3 uses unchanged:

Vector and its builder: Scala's Vector and VectorBuilder.
HashSet and HashMap: Scala's CHAMP HashSet and HashMap.
LazyList: the evaluation model of Scala's LazyList.
TreeSet and TreeMap: filter, partition and the one-pass tree building of the builders follow Scala's RedBlackTree.

Every collection except the non-empty ones (NonEmptyVector, NonEmptySet, NonEmptyMap and their sorted variants) implements Traversable<T>. It has what works the same way on every type: iterating, size, sizeCompare, contains, find, foldLeft, mkString, the conversions such as toVector and stream(), and the asJava() view.

map, filter and the rest are declared by each type, so they return that type.

Two more operations exist on most types:

partitionMap splits a collection in one pass, using a function that returns an Either. The sequences and the hash sets have it.
The static flatten removes one level of nesting.

var split = List.of(1, 2, 3, 4) // Tuple2<List<Integer>, List<String>>
    .partitionMap(n -> n % 2 == 0 ? Either.left(n) : Either.right("odd " + n));
var flat = Vector.flatten(Vector.of(Vector.of(1, 2), List.of(3))); // Vector<Integer>
// split is (List(2, 4), List(odd 1, odd 3)), flat is Vector(1, 2, 3)

var vector     = Vector.of(3, 1, 2);
var sortedList = vector.toList().sorted();  // List<Integer>
var set        = HashSet.ofAll(vector);     // HashSet<Integer>
var same       = Vector.of(1, 2, 3).equals(sortedList);
// List(1, 2, 3), a HashSet of 1, 2, 3, and true

A Vector, List, Queue or LazyList equals another of these four when they hold equal elements in the same order. Sets equal sets and maps equal maps. A NonEmptyVector equals only another NonEmptyVector; a non-empty set equals only a non-empty set, and a non-empty map only a non-empty map.

When nothing changes¶

A sequence operation that changes nothing returns the sequence itself, not a copy. Nothing is allocated, and result == original tells that nothing changed.

filter that keeps every element, remove or replace of an absent element.
take(n) with n at least the size, drop(0), a slice of the whole range, padTo below the size.
Appending, prepending or inserting an empty collection. An Iterable that can be read only once is never asked first, so it gives a copy. When the receiver is empty, appendAll and prependAll return the other side.
sorted, reverse and intersperse on fewer than two elements.
On a List or a Queue, update with the same instance as the element already there; an equal but distinct element is a change.
partition, span and splitAt return the receiver as the part that gets every element.

A List also shares what follows the last change: filter, update, span and splitAt copy only the elements before it. A filter that keeps every element is about three times faster than a copy, and one that removes an element near the front two to four and a half times.

A LazyList returns itself only when it can tell without reading an element, such as drop(0) or a patch that inserts and removes nothing. Each method's documentation says when it returns the receiver.

`mapConserve`¶

map builds a new collection. mapConserve maps the elements to elements of the same type, and returns the receiver itself when the function returns every element itself (==, not equals). Use it for a pass that usually changes nothing, such as rewriting a tree of immutable nodes.

var names     = List.of("ada", "Bob", "cy");
var same      = names.mapConserve(n -> n);                            // List<String>
var titled    = names.mapConserve(n -> n.equals("Bob") ? "BOB" : n);  // List<String>
var unchanged = same == names;                                        // boolean
// unchanged is true; titled is List(ada, BOB, cy) and shares the cell of "cy" with names

It is on Vector, NonEmptyVector, List, Queue and the sets. A List shares the elements after the last change, a Vector the parts that hold no changed element. A sorted set keeps its own order. LazyList has no mapConserve: it would have to evaluate every element to know that nothing changed.

Grouping¶

groupBy splits a collection into groups by a key. Two variants change the elements as they group them, in one pass:

groupMap(key, value) keeps what value returns for each element.
groupMapReduce(key, value, reduce) combines the values of each group into one, without building the groups.

The keys come in the order of their first element. The groups are of the collection's own type; a map groups its entries' values in a Vector, and a TreeSet in a HashSet, since the values may not be comparable. On a non-empty collection, the result is a NonEmptyMap.

var words   = List.of("apple", "bob", "avocado", "cherry", "banana");
var lengths = words.groupMap(w -> w.charAt(0), String::length);              // Map<Character, List<Integer>>
var counts  = words.groupMapReduce(w -> w.charAt(0), w -> 1, Integer::sum);  // Map<Character, Integer>
// lengths is LinkedHashMap((a, List(5, 7)), (b, List(3, 6)), (c, List(6)))
// counts is LinkedHashMap((a, 2), (b, 2), (c, 1))

Comparing sizes¶

sizeCompare(n) returns -1, 0 or 1 as a collection has fewer than, as many as, or more than n elements. It counts at most n + 1 of them. So it stays cheap on a List or a Queue, whose size() counts every element, and it returns on an infinite LazyList.

sizeCompare(other) compares with the size of another collection the same way: it counts no further than the shorter of the two.

var many     = List.range(0, 1_000_000);
var naturals = LazyList.from(1);
var big      = many.sizeCompare(3) > 0;                // boolean
var atLeast  = naturals.sizeCompare(10);               // int
var shorter  = Vector.of(1, 2).sizeCompare(naturals);  // int
// true, 1, -1

Sums, products and averages¶

The sequences, the sets, NonEmptyVector, NonEmptySet and NonEmptySortedSet add up, multiply and average the numbers a function reads from each element. The type of the function picks the arithmetic: sumInt, sumLong, sumDouble, and productInt, productLong, productDouble.

An int or long result is exact. When it does not fit, the method throws an ArithmeticException instead of wrapping around.
sumDouble and average add with compensation, so the rounding errors do not pile up over many elements.
An empty collection sums to 0 and multiplies to 1. average returns an Option, empty when there is no element; on the non-empty ones it returns the double itself.

var words   = List.of("one", "three", "five");
var letters = words.sumInt(String::length);                     // int
var mean    = words.average(String::length);                    // Option<Double>
var big     = Vector.of(Integer.MAX_VALUE, 1).sumLong(n -> n);  // long
// 12, Some(4.0), 2147483648

Nulls¶

No collection holds null: adding a null element, key or value throws a NullPointerException. Absence is an Option, which is what find, headOption and Map.get return.

var missing   = HashMap.of("a", 1).get("b");               // Option<Integer>
var firstEven = Vector.of(1, 3, 4).find(n -> n % 2 == 0);  // Option<Integer>
// None, Some(4)

A function that returns null where a collection needs an Option, a tuple or an iterable, such as the mapper of flatMap or the function of toMap, throws a NullPointerException naming the method: Vector.flatMap: mapper returned null. So do a groupBy classifier and the functions of groupMap and groupMapReduce (List.groupMap: value returned null). A function that returns a plain element, such as the mapper of map, is rejected like any other null element: Vector: element is null. A LazyList throws when it reaches that element.

Complexity¶

Each collection's page has a table of its common operations. Complexity puts all the collections side by side and lists every documented method.