1028 Intermediate

1028-btreeset-ops — BTreeSet Operations

Functional Programming

Tutorial

The Problem

Set operations — union, intersection, difference, and symmetric difference — are mathematical primitives used throughout computing: dependency resolution (which packages are in both A and B?), access control (union of permissions), deduplication, and set-based query optimization in databases.

Rust's BTreeSet provides sorted sets with efficient O(n) set operations on sorted sequences and O(log n) membership tests. The sorted ordering guarantees deterministic iteration order, making it suitable for reproducible output.

🎯 Learning Outcomes

• Perform union, intersection, difference, and symmetric difference on BTreeSet

• Understand that BTreeSet iterates in sorted order

• Check subset, superset, and disjoint relationships

• Use set operations as iterators for lazy evaluation

• Choose BTreeSet vs HashSet based on ordering requirements

Code Example

#![allow(clippy::all)]
// 1028: BTreeSet — Union, Intersection, Difference
// Rust's BTreeSet provides sorted set with efficient set operations

use std::collections::BTreeSet;

/// Basic set operations: union, intersection, difference
fn basic_ops() {
    let a: BTreeSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();
    let b: BTreeSet<i32> = [3, 4, 5, 6, 7].into_iter().collect();

    let union: Vec<_> = a.union(&b).copied().collect();
    assert_eq!(union, vec![1, 2, 3, 4, 5, 6, 7]);

    let inter: Vec<_> = a.intersection(&b).copied().collect();
    assert_eq!(inter, vec![3, 4, 5]);

    let diff: Vec<_> = a.difference(&b).copied().collect();
    assert_eq!(diff, vec![1, 2]);

    // Symmetric difference: elements in either but not both
    let sym_diff: Vec<_> = a.symmetric_difference(&b).copied().collect();
    assert_eq!(sym_diff, vec![1, 2, 6, 7]);
}

/// Subset and disjoint checks
fn subset_checks() {
    let small: BTreeSet<i32> = [2, 3].into_iter().collect();
    let big: BTreeSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let other: BTreeSet<i32> = [5, 6].into_iter().collect();

    assert!(small.is_subset(&big));
    assert!(!big.is_subset(&small));
    assert!(big.is_superset(&small));
    assert!(small.is_disjoint(&other));
}

/// Iterator-based operations
fn iter_ops() {
    let s: BTreeSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();
    let sum: i32 = s.iter().sum();
    assert_eq!(sum, 15);

    let evens: BTreeSet<_> = s.iter().filter(|&&x| x % 2 == 0).copied().collect();
    let expected: BTreeSet<i32> = [2, 4].into_iter().collect();
    assert_eq!(evens, expected);

    // Range query on sorted set
    let range: Vec<_> = s.range(2..=4).copied().collect();
    assert_eq!(range, vec![2, 3, 4]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_ops() {
        basic_ops();
    }

    #[test]
    fn test_subset_checks() {
        subset_checks();
    }

    #[test]
    fn test_iter_ops() {
        iter_ops();
    }

    #[test]
    fn test_operator_style() {
        let a: BTreeSet<i32> = [1, 2, 3].into_iter().collect();
        let b: BTreeSet<i32> = [2, 3, 4].into_iter().collect();
        // Bitwise operators work as set operations
        let union: BTreeSet<_> = &a | &b;
        let inter: BTreeSet<_> = &a & &b;
        assert_eq!(union, [1, 2, 3, 4].into_iter().collect());
        assert_eq!(inter, [2, 3].into_iter().collect());
    }
}

(* 1028: BTreeSet — Union, Intersection, Difference *)
(* OCaml's Set module provides sorted set operations *)

module IntSet = Set.Make(Int)

(* Approach 1: Basic set operations *)
let basic_ops () =
  let a = IntSet.of_list [1; 2; 3; 4; 5] in
  let b = IntSet.of_list [3; 4; 5; 6; 7] in
  let union = IntSet.union a b in
  let inter = IntSet.inter a b in
  let diff = IntSet.diff a b in
  assert (IntSet.elements union = [1; 2; 3; 4; 5; 6; 7]);
  assert (IntSet.elements inter = [3; 4; 5]);
  assert (IntSet.elements diff = [1; 2])

(* Approach 2: Subset and disjoint checks *)
let subset_checks () =
  let small = IntSet.of_list [2; 3] in
  let big = IntSet.of_list [1; 2; 3; 4] in
  let other = IntSet.of_list [5; 6] in
  assert (IntSet.subset small big);
  assert (not (IntSet.subset big small));
  assert (IntSet.disjoint small other)

(* Approach 3: Fold-based operations *)
let fold_ops () =
  let s = IntSet.of_list [1; 2; 3; 4; 5] in
  let sum = IntSet.fold (fun x acc -> x + acc) s 0 in
  assert (sum = 15);
  let evens = IntSet.filter (fun x -> x mod 2 = 0) s in
  assert (IntSet.elements evens = [2; 4])

let () =
  basic_ops ();
  subset_checks ();
  fold_ops ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Persistence: OCaml's Set is persistent via structural sharing; Rust's BTreeSet requires .clone() to preserve the original.

Iterator API: Rust's set operations return iterators, enabling lazy chaining; OCaml's operations return new sets immediately.

**No HashSet in OCaml stdlib**: OCaml's standard library only has sorted sets; Hashtbl-based sets exist in Base and Core.

Ownership of elements: Rust's set operation iterators yield references; collecting copies requires explicit .copied() or .cloned().

OCaml Approach

OCaml's Set.Make(Ord) provides the same operations:

module IntSet = Set.Make(Int)

let union a b = IntSet.union a b
let inter a b = IntSet.inter a b
let diff a b = IntSet.diff a b

OCaml's sets are persistent — operations return new sets using structural sharing. Rust's BTreeSet is mutable, so operations produce new sets by cloning.

Full Source

#![allow(clippy::all)]
// 1028: BTreeSet — Union, Intersection, Difference
// Rust's BTreeSet provides sorted set with efficient set operations

use std::collections::BTreeSet;

/// Basic set operations: union, intersection, difference
fn basic_ops() {
    let a: BTreeSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();
    let b: BTreeSet<i32> = [3, 4, 5, 6, 7].into_iter().collect();

    let union: Vec<_> = a.union(&b).copied().collect();
    assert_eq!(union, vec![1, 2, 3, 4, 5, 6, 7]);

    let inter: Vec<_> = a.intersection(&b).copied().collect();
    assert_eq!(inter, vec![3, 4, 5]);

    let diff: Vec<_> = a.difference(&b).copied().collect();
    assert_eq!(diff, vec![1, 2]);

    // Symmetric difference: elements in either but not both
    let sym_diff: Vec<_> = a.symmetric_difference(&b).copied().collect();
    assert_eq!(sym_diff, vec![1, 2, 6, 7]);
}

/// Subset and disjoint checks
fn subset_checks() {
    let small: BTreeSet<i32> = [2, 3].into_iter().collect();
    let big: BTreeSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let other: BTreeSet<i32> = [5, 6].into_iter().collect();

    assert!(small.is_subset(&big));
    assert!(!big.is_subset(&small));
    assert!(big.is_superset(&small));
    assert!(small.is_disjoint(&other));
}

/// Iterator-based operations
fn iter_ops() {
    let s: BTreeSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();
    let sum: i32 = s.iter().sum();
    assert_eq!(sum, 15);

    let evens: BTreeSet<_> = s.iter().filter(|&&x| x % 2 == 0).copied().collect();
    let expected: BTreeSet<i32> = [2, 4].into_iter().collect();
    assert_eq!(evens, expected);

    // Range query on sorted set
    let range: Vec<_> = s.range(2..=4).copied().collect();
    assert_eq!(range, vec![2, 3, 4]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_ops() {
        basic_ops();
    }

    #[test]
    fn test_subset_checks() {
        subset_checks();
    }

    #[test]
    fn test_iter_ops() {
        iter_ops();
    }

    #[test]
    fn test_operator_style() {
        let a: BTreeSet<i32> = [1, 2, 3].into_iter().collect();
        let b: BTreeSet<i32> = [2, 3, 4].into_iter().collect();
        // Bitwise operators work as set operations
        let union: BTreeSet<_> = &a | &b;
        let inter: BTreeSet<_> = &a & &b;
        assert_eq!(union, [1, 2, 3, 4].into_iter().collect());
        assert_eq!(inter, [2, 3].into_iter().collect());
    }
}

(* 1028: BTreeSet — Union, Intersection, Difference *)
(* OCaml's Set module provides sorted set operations *)

module IntSet = Set.Make(Int)

(* Approach 1: Basic set operations *)
let basic_ops () =
  let a = IntSet.of_list [1; 2; 3; 4; 5] in
  let b = IntSet.of_list [3; 4; 5; 6; 7] in
  let union = IntSet.union a b in
  let inter = IntSet.inter a b in
  let diff = IntSet.diff a b in
  assert (IntSet.elements union = [1; 2; 3; 4; 5; 6; 7]);
  assert (IntSet.elements inter = [3; 4; 5]);
  assert (IntSet.elements diff = [1; 2])

(* Approach 2: Subset and disjoint checks *)
let subset_checks () =
  let small = IntSet.of_list [2; 3] in
  let big = IntSet.of_list [1; 2; 3; 4] in
  let other = IntSet.of_list [5; 6] in
  assert (IntSet.subset small big);
  assert (not (IntSet.subset big small));
  assert (IntSet.disjoint small other)

(* Approach 3: Fold-based operations *)
let fold_ops () =
  let s = IntSet.of_list [1; 2; 3; 4; 5] in
  let sum = IntSet.fold (fun x acc -> x + acc) s 0 in
  assert (sum = 15);
  let evens = IntSet.filter (fun x -> x mod 2 = 0) s in
  assert (IntSet.elements evens = [2; 4])

let () =
  basic_ops ();
  subset_checks ();
  fold_ops ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_ops() {
        basic_ops();
    }

    #[test]
    fn test_subset_checks() {
        subset_checks();
    }

    #[test]
    fn test_iter_ops() {
        iter_ops();
    }

    #[test]
    fn test_operator_style() {
        let a: BTreeSet<i32> = [1, 2, 3].into_iter().collect();
        let b: BTreeSet<i32> = [2, 3, 4].into_iter().collect();
        // Bitwise operators work as set operations
        let union: BTreeSet<_> = &a | &b;
        let inter: BTreeSet<_> = &a & &b;
        assert_eq!(union, [1, 2, 3, 4].into_iter().collect());
        assert_eq!(inter, [2, 3].into_iter().collect());
    }
}

Deep Comparison

BTreeSet: Union, Intersection, Difference — Comparison

Core Insight

Set algebra maps naturally to both languages. OCaml's Set module provides functional (immutable) set operations; Rust's BTreeSet returns lazy iterators over sorted results, plus operator overloads (|, &) for ergonomic use.

OCaml Approach

• Set.Make(Ord) functor creates typed set module

• union, inter, diff return new immutable sets

• subset, disjoint for relationship checks

• elements to convert to sorted list

• filter and fold for derived operations

Rust Approach

• BTreeSet<T: Ord> — generic, no functor needed

• union(), intersection(), difference() return lazy iterators

• symmetric_difference() — elements in either but not both

• is_subset(), is_superset(), is_disjoint() for checks

• Operator overloads: &a | &b (union), &a & &b (intersection)

• range() for efficient sub-range queries

Comparison Table

Feature	OCaml (`Set`)	Rust (`BTreeSet`)
Union	`Set.union a b`	`a.union(&b)` / `&a \\| &b`
Intersection	`Set.inter a b`	`a.intersection(&b)` / `&a & &b`
Difference	`Set.diff a b`	`a.difference(&b)` / `&a - &b`
Symmetric diff	Manual via union+diff	`a.symmetric_difference(&b)` / `&a ^ &b`
Returns	New set (allocated)	Lazy iterator (zero-alloc)
Subset check	`Set.subset a b`	`a.is_subset(&b)`
Mutability	Immutable	Mutable

Exercises

Write a multi_union(sets: Vec<BTreeSet<i32>>) -> BTreeSet<i32> function that unions any number of sets.

Implement a simple dependency resolver: given a map of package -> direct dependencies, compute the full transitive closure using repeated set unions.

Use symmetric_difference to find words that appear in one text but not the other, implementing a simple diff tool for word sets.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust