Dict: finding a value by its key

A list finds a value by its position, but often what a program has in hand is a name: a word, a product code, a user. A Dict, short for dictionary, pairs each key with a value, and finds the value again by its key. This page shows how to fill one, look values up, walk its pairs, and handle the lookup that finds nothing, which is where Option comes in. Here is one counting the words of a sentence:

mod words;

import stdio use *;
import collections use *;

fn main() {
  let text = String.from("the cat sat on the mat and the dog sat on the log");

  // Each word, paired with how many times it appears
  var counts = new Dict[String, i32];
  each w in text.split(' ') {         // split gives back a List of the words
    if counts.contains(w) {
      counts[w] += 1;                 // seen before: one more
    } else {
      counts <- w.copy(): 1;          // new: send the word and its first count
    }
  }
  print <- counts.len(), " different words; the: ", counts["the"], ", sat: ", counts["sat"], "\n";

  // A word that may not be there: get gives back an Option
  each word in ["dog", "fish"] {
    match counts.get(*word) {
      case let n Some {print <- *word, ": ", n, "\n";}
      case is None {print <- "no ", *word, "\n";}
    }
  }
}

It prints:

8 different words; the: 4, sat: 2
dog: 1
no fish

Try this: add "mat" and "rat" to the words looked up at the end, and predict what each line will say before you run it.

Pairing keys with values#

A Dict's brackets hold two types, the keys' and then the values': a Dict[String, i32] pairs words with counts. The send operator gives it a key and its value together, with a colon between them, counts <- w.copy(): 1, and a later value for a key it already holds replaces the earlier one. The dictionary keeps its keys, so it is given a copy of the word, w.copy(), and the list of words keeps its own. A dictionary can be built in one go as a list can (Collections), its entries pairs: new Dict[String, i32] <- String.from("Ann"): 31, String.from("Bo"): 12, or <- each w in words yield w.copy(): w.len().

counts["the"] looks a value up by its key, and a dictionary whose keys are Strings is asked with plain text. In a dictionary held in a var variable, the value can be changed where it stands, as counts[w] += 1 does. A key it does not hold stops the program with a panic, "no entry for the key "fish"", so a program that is not sure asks first, with contains, as the counting loop does. The counting loop searches twice for each word, once to ask and once to add; getOrInsert does both in one search, handing back the value held, or the value given, put in place, to change:

each w in text.split(' ') {
  *counts.getOrInsert(w.copy(), 0) += 1;      // the same counts, one search a word
}

remove takes a key and its value out, and len() says how many pairs it holds.

Option: a lookup that may find nothing#

A lookup with [] trusts that the key is there. Often it may not be, and that is no mistake: "fish" was never in the sentence. get asks without that trust, and its answer says which way it went. It gives back an Option: Some holding what it found, or None. Option is an enum from the core library, declared as enum Option[T] {None; Some(T);}, so everything Enums showed works on it. The program's match is the usual one: case let n Some binds what was found, and case is None handles its absence. The match must cover both, so the missing word cannot be forgotten.

When only one case needs handling, the shorter forms from Enums apply. A binding in an if uses the value only when it is there:

if let n Some = counts.get("cat") {
  print <- "cat: ", *n, "\n";
}

A declaration whose else leaves carries on with the value, and leaves when there is none (Enums):

let n Some = counts.get(word) else { return; };

And to ask without the value, test the variant, maybe is None, or compare, maybe == None and maybe != None.

What get finds is the value where it lies in the dictionary, a borrow, so the n it binds is one too: it prints and computes like the number, and *n fetches a copy. A list's get(i), pop() and peek(), from List, answer the same way.

Your own functions can answer with an Option too, when the absence of an answer is a normal outcome rather than a failure. ?i32 is short for Option[i32], and the function returns Some with the value, or None:

// Half of n, when n is even
fn half(n i32) ?i32 {
  if n % 2 == 1 { return None; }
  Some(n / 2);
}

None takes its type from where it goes, here the function's return type. With nothing to say what it holds, as in var maybe = None;, the compiler asks for it: "Could not infer the type parameter T of None … Write the type arguments out: None[T].", so None[i32], or better, var maybe ?i32 = None;. Option is to a missing value what Result is to a failure: both put what might not be there into the type, where the compiler checks that it is handled.

Note: Not built yet: an Option used directly as a condition (if maybe is refused: the condition requires a true/false value), a plain value where an Option is wanted (write Some(5)), and shorter operators for unwrapping an Option or giving it a default. The match and the binding forms above are how an Option is handled today.

Walking a dictionary#

each with two variables walks a dictionary's keys and their values:

var repeated = 0;
each word, count in counts {
  if count > 1 { repeated += 1; }
}                                  // repeated is 3: the, sat and on

A dictionary is unordered. The order it visits its keys in is not the order they went in, and it changes from one run to the next, so a program that prints them in order sorts them first, or uses an OrderedDict, which visits its keys in the order they were added. keys() and values() walk one side only.

What can be a key#

A key must be a type that can be hashed: turned into a number that says where in the dictionary to look. Integers, bool and String can, and so can a struct that declares is Hash, which has the compiler work out its hash from its fields, and which writes the == that goes with it:

struct Pt is Hash {
  pub x i32;
  pub y i32;
  pub fn `==`(self &, o &Pt) bool { x == o.x and y == o.y; }
}

var grid = new Dict[Pt, i32];
grid <- new Pt(1, 2): 5;

A floating-point key is refused: "Dict requires K is Hash, and f64 is not Hash". A key that is not text is looked up through a borrow of it, written with &: squares[&3], grid[&new Pt(1, 2)], squares.get(&k).

You can now pair keys with values, look them up, walk them, and handle a lookup that finds nothing, with the compiler making sure you do. That completes the data types: numbers, text, tuples, structs, enums and the collections that hold them. (How List and Dict get their indexing, their send operator and their walks, and how a struct of yours can do the same, is Method patterns, in Recipes.) Every program so far has done one thing at a time, though. Next, actors put the other cores of your machine to work.