0
# Collections
1

2
Comprehensive immutable collection library with persistent data structures including sequential collections, sets, maps, and specialized collections optimized for functional programming.
3

4
## Capabilities
5

6
### Base Collection Interfaces
7

8
Core interfaces that define the collection hierarchy and common operations.
9

10
```java { .api }
11
/**
12
 * Root interface for all traversable collections
13
 */
14
interface Traversable<T> extends Value<T> {
15
    // Factory methods
16
    static <T> Traversable<T> empty();
17
    static <T> Traversable<T> of(T... elements);
18
    
19
    // Basic operations
20
    int size();
21
    boolean isEmpty();
22
    boolean contains(T element);
23
    
24
    // Transformation operations
25
    <U> Traversable<U> map(Function<? super T, ? extends U> mapper);
26
    Traversable<T> filter(Predicate<? super T> predicate);
27
    <U> U foldLeft(U zero, BiFunction<? super U, ? super T, ? extends U> combine);
28
    <U> U foldRight(U zero, BiFunction<? super T, ? super U, ? extends U> combine);
29
    
30
    // Terminal operations
31
    String mkString();
32
    String mkString(String delimiter);
33
    String mkString(String prefix, String delimiter, String suffix);
34
}
35

36
/**
37
 * Base interface for sequential collections
38
 */
39
interface Seq<T> extends Traversable<T> {
40
    // Access operations
41
    T get(int index);
42
    int indexOf(T element);
43
    int lastIndexOf(T element);
44
    
45
    // Transformation operations
46
    Seq<T> append(T element);
47
    Seq<T> prepend(T element);
48
    Seq<T> insert(int index, T element);
49
    Seq<T> remove(T element);
50
    Seq<T> removeAt(int index);
51
    
52
    // Subsequence operations
53
    Seq<T> slice(int beginIndex, int endIndex);
54
    Seq<T> take(int n);
55
    Seq<T> drop(int n);
56
    Seq<T> reverse();
57
    
58
    // Grouping operations
59
    <K> Map<K, ? extends Seq<T>> groupBy(Function<? super T, ? extends K> classifier);
60
}
61

62
/**
63
 * Interface for indexed sequential collections with O(1) random access
64
 */
65
interface IndexedSeq<T> extends Seq<T> {
66
    // Override for performance
67
    T get(int index); // O(1) access
68
}
69

70
/**
71
 * Interface for linear sequential collections with O(1) head/tail access
72
 */
73
interface LinearSeq<T> extends Seq<T> {
74
    T head();
75
    LinearSeq<T> tail();
76
    boolean isEmpty();
77
}
78
```
79

80
### List - Immutable Linked List
81

82
Immutable singly-linked list implementation optimized for prepend operations and sequential access.
83

84
```java { .api }
85
/**
86
 * Immutable singly-linked list (LIFO stack)
87
 */
88
interface List<T> extends LinearSeq<T> {
89
    // Factory methods
90
    static <T> List<T> empty();
91
    static <T> List<T> of();
92
    static <T> List<T> of(T element);
93
    static <T> List<T> of(T... elements);
94
    static <T> List<T> ofAll(Iterable<? extends T> elements);
95
    static <T> List<T> fill(int n, T element);
96
    static <T> List<T> fill(int n, Supplier<? extends T> supplier);
97
    static List<Integer> range(int from, int toExclusive);
98
    static List<Integer> rangeClosed(int from, int toInclusive);
99
    
100
    // Stack operations (O(1))
101
    T head();                                    // Get first element
102
    List<T> tail();                             // Get all but first element
103
    List<T> prepend(T element);                 // Add to front
104
    static <T> List<T> cons(T head, List<T> tail); // Construct from head and tail
105
    
106
    // List operations
107
    List<T> append(T element);                  // Add to end (O(n))
108
    List<T> appendAll(Iterable<? extends T> elements);
109
    List<T> prependAll(Iterable<? extends T> elements);
110
    
111
    // Transformation operations (return new List)
112
    <U> List<U> map(Function<? super T, ? extends U> mapper);
113
    List<T> filter(Predicate<? super T> predicate);
114
    <U> List<U> flatMap(Function<? super T, ? extends Iterable<? extends U>> mapper);
115
    List<T> distinct();
116
    List<T> sorted();
117
    List<T> sorted(Comparator<? super T> comparator);
118
    
119
    // Combining operations
120
    List<T> removeFirst(Predicate<? super T> predicate);
121
    List<T> removeLast(Predicate<? super T> predicate);
122
    List<T> removeAll(T element);
123
    List<T> replace(T currentElement, T newElement);
124
    List<T> replaceAll(T currentElement, T newElement);
125
    
126
    // Zipping operations
127
    <U> List<Tuple2<T, U>> zip(Iterable<? extends U> that);
128
    <U, R> List<R> zipWith(Iterable<? extends U> that, BiFunction<? super T, ? super U, ? extends R> mapper);
129
    List<Tuple2<T, Integer>> zipWithIndex();
130
}
131
```
132

133
**Usage Examples:**
134

135
```java
136
import io.vavr.collection.List;
137

138
// Creating lists
139
List<Integer> empty = List.empty();
140
List<Integer> numbers = List.of(1, 2, 3, 4, 5);
141
List<String> names = List.of("Alice", "Bob", "Charlie");
142

143
// Stack operations (efficient)
144
List<Integer> withZero = numbers.prepend(0);  // [0, 1, 2, 3, 4, 5]
145
Integer first = numbers.head();               // 1
146
List<Integer> rest = numbers.tail();          // [2, 3, 4, 5]
147

148
// Functional operations
149
List<Integer> doubled = numbers.map(x -> x * 2);
150
List<Integer> evens = numbers.filter(x -> x % 2 == 0);
151
List<String> words = List.of("hello", "world").map(String::toUpperCase);
152

153
// Combining lists
154
List<Integer> extended = numbers.append(6).appendAll(List.of(7, 8, 9));
155
List<Integer> combined = List.of(0).appendAll(numbers);
156

157
// Pattern matching on lists
158
String describe(List<Integer> list) {
159
    return list.isEmpty() ? "empty" : 
160
           list.tail().isEmpty() ? "single: " + list.head() :
161
           "multiple starting with " + list.head();
162
}
163
```
164

165
### Vector - Immutable Indexed Sequence
166

167
High-performance immutable indexed sequence with efficient random access and updates.
168

169
```java { .api }
170
/**
171
 * Immutable indexed sequence with O(log n) access and updates
172
 */
173
class Vector<T> implements IndexedSeq<T> {
174
    // Factory methods
175
    static <T> Vector<T> empty();
176
    static <T> Vector<T> of(T... elements);
177
    static <T> Vector<T> ofAll(Iterable<? extends T> elements);
178
    static <T> Vector<T> fill(int n, T element);
179
    static Vector<Integer> range(int from, int toExclusive);
180
    
181
    // Indexed access (O(log n))
182
    T get(int index);
183
    Vector<T> update(int index, T element);
184
    
185
    // Modification operations (O(log n))
186
    Vector<T> append(T element);
187
    Vector<T> prepend(T element);
188
    Vector<T> insert(int index, T element);
189
    Vector<T> removeAt(int index);
190
    
191
    // Transformation operations
192
    <U> Vector<U> map(Function<? super T, ? extends U> mapper);
193
    Vector<T> filter(Predicate<? super T> predicate);
194
    Vector<T> sorted();
195
    Vector<T> sorted(Comparator<? super T> comparator);
196
    
197
    // Subsequence operations
198
    Vector<T> slice(int beginIndex, int endIndex);
199
    Vector<T> take(int n);
200
    Vector<T> drop(int n);
201
    Vector<T> reverse();
202
}
203
```
204

205
### Array - Immutable Array Wrapper
206

207
Immutable wrapper around Java arrays providing indexed access with functional programming operations.
208

209
```java { .api }
210
/**
211
 * Immutable wrapper for Object[] with O(1) indexed access
212
 */
213
class Array<T> implements IndexedSeq<T> {
214
    // Factory methods
215
    static <T> Array<T> empty();
216
    static <T> Array<T> of(T... elements);
217
    static <T> Array<T> ofAll(Iterable<? extends T> elements);
218
    static <T> Array<T> ofAll(java.util.stream.Stream<? extends T> javaStream);
219
    static <T> Array<T> fill(int n, T element);
220
    static <T> Array<T> fill(int n, Supplier<? extends T> supplier);
221
    static Array<Integer> range(int from, int toExclusive);
222
    static Array<Integer> rangeClosed(int from, int toInclusive);
223
    
224
    // Indexed access (O(1))
225
    T get(int index);                           // Direct array access
226
    Array<T> update(int index, T element);      // Create new array with updated element
227
    
228
    // Modification operations (create new array)
229
    Array<T> append(T element);
230
    Array<T> appendAll(Iterable<? extends T> elements);
231
    Array<T> prepend(T element);
232
    Array<T> prependAll(Iterable<? extends T> elements);
233
    Array<T> insert(int index, T element);
234
    Array<T> insertAll(int index, Iterable<? extends T> elements);
235
    Array<T> remove(T element);
236
    Array<T> removeAt(int index);
237
    Array<T> removeAll(Iterable<? extends T> elements);
238
    
239
    // Transformation operations
240
    <U> Array<U> map(Function<? super T, ? extends U> mapper);
241
    Array<T> filter(Predicate<? super T> predicate);
242
    <U> Array<U> flatMap(Function<? super T, ? extends Iterable<? extends U>> mapper);
243
    Array<T> distinct();
244
    Array<T> distinctBy(Comparator<? super T> comparator);
245
    Array<T> sorted();
246
    Array<T> sorted(Comparator<? super T> comparator);
247
    
248
    // Subsequence operations
249
    Array<T> slice(int beginIndex, int endIndex);
250
    Array<T> take(int n);
251
    Array<T> drop(int n);
252
    Array<T> takeWhile(Predicate<? super T> predicate);
253
    Array<T> dropWhile(Predicate<? super T> predicate);
254
    Array<T> reverse();
255
    
256
    // Conversion operations
257
    Object[] toJavaArray();                     // Direct array access
258
    T[] toJavaArray(Class<T> componentType);    // Typed array conversion
259
    java.util.List<T> toJavaList();
260
    
261
    // Zipping operations
262
    <U> Array<Tuple2<T, U>> zip(Iterable<? extends U> that);
263
    <U, R> Array<R> zipWith(Iterable<? extends U> that, BiFunction<? super T, ? super U, ? extends R> mapper);
264
    Array<Tuple2<T, Integer>> zipWithIndex();
265
}
266
```
267

268
**Usage Examples:**
269

270
```java
271
import io.vavr.collection.Array;
272

273
// Creating arrays
274
Array<Integer> empty = Array.empty();
275
Array<Integer> numbers = Array.of(1, 2, 3, 4, 5);
276
Array<String> words = Array.of("hello", "world", "vavr");
277

278
// O(1) indexed access (advantage over List)
279
Integer third = numbers.get(2);                // 3 (no traversal needed)
280
Array<Integer> updated = numbers.update(1, 10); // [1, 10, 3, 4, 5]
281

282
// Functional operations
283
Array<Integer> doubled = numbers.map(x -> x * 2);
284
Array<Integer> evens = numbers.filter(x -> x % 2 == 0);
285
Array<String> lengths = words.map(w -> "Length: " + w.length());
286

287
// Array-specific operations
288
Array<Integer> range = Array.range(1, 6);      // [1, 2, 3, 4, 5]
289
Array<String> filled = Array.fill(3, "test");  // ["test", "test", "test"]
290

291
// Efficient bulk operations
292
Array<Integer> extended = numbers.appendAll(Array.of(6, 7, 8));
293
Array<Integer> combined = Array.of(0).prependAll(numbers);
294

295
// Direct conversion to Java arrays (efficient)
296
Integer[] javaArray = numbers.toJavaArray(Integer.class);
297
Object[] objectArray = numbers.toJavaArray();
298

299
// Sorting (creates new array)
300
Array<String> sorted = words.sorted();
301
Array<Integer> descending = numbers.sorted((a, b) -> b.compareTo(a));
302

303
// Memory-efficient operations
304
Array<Integer> slice = numbers.slice(1, 4);    // [2, 3, 4]
305
Array<Integer> first3 = numbers.take(3);       // [1, 2, 3]
306
Array<Integer> skip2 = numbers.drop(2);        // [3, 4, 5]
307

308
// Pattern matching style operations
309
String describe = numbers.isEmpty() ? "empty" :
310
                 numbers.size() == 1 ? "single" : 
311
                 "array of " + numbers.size() + " elements";
312
```
313

314
Array is particularly useful when you need:
315
- **O(1) indexed access** (unlike List which is O(n))
316
- **Efficient conversion** to/from Java arrays
317
- **Memory efficiency** for large datasets
318
- **Bulk operations** on array-like data structures
319

320
### HashMap - Immutable Hash Map
321

322
Hash-based immutable map implementation with efficient key-value operations.
323

324
```java { .api }
325
/**
326
 * Immutable hash-based map with O(1) expected time operations
327
 */
328
class HashMap<K, V> implements Map<K, V> {
329
    // Factory methods
330
    static <K, V> HashMap<K, V> empty();
331
    static <K, V> HashMap<K, V> of(K key, V value);
332
    static <K, V> HashMap<K, V> of(K k1, V v1, K k2, V v2);
333
    // ... up to 10 key-value pairs
334
    static <K, V> HashMap<K, V> ofEntries(Tuple2<? extends K, ? extends V>... entries);
335
    static <K, V> HashMap<K, V> ofEntries(Iterable<? extends Tuple2<? extends K, ? extends V>> entries);
336
    
337
    // Map operations
338
    Option<V> get(K key);                       // Get value for key
339
    V getOrElse(K key, V defaultValue);        // Get value or default
340
    boolean containsKey(K key);                 // Check if key exists
341
    boolean containsValue(V value);             // Check if value exists
342
    
343
    // Modification operations (return new HashMap)
344
    HashMap<K, V> put(K key, V value);         // Add/update key-value pair
345
    HashMap<K, V> put(Tuple2<? extends K, ? extends V> entry);
346
    HashMap<K, V> putAll(Iterable<? extends Tuple2<? extends K, ? extends V>> entries);
347
    HashMap<K, V> remove(K key);               // Remove key-value pair
348
    HashMap<K, V> removeAll(Iterable<? extends K> keys);
349
    
350
    // Transformation operations
351
    <K2, V2> HashMap<K2, V2> map(BiFunction<? super K, ? super V, Tuple2<K2, V2>> mapper);
352
    <V2> HashMap<K, V2> mapValues(Function<? super V, ? extends V2> mapper);
353
    HashMap<K, V> filter(BiPredicate<? super K, ? super V> predicate);
354
    HashMap<K, V> filterKeys(Predicate<? super K> predicate);
355
    HashMap<K, V> filterValues(Predicate<? super V> predicate);
356
    
357
    // Collection views
358
    Set<K> keySet();                           // Get all keys
359
    Traversable<V> values();                   // Get all values
360
    Set<Tuple2<K, V>> entrySet();             // Get all key-value pairs
361
    
362
    // Merging operations
363
    HashMap<K, V> merge(Map<? extends K, ? extends V> that);
364
    <U, R> HashMap<K, R> merge(Map<? extends K, ? extends U> that, 
365
                               BiFunction<? super V, ? super U, ? extends R> collisionResolution);
366
}
367
```
368

369
**Usage Examples:**
370

371
```java
372
import io.vavr.collection.HashMap;
373
import io.vavr.collection.Map;
374
import io.vavr.Tuple;
375

376
// Creating maps
377
Map<String, Integer> scores = HashMap.of(
378
    "Alice", 95,
379
    "Bob", 87,
380
    "Charlie", 92
381
);
382

383
// Map operations
384
Integer aliceScore = scores.get("Alice").getOrElse(0);
385
boolean hasAlice = scores.containsKey("Alice");
386

387
// Adding/updating entries
388
Map<String, Integer> updated = scores.put("David", 89);
389
Map<String, Integer> incremented = scores.mapValues(score -> score + 5);
390

391
// Filtering
392
Map<String, Integer> highScores = scores.filter((name, score) -> score > 90);
393
Map<String, Integer> aNames = scores.filterKeys(name -> name.startsWith("A"));
394

395
// Working with entries
396
scores.forEach((name, score) -> 
397
    System.out.println(name + ": " + score));
398

399
// Converting between representations
400
java.util.Map<String, Integer> javaMap = scores.toJavaMap();
401
```
402

403
### HashSet - Immutable Hash Set
404

405
Hash-based immutable set implementation with efficient membership testing and set operations.
406

407
```java { .api }
408
/**
409
 * Immutable hash-based set with O(1) expected time operations
410
 */
411
class HashSet<T> implements Set<T> {
412
    // Factory methods
413
    static <T> HashSet<T> empty();
414
    static <T> HashSet<T> of(T element);
415
    static <T> HashSet<T> of(T... elements);
416
    static <T> HashSet<T> ofAll(Iterable<? extends T> elements);
417
    
418
    // Set operations
419
    boolean contains(T element);                // Test membership
420
    HashSet<T> add(T element);                 // Add element
421
    HashSet<T> addAll(Iterable<? extends T> elements);
422
    HashSet<T> remove(T element);              // Remove element
423
    HashSet<T> removeAll(Iterable<? extends T> elements);
424
    
425
    // Set algebra operations
426
    HashSet<T> union(Set<? extends T> that);          // Union (A ∪ B)
427
    HashSet<T> intersect(Set<? extends T> that);      // Intersection (A ∩ B)  
428
    HashSet<T> diff(Set<? extends T> that);           // Difference (A - B)
429
    
430
    // Transformation operations
431
    <U> HashSet<U> map(Function<? super T, ? extends U> mapper);
432
    HashSet<T> filter(Predicate<? super T> predicate);
433
    <U> HashSet<U> flatMap(Function<? super T, ? extends Iterable<? extends U>> mapper);
434
    
435
    // Subset operations
436
    boolean isSubsetOf(Set<? extends T> that);
437
    boolean isProperSubsetOf(Set<? extends T> that);
438
}
439
```
440

441
### Stream - Lazy Infinite Sequence
442

443
Lazy evaluation sequence that can represent infinite collections with on-demand computation.
444

445
```java { .api }
446
/**
447
 * Lazy infinite sequence with on-demand evaluation
448
 */
449
class Stream<T> implements LinearSeq<T> {
450
    // Factory methods  
451
    static <T> Stream<T> empty();
452
    static <T> Stream<T> of(T... elements);
453
    static <T> Stream<T> ofAll(Iterable<? extends T> elements);
454
    static <T> Stream<T> continually(T element);              // Infinite constant stream
455
    static <T> Stream<T> continually(Supplier<? extends T> supplier); // Infinite generated stream
456
    static <T> Stream<T> iterate(T seed, Function<? super T, ? extends T> f); // Infinite iteration
457
    static Stream<Integer> from(int start);                   // Infinite arithmetic progression
458
    static Stream<Integer> range(int from, int toExclusive);  // Finite range
459
    
460
    // Stream operations (lazy)
461
    T head();                                  // First element (evaluated)
462
    Stream<T> tail();                         // Rest of stream (lazy)
463
    boolean isEmpty();                         // Check if stream is empty
464
    
465
    // Transformation operations (lazy)
466
    <U> Stream<U> map(Function<? super T, ? extends U> mapper);
467
    Stream<T> filter(Predicate<? super T> predicate);
468
    <U> Stream<U> flatMap(Function<? super T, ? extends Iterable<? extends U>> mapper);
469
    Stream<T> distinct();
470
    
471
    // Limiting operations (finite results)
472
    Stream<T> take(int n);                    // Take first n elements
473
    Stream<T> takeWhile(Predicate<? super T> predicate); // Take while condition holds
474
    Stream<T> drop(int n);                    // Skip first n elements  
475
    Stream<T> dropWhile(Predicate<? super T> predicate); // Skip while condition holds
476
    
477
    // Terminal operations (force evaluation)
478
    List<T> toList();                         // Convert to List (forces evaluation)
479
    Vector<T> toVector();                     // Convert to Vector
480
    T reduce(BinaryOperator<T> op);          // Reduce to single value
481
    <U> U foldLeft(U zero, BiFunction<? super U, ? super T, ? extends U> combine);
482
    
483
    // Zipping operations
484
    <U> Stream<Tuple2<T, U>> zip(Iterable<? extends U> that);
485
    Stream<Tuple2<T, Integer>> zipWithIndex();
486
}
487
```
488

489
**Usage Examples:**
490

491
```java
492
import io.vavr.collection.Stream;
493
import io.vavr.collection.List;
494

495
// Infinite streams
496
Stream<Integer> naturals = Stream.from(1);           // 1, 2, 3, 4, ...
497
Stream<Integer> evens = naturals.filter(x -> x % 2 == 0); // 2, 4, 6, 8, ...
498
Stream<Integer> powers = Stream.iterate(1, x -> x * 2);   // 1, 2, 4, 8, 16, ...
499

500
// Taking finite portions
501
List<Integer> first10Evens = evens.take(10).toList();
502
List<Integer> powersUpTo1000 = powers.takeWhile(x -> x <= 1000).toList();
503

504
// Lazy evaluation demonstration
505
Stream<String> expensive = Stream.continually(() -> {
506
    System.out.println("Computing...");
507
    return "expensive";
508
});
509

510
// Nothing printed yet - computation is lazy
511
Stream<String> transformed = expensive.map(String::toUpperCase);
512

513
// Still nothing printed - still lazy
514
String first = transformed.head(); // Now prints "Computing..." once
515

516
// Fibonacci sequence example
517
Stream<Integer> fibonacci = Stream.of(1, 1)
518
    .appendSelf(self -> self.zip(self.tail()).map(t -> t._1() + t._2()));
519
List<Integer> first10Fib = fibonacci.take(10).toList(); // [1,1,2,3,5,8,13,21,34,55]
520
```
521

522
### Specialized Collections
523

524
Additional collection types for specific use cases.
525

526
```java { .api }
527
/**
528
 * Character sequence with string-like operations
529
 */
530
class CharSeq implements IndexedSeq<Character> {
531
    static CharSeq empty();
532
    static CharSeq of(String string);
533
    static CharSeq of(char... chars);
534
    
535
    // String-like operations
536
    char charAt(int index);
537
    CharSeq substring(int beginIndex);
538
    CharSeq substring(int beginIndex, int endIndex);
539
    List<CharSeq> split(String delimiter);
540
    CharSeq replace(char oldChar, char newChar);
541
    CharSeq toLowerCase();
542
    CharSeq toUpperCase();
543
    CharSeq trim();
544
    
545
    // Conversion
546
    String mkString();
547
    char[] toCharArray();
548
}
549

550
/**
551
 * FIFO queue interface
552
 */
553
interface Queue<T> extends Traversable<T> {
554
    static <T> Queue<T> empty();
555
    static <T> Queue<T> of(T... elements);
556
    
557
    T peek();                           // Get front element without removing
558
    Option<T> peekOption();            // Safe peek operation
559
    Queue<T> enqueue(T element);       // Add to rear
560
    Tuple2<T, Queue<T>> dequeue();     // Remove from front, return element and new queue
561
    Option<Tuple2<T, Queue<T>>> dequeueOption(); // Safe dequeue operation
562
}
563

564
/**
565
 * Priority queue with heap-based implementation
566
 */
567
class PriorityQueue<T> implements Queue<T> {
568
    static <T extends Comparable<? super T>> PriorityQueue<T> empty();
569
    static <T> PriorityQueue<T> empty(Comparator<? super T> comparator);
570
    static <T extends Comparable<? super T>> PriorityQueue<T> of(T... elements);
571
    
572
    // Priority queue specific operations
573
    T peek();                          // Get highest priority element
574
    PriorityQueue<T> enqueue(T element); // Add element maintaining heap property
575
    Tuple2<T, PriorityQueue<T>> dequeue(); // Remove highest priority element
576
    
577
    // Merge operation
578
    PriorityQueue<T> merge(PriorityQueue<T> that);
579
}
580

581
/**
582
 * Compact set for non-negative integers
583
 */
584
class BitSet implements SortedSet<Integer> {
585
    static BitSet empty();
586
    static BitSet of(int... ints);
587
    static BitSet ofAll(Iterable<Integer> ints);
588
    
589
    // BitSet specific operations
590
    BitSet add(int value);             // Add integer to set
591
    BitSet remove(int value);          // Remove integer from set
592
    BitSet union(BitSet that);         // Bitwise OR
593
    BitSet intersect(BitSet that);     // Bitwise AND
594
    BitSet complement();               // Bitwise NOT (finite range)
595
    
596
    // Range operations
597
    static BitSet range(int from, int toExclusive);
598
    int min();                         // Smallest element
599
    int max();                         // Largest element
600
}
601
```