Matching with no clean sides

Matching without a clean two-sided structure is still in the cheap category. Surprising, and worth knowing.

1. 01
   Roommate pairing has no left/right split — any student can pair with any other. petgraph's maximum_matching runs the blossom algorithm and returns the maximum set of disjoint pairs.

   use petgraph::algo::matching::maximum_matching;
   use petgraph::graph::UnGraph;
   
   fn roommate_pairs(compat: &UnGraph<&str, ()>) -> Vec<(&str, &str)> {
       let m = maximum_matching(compat);
       m.edges()
           .map(|(a, b)| (compat[a], compat[b]))
           .collect()
   }

2. 02
   Page 4 introduced &str as "a read-only view into someone else's bytes." The graph on this page carries &str labels — borrowed strings, owned by whoever built the graph. Rust has a second string type, String, which owns its bytes on the heap, and the choice between the two is one of the most consequential decisions in any Rust API. Beginners reach for String everywhere because it is the more permissive type — and pay for it on every parameter pass, every clone, every function boundary. The rule of thumb that experienced Rust programmers internalise: take &str for parameters, return String when you constructed new text, hold String in a struct only when the struct should own its text. Reaching for the easiest-to-remember type — String everywhere — produces APIs that allocate on every call and force callers to clone literals they could have borrowed. Thinking carefully about how a series of chars flows through your code is the work.

   // Two string types, two different jobs.
   
   let owned:  String       = String::from("hello"); // owns bytes on the heap
   let view:   &str         = &owned;                // borrow into owned's bytes
   let literal: &'static str = "hello";              // bytes baked into the binary
   
   
   // ── Parameters: prefer &str — borrows, no allocation ──────────
   fn greet(name: &str) -> String {
       format!("Hello, {}!", name)        // returns a NEW String
   }
   
   greet("Andy");                          // literal is &str ✓
   greet(&owned);                          // &String coerces to &str ✓
   greet(&owned[1..4]);                    // slicing a String yields &str ✓
   
   
   // ── The trap: needlessly demanding ownership ──────────────────
   fn greet_owns(name: String) -> String {        // takes ownership
       format!("Hello, {}!", name)
   }
   
   greet_owns("Andy".to_string());          // had to allocate the literal
   greet_owns(owned.clone());               // had to deep-copy the String
   //                  └─ every caller pays for the easy signature.
   
   
   // ── Struct fields: pick based on lifetime ─────────────────────
   struct Customer {
       name:   String,         // Customer should own its name — String.
       region: &'static str,   // region is one of a fixed set of tags — interned literal.
   }
   
   struct CustomerView<'a> {
       name:   &'a str,        // view into a name owned somewhere else.
   }
   
   
   // ── Rule of thumb ─────────────────────────────────────────────
   //   parameters      →  &str   (borrow; no allocation)
   //   return values   →  String when you constructed new text
   //                      &str   when you're returning a view into existing bytes
   //   struct fields   →  String when the struct should own
   //                      &str   (with a lifetime) when it borrows

3. 03
   () is Rust's unit type — a tuple with zero elements. It carries no information and takes zero bytes. You use it whenever a slot in the type system needs to be filled but has nothing to say. On this page, UnGraph<&str, ()> declares a graph whose nodes carry &str labels and whose edges carry () because there is no weight to attach — two roommates are either compatible or not, no extra data needed. You also see () as the return type of functions that produce no value, and as the success type of Result<(), Error> where only the error is interesting.

   // () — zero-element tuple, zero bytes, no information.
   
   // As the edge type when there's nothing to attach to an edge:
   let g: UnGraph<&str, ()> = UnGraph::new_undirected();
   //                   └── edges carry no weight — "they're connected" is the only fact
   
   // As a function return type — "I finished successfully, no value":
   fn save_to_disk(data: &[u8]) -> () { /* ... */ }     // explicit
   fn save_implicit(data: &[u8])      { /* ... */ }     // same thing — () is the default
   
   // As the Ok variant of Result when only failure is interesting:
   fn validate(name: &str) -> Result<(), String> {
       if name.is_empty() {
           Err("name is empty".to_string())
       } else {
           Ok(())
       }
   }
   
   // Three equivalent ways to write a no-value function:
   fn a() -> () { () }
   fn b() -> () {  }
   fn c()        {  }

4. 04
   The body of roommate_pairs is the iterator chain idiom — Rust's adoption of the functional-programming pipeline (map, filter, fold, collect). An iterator is a lazy sequence: it produces values one at a time on demand, doing no work until something asks. .map(f) returns a new iterator that yields f(x) for each x of the original — still lazy, still no work done. .collect() is the terminal step that finally pulls the chain — it consumes the iterator and gathers the values into a concrete collection (a Vec, a HashMap, a String, whichever you ask for). The whole chain compiles down to a single loop — there is no per-step allocation, no intermediate Vec. This is the standard way to transform a collection in Rust and a much better default than a hand-written for loop with Vec::push.

   // The page 14 chain, broken down:
   let pairs: Vec<(&str, &str)> = m.edges()             // iterator of (NodeIndex, NodeIndex)
       .map(|(a, b)| (compat[a], compat[b]))            // → iterator of (&str, &str)
       .collect();                                       // pull the chain → Vec<(&str, &str)>
   
   
   // Equivalent imperative version — works, but more code and more state:
   let mut pairs: Vec<(&str, &str)> = Vec::new();
   for (a, b) in m.edges() {
       pairs.push((compat[a], compat[b]));
   }
   
   
   // Common iterator combinators (all lazy until a terminal is called):
   let evens: Vec<i32> = (1..=10).filter(|n| n % 2 == 0).collect();
   //                              └── keep only elements matching the predicate
   
   let squared: Vec<i32> = (1..=5).map(|n| n * n).collect();
   //                              └── transform each element
   
   let total: i32 = (1..=10).sum();                          // terminal: add
   let count: usize = (1..=10).filter(|n| n % 3 == 0).count(); // terminal: count
   
   // fold — generalises sum/count/max/min: an initial value and an accumulator.
   let product: i32 = (1..=5).fold(1, |acc, n| acc * n);     // 120
   
   
   // Why the chain is the right default:
   //   1. Reads top-to-bottom as "what we're doing to the data."
   //   2. The compiler fuses adjacent operations — no temporary Vecs.
   //   3. Mistakes that are easy in a for/push loop (off-by-one, wrong
   //      mutation order) don't have room to happen.
   //   4. The same chain works whether the source is a Vec, a slice,
   //      a HashMap, a file's lines, or a channel.