# 4. Collections

> Chapter 4: arrays, lists, hashes with defaults, ranges, tuples and named tuples, blocks and iterators, and why Alice pipelines are fast.

Canonical: https://alice-lang.org/documentation/learn/collections/

[Documentation index](https://alice-lang.org/documentation/llms.txt) · [Complete book](https://alice-lang.org/llms-full.txt)

A tea shop has many teas, many orders and many customers. Programs need to keep many values together, walk through them, and ask questions about them: how many, which ones, what total. This chapter introduces the collections you will use every day, and the blocks that work on them.

## 4.1 Arrays

An array is a numbered row of values of one type. Write it with square brackets:

```alice
prices = [250, 300, 175]
puts prices[0]
puts prices.last
puts prices.size
puts prices
```

```text title="Output"
250
175
3
[250, 300, 175]
```

Positions start at 0, and `last` is the final element. The type of `prices` is `Array(Int32)`.

An index outside the array is a runtime error. Alice checks every access, so a wrong index cannot read some other memory. Unlike Ruby, a negative index is outside the array too:

```alice
prices = [250, 300, 175]
puts prices[-1]
```

```text title="Runtime error"
IndexOutOfRangeException: Index was outside the bounds of the array.
```

### Arrays have a fixed size

Here Alice differs from Ruby. An `Array(T)` is a .NET array: its size is fixed when it is made. You can change its elements, but you cannot add one:

```alice fail="AL0305"
prices = [250, 300, 175]
prices << 400
```

```text title="Error"
error[AL0305]
expected List(Int32), got Array(Int32)
```

Why? Fixed-size arrays are the fastest structure a computer has: one block of memory, no bookkeeping. Most of the speed features in this book, such as SIMD, parallel loops and pooled buffers, work on arrays. So Alice keeps arrays simple, and gives growing a separate type.

To make an array of a given size, say what goes in each slot:

```alice
zeros = Array(Int32).new(4, 0)
squares = Array(Int32).new(5) { |i| i * i }
puts zeros
puts squares
```

```text title="Output"
[0, 0, 0, 0]
[0, 1, 4, 9, 16]
```

## 4.2 Lists grow

When you do not know the size in advance, use a `List(T)`. It grows as you add to it:

```alice
orders = List(String).new
orders << "Assam"
orders << "Earl Grey" << "Sencha"
puts orders.size
puts orders[1]
orders.RemoveAt(0)
puts orders
```

```text title="Output"
3
Earl Grey
["Earl Grey", "Sencha"]
```

`<<` appends and can be chained. `List(T)` is the .NET `List<T>`, so all of its methods work under their .NET names, like `RemoveAt`. The empty literal `[] of String` also makes a list.

Which one should you use? Use an **array** when the size is known, or once you are done building. Use a **list** while you collect. `to_a` turns a list into an array.

### Two names, one array

Assigning an array or a list to another variable does not copy it. Both names then refer to the same collection:

```alice
a = [1, 2, 3]
b = a
b[0] = 100
puts a[0]
c = a.dup
c[0] = 7
puts a[0]
```

```text title="Output"
100
100
```

`dup` makes a copy. This sharing is normal in Ruby, Python and C#. It becomes important when two threads share an array, and [chapter 10](https://alice-lang.org/documentation/learn/safety.md) shows how the compiler watches for that.

## 4.3 Hashes

A hash maps **keys** to **values**: tea names to prices, words to counts, ids to customers. Write it with `=>`:

```alice
menu = {"Assam" => 250, "Earl Grey" => 300}
menu["Sencha"] = 350
puts menu["Earl Grey"]
puts menu.size
puts menu.key?("Oolong")
menu.each { |name, cents| puts "#{name}: #{cents}" }
```

```text title="Output"
300
3
false
Assam: 250
Earl Grey: 300
Sencha: 350
```

A hash remembers the order in which keys were added, and `each` gives the block both the key and the value. The type is `Hash(String, Int32)`, which is the .NET `Dictionary<String, Int32>`.

### A missing key is an error

In Ruby, `menu["Oolong"]` returns `nil`. In Alice it raises `KeyNotFoundException`:

```alice
menu = {"Assam" => 250}
puts menu["Oolong"]
```

```text title="Runtime error"
KeyNotFoundException: The given key 'Oolong' was not present in the dictionary.
```

That is deliberate. If a missing key silently gave `nil`, every lookup would have the type `Int32?`, and every use would need a check. Instead, you say what you want when the key might be missing:

```alice
menu = {"Assam" => 250}
puts menu.fetch("Oolong", 0)
puts menu.key?("Oolong") ? "on the menu" : "not on the menu"
```

```text title="Output"
0
not on the menu
```

### Hashes with a default

Counting is so common that hashes have a shortcut. `Hash(K, V).new(default)` makes a hash where every missing key reads as `default`:

```alice
sold = ["Assam", "Sencha", "Assam", "Earl Grey", "Assam"]
counts = Hash(String, Int32).new(0)
sold.each { |tea| counts[tea] += 1 }
puts counts
puts counts["Oolong"]
```

```text title="Output"
{"Assam" => 3, "Sencha" => 1, "Earl Grey" => 1}
0
```

`counts[tea] += 1` reads the old count, which is 0 the first time, and stores the new one. Reading `counts["Oolong"]` gives the default but does not store it. For this exact job there is also `tally`:

```alice
puts ["Assam", "Sencha", "Assam"].tally
```

```text title="Output"
{"Assam" => 2, "Sencha" => 1}
```

## 4.4 Ranges and tuples

A **range** is a sequence of numbers described by its ends. You used them in `for` loops. They are collections too:

```alice
puts (1..5).sum
puts (1...5).to_a
puts (1..10).step(3).to_a
puts (1..10).includes?(7)
```

```text title="Output"
15
[1, 2, 3, 4]
[1, 4, 7, 10]
true
```

A range does not store its numbers, so `(1..1_000_000)` costs nothing until you use it.

A **tuple** groups a few values of different types, like a tea and its price. A **named tuple** gives each value a name, which is clearer when there are more than two:

```alice
pair = {"Assam", 250}
name, cents = pair
puts "#{name} costs #{cents}"
puts pair[1]

tea = {name: "Earl Grey", cents: 300, caffeine: true}
puts tea.name
puts tea[:cents]
puts tea
```

```text title="Output"
Assam costs 250
250
Earl Grey
300
{name: "Earl Grey", cents: 300, caffeine: true}
```

Tuples are values, not objects: making one allocates nothing. Use them to return a few results from a method. When a group of values deserves methods of its own, make it a record instead ([chapter 6](https://alice-lang.org/documentation/learn/types.md)).

## 4.5 Blocks and iterators

You have written blocks already: the code in `{ |i| ... }` after `times` or `each`. A block is a piece of code that you hand to a method, and the method calls it. Collections have many methods that take blocks, and together they replace most loops.

Here is a question about an order list, first with a loop and then with blocks:

```alice
prices = [250, 300, 175, 400, 350]

expensive_total = 0
for p in prices
  expensive_total += p if p >= 300
end
puts expensive_total

puts prices.select { |p| p >= 300 }.sum
```

```text title="Output"
1050
1050
```

The second version says *what* you want: pick the expensive ones, then add them up. The most useful iterators are:

| Method                                             | Gives you                                                 |
| -------------------------------------------------- | --------------------------------------------------------- |
| `map { \|x\| ... }`                                | a new collection with the block's result for each element |
| `select { \|x\| ... }` / `reject`                  | the elements for which the block is true / false          |
| `find { \|x\| ... }`                               | the first such element, or `nil`                          |
| `sum`, `min`, `max`, `count`                       | one number                                                |
| `sort`, `sort_by { \|x\| ... }`, `reverse`, `uniq` | a reordered collection                                    |
| `each_with_index { \|x, i\| ... }`                 | each element with its position                            |
| `group_by { \|x\| ... }`, `tally`, `partition`     | elements sorted into groups                               |
| `reduce(start) { \|acc, x\| ... }`                 | anything you can build one element at a time              |

```alice
teas = ["Assam", "Earl Grey", "Sencha", "Oolong"]
puts teas.map { |t| t.size }
puts teas.sort_by { |t| t.size }.first
puts teas.reject { |t| t.includes?(" ") }.join(", ")
teas.each_with_index { |t, i| puts "#{i + 1}. #{t}" }
puts teas.reduce(0) { |total, t| total + t.size }
```

```text title="Output"
[5, 9, 6, 6]
Assam
Assam, Sencha, Oolong
1. Assam
2. Earl Grey
3. Sencha
4. Oolong
26
```

### Shorter blocks

When a block only calls one method on its argument, `&:name` says it in two characters. A block without `|params|` can name its argument `it`, or its arguments `_1`, `_2`:

```alice
teas = ["assam", "sencha"]
puts teas.map(&:upcase)
puts [3, 1, 2].map { it * 10 }
puts [3, 1, 2].sort { _2 <=> _1 }
```

```text title="Output"
["ASSAM", "SENCHA"]
[30, 10, 20]
[3, 2, 1]
```

`a <=> b` compares two values and gives -1, 0 or 1. `sort` uses it to order the elements, so swapping `_1` and `_2` sorts in reverse.

## 4.6 Why pipelines are fast

A chain like `map`, then `select`, then `sum` looks expensive. In many languages it is: each step builds a whole new array. A million elements means two temporary arrays of a million elements each.

Alice **fuses** such chains. It compiles the pipeline into one loop that computes each element, tests it and adds it, with no temporary arrays at all:

```alice
def even_squares(n : Int32) : Int64
  (1..n).map { |i| i.to_i64 * i }.select { |x| x % 2 == 0 }.sum
end

puts even_squares(1_000_000)
```

```text title="Output"
166667166667000000
```

You can see this with `alice emit`, which prints the C# the compiler generates. Shortened, the method becomes:

```csharp
long sum = 0;
for (var i = 1; i <= n; i++)
{
    var x = ((long)i) * i;
    if ((x & 1) == 0) sum += x;
}
return sum;
```

This is what you would write by hand in C. It even replaced `x % 2 == 0` with a cheaper bit test. So in Alice you do not have to choose between readable code and fast code: write the pipeline. [Chapter 12](https://alice-lang.org/documentation/learn/performance.md) shows how to check which optimizations a method received.

## Project: the menu and the day's orders

The tea shop now has a menu and a list of the day's orders. Each order is a tuple of a tea and a number of cups. We want the revenue, the best seller and the cups sold per tea.

```alice
menu = {"Assam" => 250, "Earl Grey" => 300, "Sencha" => 350}
orders = [{"Assam", 2}, {"Sencha", 1}, {"Assam", 3}, {"Earl Grey", 1}]

revenue = orders.sum { |o| menu[o[0]].to_i64 * o[1] }
puts "Revenue: #{revenue} cents"

cups = Hash(String, Int32).new(0)
orders.each { |o| cups[o[0]] += o[1] }
puts cups

best = cups.max_by { |tea, n| n }
puts "Best seller: #{best.key} (#{best.value} cups)"
```

```text title="Output"
Revenue: 1900 cents
{"Assam" => 5, "Sencha" => 1, "Earl Grey" => 1}
Best seller: Assam (5 cups)
```

`max_by` on a hash returns the winning key-value pair. `key` and `value` read its two halves.

:::caution\[Common mistakes]

- **A negative index.** `xs[-1]` is `IndexOutOfRangeException`, not the last element. Use `xs.last`.
- **Appending to an array.** `xs << 4` on an `Array(T)` does not compile. Build a `List(T)`, or make the array with its final size.
- **Expecting `nil` for a missing hash key.** `h[k]` raises `KeyNotFoundException`. Use `fetch(k, default)`, `key?(k)` or a hash with a default.
- **Forgetting that assignment shares.** `b = a` does not copy. Use `a.dup` when you need an independent copy.
- **Expecting a `Float64` sum of integers.** `sum` keeps the element type. Convert first: `xs.sum { |x| x.to_f }`.
  :::

## Exercises

1. Given `words = ["tea", "cake", "tea", "jam", "cake", "tea"]`, print how many times each word occurs, then the most common word.
2. Print the squares of the odd numbers from 1 to 9, joined with spaces.
3. Write `average(xs : Array(Int32)) : Float64`. What should it do for an empty array? Make it return `0.0` then.
4. Given `menu = {"Assam" => 250, "Sencha" => 350}`, print the teas that cost less than 300, using `select` and `keys`.

<details>
<summary>Answers</summary>

1. Answer:

   ```alice
   words = ["tea", "cake", "tea", "jam", "cake", "tea"]
   counts = words.tally
   puts counts
   puts counts.max_by { |w, n| n }.key
   ```

   ```text title="Output"
   {"tea" => 3, "cake" => 2, "jam" => 1}
   tea
   ```

2. Answer:

   ```alice
   puts (1..9).select { |n| n.odd? }.map { |n| n * n }.join(" ")
   ```

   ```text title="Output"
   1 9 25 49 81
   ```

3. Check the empty case first, because dividing by a size of 0 has no sensible answer:

   ```alice
   def average(xs : Array(Int32)) : Float64
     return 0.0 if xs.empty?
     xs.sum.to_f / xs.size
   end

   puts average([1, 2, 3, 4])
   puts average(Array(Int32).new(0, 0))
   ```

   ```text title="Output"
   2.5
   0.0
   ```

4. Answer:

   ```alice
   menu = {"Assam" => 250, "Sencha" => 350}
   puts menu.select { |tea, cents| cents < 300 }.keys.join(", ")
   ```

   ```text title="Output"
   Assam
   ```

</details>

## Summary

- `Array(T)` has a fixed size and is the fastest collection. `List(T)` grows with `<<`.
- Assigning a collection shares it. `dup` copies.
- `Hash(K, V)` maps keys to values. A missing key raises; `fetch`, `key?` and `Hash(K, V).new(default)` handle it.
- Ranges describe sequences without storing them. Tuples and named tuples group a few values for free.
- Blocks with `map`, `select`, `sum` and friends replace most loops, and the compiler fuses chains into one loop.

[Chapter 5](https://alice-lang.org/documentation/learn/strings.md) looks at the values you have printed all along: strings.

## Continue reading

- Previous: [3. Common programming concepts](https://alice-lang.org/documentation/learn/common-concepts.md)
- Next: [5. Strings and text](https://alice-lang.org/documentation/learn/strings.md)