Chapter 6: Collections

Beyond Single Values

You've been working with individual values and structs. But programs need to work with groups of things: a list of users, a set of tags, a mapping from names to ages. Collections are how you handle multiple values.

Wyn gives you three collection types:

• Arrays: Ordered sequences
• HashMaps: Key-value pairs
• HashSets: Unique values

Each has different performance characteristics and use cases. Choose the right one and your code will be fast and clear. Choose the wrong one and you'll fight the language.

Arrays: Ordered Sequences

Arrays store multiple values of the same type in order:

fn main() -> int {
    var numbers = [1, 2, 3, 4, 5]
    var names = ["Alice", "Bob", "Charlie"]
    var empty = []
    
    return 0
}

Access elements by index (zero-based):

fn main() -> int {
    var numbers = [10, 20, 30, 40, 50]
    
    print(numbers[0])  // 10 - first element
    print(numbers[2])  // 30 - third element
    print(numbers[4])  // 50 - last element
    
    return 0
}

Modify elements:

fn main() -> int {
    var numbers = [1, 2, 3]
    numbers[0] = 10
    numbers[1] = 20
    
    print(numbers[0])  // 10
    return 0
}

Array Methods

Arrays are objects with methods:

fn main() -> int {
    var numbers = [1, 2, 3, 4, 5]
    
    print(numbers.len())  // 5 - length
    
    numbers.push(6)       // Add to end
    print(numbers.len())  // 6
    
    print(numbers.contains(3))   // true
    print(numbers.contains(10))  // false
    
    return 0
}

The len() method is O(1)-constant time. The array knows its length.

The contains() method is O(n)-it checks every element. For small arrays, that's fine. For large ones, use a HashSet instead.

Higher-Order Array Methods

Arrays support functional programming operations:

fn main() -> int {
    var numbers = [1, 2, 3, 4, 5]
    
    // Map: transform each element
    var doubled = numbers.map((x) => x * 2)
    // [2, 4, 6, 8, 10]
    
    // Filter: keep matching elements
    var evens = numbers.filter((x) => x % 2 == 0)
    // [2, 4]
    
    // Reduce: combine into single value
    var sum = numbers.reduce((acc, x) => acc + x, 0)
    // 15
    
    return 0
}

These are powerful but can be slower than explicit loops. Use them when clarity matters more than the last bit of performance.

HashMaps: Key-Value Pairs

HashMaps store associations between keys and values. Need to look up a user by ID? A configuration value by name? A word count by word? Use a HashMap.

fn main() -> int {
    var ages = {"Alice": 25, "Bob": 30, "Charlie": 35}
    
    print(ages["Alice"])  // 25
    print(ages["Bob"])    // 30
    
    return 0
}

The literal syntax is {key: value, key: value}. Keys must be unique. Values can be anything.

Adding and Updating

Use indexing to add or update entries:

fn main() -> int {
    var scores = {"Alice": 95}
    
    scores["Bob"] = 87      // Add new entry
    scores["Alice"] = 98    // Update existing
    
    print(scores["Alice"])  // 98
    print(scores["Bob"])    // 87
    
    return 0
}

HashMap Methods

fn main() -> int {
    var map = {"a": 1, "b": 2, "c": 3}
    
    print(map.has("a"))  // true - check if key exists
    print(map.has("z"))  // false
    
    print(map.len())     // 3 - number of entries
    
    map.remove("b")      // Remove entry
    print(map.len())     // 2
    
    return 0
}

Always check if a key exists before accessing it. Accessing a non-existent key is undefined behavior.

When to Use HashMaps

Use HashMaps when:

• You need fast lookups by key (O(1) average)
• Keys are unique
• Order doesn't matter
• You're building associations (name → value, ID → object)

Don't use HashMaps when:

• You need ordered iteration
• You're just storing a list of values
• Keys aren't unique

HashSets: Unique Values

HashSets store unique values with fast membership testing. Need to track which users have logged in? Which pages have been visited? Which tags are active? Use a HashSet.

fn main() -> int {
    var tags = {:"rust", "systems", "programming"}
    
    print(tags.contains("rust"))     // true
    print(tags.contains("python"))   // false
    
    return 0
}

The literal syntax is {:value, value}. The : distinguishes it from a HashMap.

HashSet Methods

fn main() -> int {
    var set = {:"a", "b", "c"}
    
    set.insert("d")      // Add element
    print(set.len())     // 4
    
    set.remove("b")      // Remove element
    print(set.len())     // 3
    
    print(set.contains("a"))  // true
    
    return 0
}

Duplicates are automatically ignored:

fn main() -> int {
    var set = {:"a", "b"}
    set.insert("a")  // Already exists, no effect
    print(set.len())  // Still 2
    return 0
}

When to Use HashSets

Use HashSets when:

• You need unique values
• You test membership frequently (O(1) average)
• Order doesn't matter
• You're tracking presence (visited pages, active users)

Don't use HashSets when:

• You need duplicates
• You need ordered iteration
• You need to associate keys with values (use HashMap)

Choosing the Right Collection

This matters. The wrong choice makes your code slow or awkward.

Use Arrays when:

• You need ordered elements
• You access by index
• You iterate sequentially
• Order matters

var scores = [95, 87, 92, 88]  // Test scores in order
var names = ["Alice", "Bob", "Charlie"]  // Ordered list

Use HashMaps when:

• You need key-value associations
• You look up by key
• Order doesn't matter
• Keys are unique

var ages = {"Alice": 25, "Bob": 30}  // Name → age
var config = {"host": "localhost", "port": 8080}  // Config values

Use HashSets when:

• You need unique values
• You test membership frequently
• Order doesn't matter
• No duplicates allowed

var visited = {:"page1", "page2"}  // Unique visited pages
var tags = {:"rust", "systems"}    // Unique tags

Performance Characteristics

Understanding performance helps you choose correctly:

Arrays:

• Access by index: O(1)
• Append: O(1) amortized
• Search: O(n)
• Insert/delete in middle: O(n)

HashMaps:

• Lookup: O(1) average
• Insert: O(1) average
• Delete: O(1) average
• Memory overhead: Higher than arrays

HashSets:

• Membership test: O(1) average
• Insert: O(1) average
• Delete: O(1) average
• Memory overhead: Similar to HashMap

The "average" qualifier matters. Hash collisions can degrade to O(n), but this is rare with good hash functions.

Common Patterns

Counting with HashMap

fn main() -> int {
    var words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
    var counts = {}
    
    for (var i = 0; i < words.len(); i = i + 1) {
        var word = words[i]
        if (counts.has(word)) {
            counts[word] = counts[word] + 1
        } else {
            counts[word] = 1
        }
    }
    
    print(counts["apple"])   // 3
    print(counts["banana"])  // 2
    
    return 0
}

This is the word count pattern. You'll use it constantly.

Removing Duplicates with HashSet

fn main() -> int {
    var tags = ["red", "blue", "red", "green", "blue", "red"]
    var unique = {:}
    
    for (var i = 0; i < tags.len(); i = i + 1) {
        unique.add(tags[i])
    }
    
    print(unique.len())  // 3 - only unique values
    
    return 0
}

Caching with HashMap

var cache = {}

fn expensive_computation(n: int) -> int {
    var key = n.to_string()
    if (cache.has(key)) {
        return cache[key]  // Return cached result
    }
    
    // Perform expensive computation
    var result = n * n
    cache[key] = result
    
    return result
}

fn main() -> int {
    print(expensive_computation(5))  // Computes: 25
    print(expensive_computation(5))  // Uses cache: 25
    return 0
}

This is memoization. It trades memory for speed.

What You've Learned

Collections let you work with multiple values. Arrays for ordered sequences, HashMaps for key-value pairs, HashSets for unique values.

Choose based on your access patterns. Need order? Array. Need fast lookup? HashMap. Need uniqueness? HashSet.

Performance characteristics matter. Arrays are O(1) for index access but O(n) for search. HashMaps and HashSets are O(1) average for most operations.

Common patterns-counting, deduplication, caching-appear everywhere. Learn them once, use them forever.

Exercises

1. Sum and average: Create an array of numbers, calculate their sum and average.

2. Phone book: Build a HashMap mapping names to phone numbers. Add entries, look them up, remove them.

3. Unique words: Given a sentence as a string, split it into words and use a HashSet to find unique words.

4. Most frequent: Write a function that finds the most frequent element in an array using a HashMap.

5. Intersection: Given two arrays, find elements that appear in both. Use a HashSet for efficiency.

6. Cache implementation: Implement a simple cache using a HashMap. Add a size limit-when the cache is full, remove the oldest entry.

7. Performance test: Create a large array (10,000 elements). Time how long it takes to search for an element. Now put the same elements in a HashSet and time the search. See the difference.

---

Next: Chapter 7: Error Handling