Traits and Iteration

Shared behavior, loops, and parallelism

Recap

So far we have seen

• Rust’s basic types, struct, enum, generics
• Ownership, borrowing, lifetimes

Next: how to define shared behavior across types and use it to iterate over data

1. Traits: shared behavior (cf. Haskell’s typeclasses)
2. Iterators: for loops, map, filter, collect
3. Parallel Iteration: with rayon

Today’s Goals

1. Traits: shared behavior (cf. Haskell’s typeclasses)
2. Iterators: for loops, map, filter, collect
3. Parallel Iteration: with rayon

What is a Trait?

A trait defines a set of methods that a type must implement …

… aka typeclass in Haskell!

Haskell

class Summary a where
  summarize :: a -> String

Rust

trait Summary {
    fn summarize(&self) -> String;
}

(Like typeclasses) traits let us write code that works with any type that implements that interface.

Implementing a Trait

Haskell

data Article = MkArticle
  { headline :: String
  , author   :: String
  }

instance Summary Article where
  summarize a = headline a ++ ", by " ++ author a

Rust

struct Article {
    headline: String,
    author: String,
}

impl Summary for Article {
    fn summarize(&self) -> String {
        format!("{}, by {}", self.headline, self.author)
    }
}

Multiple Types, One Trait

Different types can implement the same trait with different behavior

struct Post {
    username: String,
    content: String,
}

impl Summary for Post {
    fn summarize(&self) -> String {
        format!("{}: {}", self.username, self.content)
    }
}

Now we can call summarize() on both Article and Post

fn main() {
    let a = Article { headline: String::from("Penguins Win!"),
                      author: String::from("Iceburgh") };
    let p = Post { username: String::from("horse_ebooks"),
                   content: String::from("of course as you know") };
    println!("{}", a.summarize()); // "Penguins Win!, by Iceburgh"
    println!("{}", p.summarize()); // "horse_ebooks: of course as you know"
}

Traits as Parameters

We can write functions that accept any type implementing a trait

Haskell: “Constraint”

notify :: (Summary a) => a -> String
notify item = "Breaking news! " ++ summarize item

• Haskell calls Summary a a constraint on the type variable a

Rust: “Trait Bound”

fn notify<T: Summary>(item: &T) {
    println!("Breaking news! {}", item.summarize());
}

• Rust calls T: Summary a trait bound on the type variable T

Multiple Trait Bounds

A parameter can require multiple traits with +

fn notify<T: Summary + std::fmt::Display>(item: &T) {
    println!("Breaking news! {}", item.summarize());
}

When bounds get long, use a where clause:

fn some_function<T, U>(t: &T, u: &U) -> i32
where
    T: Summary + Clone,
    U: Clone + std::fmt::Debug,
{
    todo!()
}

QUIZ

trait Area {
    fn area(&self) -> f64;
}

struct Circle { radius: f64 }

struct Rect { width: f64, height: f64 }

impl Area for Circle {
    fn area(&self) -> f64 {
        std::f64::consts::PI * self.radius * self.radius
    }
}

fn print_area<T: Area>(shape: &T) {
    println!("Area: {}", shape.area());
}

fn main() {
    let c = Circle { radius: 10.0 };
    let r = Rect { width: 3.0, height: 4.0 };
    print_area(&c);
    print_area(&r);
}

What happens?

Compiler Error: Trait Not Implemented

error[E0277]: the trait bound `Rect: Area` is not satisfied
  --> src/main.rs:20:17
   |
20 |     print_area(&r);
   |     ---------- ^^ the trait `Area` is not implemented for `Rect`
   |     |
   |     required by a bound introduced by this call

Fix: implement Area for Rect!

impl Area for Rect {
    fn area(&self) -> f64 {
        self.width * self.height
    }
}

Familiar Traits: Debug, Clone, Copy

We’ve already used traits via #[derive(...)]!

#[derive(Debug, Clone, Copy)]
struct Circle {
    x: f64,
    y: f64,
    radius: f64,
}

• Debug lets you print with {:?}
• Clone gives you .clone()
• Copy makes assignment copy instead of move

These are all traits defined in the standard library.

Goal Today

1. Traits: shared behavior (cf. Haskell’s typeclasses)
2. Iterators: for loops, map, filter, collect
3. Parallel Iteration: with rayon

The Iterator Trait

Iteration in Rust is built on a simple trait

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

• type Item is the type of elements produced (an associated type)
• next() returns Some(value) or None when done
• Calling next() consumes one element (hence &mut self)

Calling next Directly

fn main() {
    let v = vec![10, 20, 30];
    let mut iter = v.iter();

    println!("{:?}", iter.next()); // Some(10)
    println!("{:?}", iter.next()); // Some(20)
    println!("{:?}", iter.next()); // Some(30)
    println!("{:?}", iter.next()); // None
}

Note: iter must be mut because next() advances internal state.

for Loops Use Iterators

A for loop is syntactic sugar for calling next() repeatedly

fn main() {
    let v = vec![10, 20, 30];
    for val in v.iter() {
        println!("Got: {val}");
    }
}

Prints:

Got: 10
Got: 20
Got: 30

The for loop calls next() behind the scenes until it gets None.

Three Ways to Iterate

QUIZ

fn main() {
    let v = vec![String::from("a"), String::from("b")];

    for s in v.iter() {
        println!("{s}");
    }
    println!("{:?}", v);
}

fn main() {
    let mut v = vec![String::from("a"), String::from("b")];

    for s in v.iter_mut() {
        s.push_str("_foo");
    }
    println!("{:?}", v);
}

fn main() {
    let v = vec![String::from("a"), String::from("b")];

    for s in v.into_iter() {
        println!("{s}");
    }

    println!("{:?}", v);
}

Iterator Adaptors: map

Iterator adaptors transform one iterator into another.

Haskell

map (+1) [1, 2, 3]   -- [2, 3, 4]

Rust

fn main() {
    let v = vec![1, 2, 3];
    let v2: Vec<i32> = v.iter().map(|x| x + 1).collect();
    println!("{:?}", v2); // [2, 3, 4]
}

• |x| x + 1 is a closure (like Haskell’s \x -> x + 1)
• .collect() consumes the iterator and builds a Vec

Important: iterators are lazy – nothing happens until you consume them!

Iterator Adaptors: filter

Haskell

filter even [1, 2, 3, 4, 5]   -- [2, 4]

Rust

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    let evens: Vec<&i32> = v.iter().filter(|x| *x % 2 == 0).collect();
    println!("{:?}", evens); // [2, 4]
}

filter keeps elements where the closure returns true.

Chaining Adaptors

You can chain map, filter, and other adaptors together

Haskell

sum (map (*2) (filter even [1..10]))   -- 60

Rust

fn main() {
    let v: Vec<i32> = (1..=10).collect();
    let result: i32 = v.iter()
        .filter(|x| *x % 2 == 0)
        .map(|x| x * 2)
        .sum();
    println!("{result}"); // 60
}

Read it as a pipeline: start with 1..=10, keep evens, double them, sum.

QUIZ

What does this print?

fn main() {
    let words = vec!["hello", "world", "hi"];
    let result: Vec<_> = words.iter()
        .filter(|w| w.len() > 2)
        .collect();
    println!("{:?}", result);
}

Answer

["hello", "world"]

• filter keeps words with length > 2: "hello", "world"
• copied converts &&str to &str
• collect builds a Vec<&str>

Goal Today

1. Traits: shared behavior (cf. Haskell’s typeclasses)
2. Iterators: for loops, map, filter, collect
3. Parallel Iteration: with rayon

Parallel Iteration with Rayon

What if you want to speed up iteration by using multiple cores?

In most languages, parallelism is hard and error-prone (data races, deadlocks, …).

Rust’s ownership it safe; Rayon makes it easy.

Sequential vs Parallel: One Line Change

Sequential

let total: i32 = data.iter()
    .filter(|x| is_interesting(x))
    .map(|x| heavy_computation(x))
    .sum();

Parallel (with Rayon)

use rayon::prelude::*;

let total: i32 = data.par_iter()
    .filter(|x| is_interesting(x))
    .map(|x| heavy_computation(x))
    .sum();

Just change .iter() to .par_iter() … that’s it!

Rayon automatically splits the work across threads.

Rayon’s Parallel Iterators

Three parallel equivalents of the sequential methods:

All the familiar adaptors work: map, filter, sum, collect, …

Example: Parallel Sum of Squares

use rayon::prelude::*;

fn sum_of_squares(v: &[i64]) -> i64 {
    v.par_iter()
        .map(|x| x * x)
        .sum()
}

fn main() {
    let data: Vec<i64> = (1..=1_000_000).collect();
    let result = sum_of_squares(&data);
    println!("Sum of squares: {result}");
}

Rayon handles thread creation, work splitting, and joining – all behind the scenes.

Why is Rayon Safe?

Why can’t we have data races?

Sequential: This compiles

let mut total = 0;
data.iter()
    .filter(|x| is_interesting(x))
    .for_each(|x| total += heavy_computation(x));

Parallel: This does NOT compile!

let mut total = 0;
data.par_iter()
    .filter(|x| is_interesting(x))
    .for_each(|x| total += heavy_computation(x));  // ERROR!

error: cannot assign to `total`, as it is a captured variable
       in a `Fn` closure

Rust’s Type System Prevents Data Races

Rayon requires closures to be Fn (not FnMut)

• Fn: can only read captured variables (shared access)
• FnMut: can modify captured variables (exclusive access)

Multiple threads running total += ... would be a data race!

The compiler rejects this at compile time.

Fix: use Rayon’s built-in sum(), which safely combines partial results

let total: i32 = data.par_iter()
    .filter(|x| is_interesting(x))
    .map(|x| heavy_computation(x))
    .sum();                          // safe parallel reduction

This is Rust’s fearless concurrency: the compiler catches threading bugs before your code runs.

QUIZ

Which of these can be safely parallelized with par_iter?

// (A) sum the lengths of strings
let total: usize = words.iter()
    .map(|w| w.len())
    .sum();

// (B) collect uppercase versions
let upper: Vec<String> = words.iter()
    .map(|w| w.to_uppercase())
    .collect();

// (C) push into a shared vec
let mut results = Vec::new();
words.iter()
    .for_each(|w| results.push(w.to_uppercase()));

Answer

• (A) Yes! map + sum is safe to parallelize; no shared mutable state.
• (B) Yes! map + collect is safe; each closure produces an independent value.
• (C) No! results.push(...) mutates a shared Vec – the compiler would reject the parallel version.

The pattern: if your pipeline uses pure functions (no side effects), it parallelizes safely.

Using Rayon: Setup

Add rayon to your Cargo.toml:

[dependencies]
rayon = "1.10"

Then import the prelude:

use rayon::prelude::*;

That’s it! Now .par_iter(), .par_iter_mut(), and .into_par_iter() are available on standard collections.

Goal Today

1. Traits: shared behavior via trait, impl Trait for Type, trait bounds
2. Iterators: Iterator trait, for loops, map, filter, collect
3. Parallel Iteration: Rayon’s par_iter, fearless concurrency

Summary

Traits define shared behavior across types

• Like Haskell’s typeclasses
• Use impl Trait or T: Trait for generic functions

Iterators provide a uniform way to process sequences

• for loops, map, filter, collect, sum, …
• Lazy: nothing happens until consumed

Rayon makes parallelism a one-line change

• Replace .iter() with .par_iter()
• Rust’s type system prevents data races at compile time
• “Fearless concurrency”

Material Inspired by

• https://doc.rust-lang.org/book/ch10-02-traits.html
• https://doc.rust-lang.org/book/ch13-02-iterators.html
• https://developers.redhat.com/blog/2021/04/30/how-rust-makes-rayons-data-parallelism-magical