230 Intermediate

Semigroup

Algebra / Type Classes

Tutorial Video

Text description (accessibility)

This video demonstrates the "Semigroup" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Algebra / Type Classes. Model a semigroup — a type equipped with an associative binary operation — and show how several familiar operations (min, max, concatenation, first) are all instances of the same abstraction. Key difference from OCaml: 1. **Module system vs traits:** OCaml first

Tutorial

The Problem

Model a semigroup — a type equipped with an associative binary operation — and show how several familiar operations (min, max, concatenation, first) are all instances of the same abstraction.

🎯 Learning Outcomes

• How to encode type-class-style abstractions as Rust traits

• Why Rust newtypes are needed when multiple semigroup instances exist for the same primitive type

• How split_first + fold cleanly expresses "reduce a non-empty sequence" without panicking

• Why the absence of an identity element (unlike Monoid) means sconcat returns Option<S>

🦀 The Rust Way

Rust uses a trait Semigroup with a single fn append(self, other: Self) -> Self. Each instance (Min, Max, First, NonEmptyList) is a newtype wrapper, avoiding coherence conflicts that would arise from implementing the trait directly on i64. sconcat returns Option<S> instead of panicking — idiomatic Rust prefers explicit failure over exceptions.

Code Example

pub trait Semigroup {
    fn append(self, other: Self) -> Self;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Min(pub i64);

impl Semigroup for Min {
    fn append(self, other: Self) -> Self {
        Min(self.0.min(other.0))
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct First<T>(pub T);

impl<T> Semigroup for First<T> {
    fn append(self, _other: Self) -> Self { self }
}

pub fn sconcat<S: Semigroup + Clone>(items: &[S]) -> Option<S> {
    let (head, tail) = items.split_first()?;
    Some(tail.iter().cloned().fold(head.clone(), |acc, x| acc.append(x)))
}

module type SEMIGROUP = sig
  type t
  val append : t -> t -> t
end

module MinSemigroup : SEMIGROUP with type t = int = struct
  type t = int
  let append = min
end

module FirstSemigroup : SEMIGROUP with type t = string = struct
  type t = string
  let append a _ = a
end

let sconcat (module S : SEMIGROUP) lst =
  match lst with
  | []      -> failwith "sconcat: empty list"
  | x :: xs -> List.fold_left S.append x xs

Key Differences

Module system vs traits: OCaml first-class modules ((module MinSemigroup)) become Rust generic type parameters (<S: Semigroup>).

Failure mode: OCaml failwith on empty list vs Rust Option::None — Rust makes partial functions explicit in the type.

Multiple instances per type: OCaml uses distinct named modules; Rust uses newtypes (Min, Max) to avoid orphan/coherence violations.

Ownership: append(self, other: Self) consumes both values — idiomatic for value types; Clone bound lets combinators work on slices.

OCaml Approach

OCaml uses a module signature SEMIGROUP with a single append value, then functor-style first-class modules passed to sconcat. The List.fold_left inside sconcat does the left-associative reduction, and a missing identity means an empty list causes failwith.

Full Source

#![allow(clippy::all)]
// A semigroup is a set with an associative binary operation.
// Like a monoid but without requiring an identity element.
// Weaker but more widely applicable.

/// A semigroup: a type with an associative binary operation.
///
/// Law: (a.append(b)).append(c) == a.append(b.append(c))
pub trait Semigroup {
    fn append(self, other: Self) -> Self;
}

// ── Concrete semigroup instances ──────────────────────────────────────────────

/// NonEmpty list semigroup — concatenation (note: no empty element!)
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NonEmptyList<T>(pub Vec<T>);

impl<T: Clone> Semigroup for NonEmptyList<T> {
    fn append(self, other: Self) -> Self {
        let mut v = self.0;
        v.extend(other.0);
        NonEmptyList(v)
    }
}

/// Min semigroup — take the smaller of two values
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Min(pub i64);

impl Semigroup for Min {
    fn append(self, other: Self) -> Self {
        Min(self.0.min(other.0))
    }
}

/// Max semigroup — take the larger of two values
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Max(pub i64);

impl Semigroup for Max {
    fn append(self, other: Self) -> Self {
        Max(self.0.max(other.0))
    }
}

/// First semigroup — always keep the first value, discard the second
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct First<T>(pub T);

impl<T> Semigroup for First<T> {
    fn append(self, _other: Self) -> Self {
        self
    }
}

// ── Semigroup combinators ─────────────────────────────────────────────────────

/// Reduce a non-empty slice using a left fold (mirrors OCaml's `sconcat`).
/// Returns `None` for empty input — semigroup has no identity to fall back on.
pub fn sconcat<S: Semigroup + Clone>(items: &[S]) -> Option<S> {
    let (head, tail) = items.split_first()?;
    Some(
        tail.iter()
            .cloned()
            .fold(head.clone(), |acc, x| acc.append(x)),
    )
}

/// Recursive version of `sconcat` — right-to-left, equivalent by associativity.
pub fn sconcat_recursive<S: Semigroup + Clone>(items: &[S]) -> Option<S> {
    match items {
        [] => None,
        [x] => Some(x.clone()),
        [head, rest @ ..] => sconcat_recursive(rest).map(|tail| head.clone().append(tail)),
    }
}

/// Check the associativity law: (a ⊕ b) ⊕ c == a ⊕ (b ⊕ c)
pub fn check_associativity<S: Semigroup + PartialEq + Clone>(a: S, b: S, c: S) -> bool {
    a.clone().append(b.clone()).append(c.clone()) == a.append(b.append(c))
}

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

    // ── Min semigroup ──────────────────────────────────────────────────────────

    #[test]
    fn test_min_single_pair() {
        assert_eq!(Min(3).append(Min(7)), Min(3));
        assert_eq!(Min(7).append(Min(3)), Min(3));
    }

    #[test]
    fn test_min_associativity() {
        assert!(check_associativity(Min(3), Min(1), Min(4)));
    }

    #[test]
    fn test_min_sconcat() {
        let nums = [3, 1, 4, 1, 5, 9, 2, 6].map(Min);
        assert_eq!(sconcat(&nums), Some(Min(1)));
    }

    #[test]
    fn test_min_sconcat_empty() {
        let empty: &[Min] = &[];
        assert_eq!(sconcat(empty), None);
    }

    // ── Max semigroup ──────────────────────────────────────────────────────────

    #[test]
    fn test_max_single_pair() {
        assert_eq!(Max(3).append(Max(7)), Max(7));
        assert_eq!(Max(7).append(Max(3)), Max(7));
    }

    #[test]
    fn test_max_associativity() {
        assert!(check_associativity(Max(3), Max(1), Max(4)));
    }

    #[test]
    fn test_max_sconcat() {
        let nums = [3, 1, 4, 1, 5, 9, 2, 6].map(Max);
        assert_eq!(sconcat(&nums), Some(Max(9)));
    }

    #[test]
    fn test_max_sconcat_single() {
        assert_eq!(sconcat(&[Max(42)]), Some(Max(42)));
    }

    // ── First semigroup ────────────────────────────────────────────────────────

    #[test]
    fn test_first_keeps_left() {
        assert_eq!(First("hello").append(First("world")), First("hello"));
    }

    #[test]
    fn test_first_sconcat() {
        let words = [First("first"), First("second"), First("third")];
        assert_eq!(sconcat(&words), Some(First("first")));
    }

    #[test]
    fn test_first_associativity() {
        assert!(check_associativity(First("a"), First("b"), First("c")));
    }

    // ── NonEmptyList semigroup ─────────────────────────────────────────────────

    #[test]
    fn test_nonemptylist_append() {
        let a = NonEmptyList(vec![1, 2]);
        let b = NonEmptyList(vec![3, 4]);
        assert_eq!(a.append(b), NonEmptyList(vec![1, 2, 3, 4]));
    }

    #[test]
    fn test_nonemptylist_associativity() {
        assert!(check_associativity(
            NonEmptyList(vec![1]),
            NonEmptyList(vec![2]),
            NonEmptyList(vec![3]),
        ));
    }

    #[test]
    fn test_nonemptylist_sconcat() {
        let lists = [
            NonEmptyList(vec![1, 2]),
            NonEmptyList(vec![3]),
            NonEmptyList(vec![4, 5]),
        ];
        assert_eq!(sconcat(&lists), Some(NonEmptyList(vec![1, 2, 3, 4, 5])));
    }

    // ── Recursive sconcat ──────────────────────────────────────────────────────

    #[test]
    fn test_sconcat_recursive_min() {
        let nums = [3, 1, 4, 1, 5].map(Min);
        assert_eq!(sconcat_recursive(&nums), Some(Min(1)));
    }

    #[test]
    fn test_sconcat_recursive_first() {
        let words = [First("alpha"), First("beta"), First("gamma")];
        assert_eq!(sconcat_recursive(&words), Some(First("alpha")));
    }

    #[test]
    fn test_sconcat_recursive_empty() {
        let empty: &[Max] = &[];
        assert_eq!(sconcat_recursive(empty), None);
    }

    #[test]
    fn test_sconcat_and_recursive_agree() {
        // By associativity, both folds must give the same result
        let nums = [3, 1, 4, 1, 5, 9, 2, 6].map(Min);
        assert_eq!(sconcat(&nums), sconcat_recursive(&nums));
    }
}

(* A semigroup is a set with an associative binary operation.
   Like a monoid but without requiring an identity element.
   Weaker but more widely applicable. *)

module type SEMIGROUP = sig
  type t
  val append : t -> t -> t
  (* Law: append (append a b) c = append a (append b c) *)
end

(* NonEmpty list semigroup — note: no empty! *)
module NonEmptyList : SEMIGROUP with type t = int list = struct
  type t = int list
  let append = ( @ )
end

(* Min semigroup — take the smaller *)
module MinSemigroup : SEMIGROUP with type t = int = struct
  type t = int
  let append = min
end

(* Max semigroup — take the larger *)
module MaxSemigroup : SEMIGROUP with type t = int = struct
  type t = int
  let append = max
end

(* First semigroup — always keep the first *)
module FirstSemigroup : SEMIGROUP with type t = string = struct
  type t = string
  let append a _ = a
end

(* Reduce non-empty list with semigroup *)
let sconcat (module S : SEMIGROUP) lst =
  match lst with
  | []     -> failwith "sconcat: empty list"
  | x :: xs -> List.fold_left S.append x xs

let () =
  let nums = [3; 1; 4; 1; 5; 9; 2; 6] in
  Printf.printf "min of nums: %d\n" (sconcat (module MinSemigroup) nums);
  Printf.printf "max of nums: %d\n" (sconcat (module MaxSemigroup) nums);

  let words = ["first"; "second"; "third"] in
  Printf.printf "first word: %s\n" (sconcat (module FirstSemigroup) words);

  (* Verify associativity *)
  let a = 3 and b = 1 and c = 4 in
  assert (MinSemigroup.append (MinSemigroup.append a b) c =
          MinSemigroup.append a (MinSemigroup.append b c));
  Printf.printf "Associativity law holds\n"

✓ Tests Rust test suite

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

    // ── Min semigroup ──────────────────────────────────────────────────────────

    #[test]
    fn test_min_single_pair() {
        assert_eq!(Min(3).append(Min(7)), Min(3));
        assert_eq!(Min(7).append(Min(3)), Min(3));
    }

    #[test]
    fn test_min_associativity() {
        assert!(check_associativity(Min(3), Min(1), Min(4)));
    }

    #[test]
    fn test_min_sconcat() {
        let nums = [3, 1, 4, 1, 5, 9, 2, 6].map(Min);
        assert_eq!(sconcat(&nums), Some(Min(1)));
    }

    #[test]
    fn test_min_sconcat_empty() {
        let empty: &[Min] = &[];
        assert_eq!(sconcat(empty), None);
    }

    // ── Max semigroup ──────────────────────────────────────────────────────────

    #[test]
    fn test_max_single_pair() {
        assert_eq!(Max(3).append(Max(7)), Max(7));
        assert_eq!(Max(7).append(Max(3)), Max(7));
    }

    #[test]
    fn test_max_associativity() {
        assert!(check_associativity(Max(3), Max(1), Max(4)));
    }

    #[test]
    fn test_max_sconcat() {
        let nums = [3, 1, 4, 1, 5, 9, 2, 6].map(Max);
        assert_eq!(sconcat(&nums), Some(Max(9)));
    }

    #[test]
    fn test_max_sconcat_single() {
        assert_eq!(sconcat(&[Max(42)]), Some(Max(42)));
    }

    // ── First semigroup ────────────────────────────────────────────────────────

    #[test]
    fn test_first_keeps_left() {
        assert_eq!(First("hello").append(First("world")), First("hello"));
    }

    #[test]
    fn test_first_sconcat() {
        let words = [First("first"), First("second"), First("third")];
        assert_eq!(sconcat(&words), Some(First("first")));
    }

    #[test]
    fn test_first_associativity() {
        assert!(check_associativity(First("a"), First("b"), First("c")));
    }

    // ── NonEmptyList semigroup ─────────────────────────────────────────────────

    #[test]
    fn test_nonemptylist_append() {
        let a = NonEmptyList(vec![1, 2]);
        let b = NonEmptyList(vec![3, 4]);
        assert_eq!(a.append(b), NonEmptyList(vec![1, 2, 3, 4]));
    }

    #[test]
    fn test_nonemptylist_associativity() {
        assert!(check_associativity(
            NonEmptyList(vec![1]),
            NonEmptyList(vec![2]),
            NonEmptyList(vec![3]),
        ));
    }

    #[test]
    fn test_nonemptylist_sconcat() {
        let lists = [
            NonEmptyList(vec![1, 2]),
            NonEmptyList(vec![3]),
            NonEmptyList(vec![4, 5]),
        ];
        assert_eq!(sconcat(&lists), Some(NonEmptyList(vec![1, 2, 3, 4, 5])));
    }

    // ── Recursive sconcat ──────────────────────────────────────────────────────

    #[test]
    fn test_sconcat_recursive_min() {
        let nums = [3, 1, 4, 1, 5].map(Min);
        assert_eq!(sconcat_recursive(&nums), Some(Min(1)));
    }

    #[test]
    fn test_sconcat_recursive_first() {
        let words = [First("alpha"), First("beta"), First("gamma")];
        assert_eq!(sconcat_recursive(&words), Some(First("alpha")));
    }

    #[test]
    fn test_sconcat_recursive_empty() {
        let empty: &[Max] = &[];
        assert_eq!(sconcat_recursive(empty), None);
    }

    #[test]
    fn test_sconcat_and_recursive_agree() {
        // By associativity, both folds must give the same result
        let nums = [3, 1, 4, 1, 5, 9, 2, 6].map(Min);
        assert_eq!(sconcat(&nums), sconcat_recursive(&nums));
    }
}

Deep Comparison

OCaml vs Rust: Semigroup

Side-by-Side Code

OCaml

module type SEMIGROUP = sig
  type t
  val append : t -> t -> t
end

module MinSemigroup : SEMIGROUP with type t = int = struct
  type t = int
  let append = min
end

module FirstSemigroup : SEMIGROUP with type t = string = struct
  type t = string
  let append a _ = a
end

let sconcat (module S : SEMIGROUP) lst =
  match lst with
  | []      -> failwith "sconcat: empty list"
  | x :: xs -> List.fold_left S.append x xs

Rust (idiomatic)

pub trait Semigroup {
    fn append(self, other: Self) -> Self;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Min(pub i64);

impl Semigroup for Min {
    fn append(self, other: Self) -> Self {
        Min(self.0.min(other.0))
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct First<T>(pub T);

impl<T> Semigroup for First<T> {
    fn append(self, _other: Self) -> Self { self }
}

pub fn sconcat<S: Semigroup + Clone>(items: &[S]) -> Option<S> {
    let (head, tail) = items.split_first()?;
    Some(tail.iter().cloned().fold(head.clone(), |acc, x| acc.append(x)))
}

Rust (functional/recursive)

pub fn sconcat_recursive<S: Semigroup + Clone>(items: &[S]) -> Option<S> {
    match items {
        [] => None,
        [x] => Some(x.clone()),
        [head, rest @ ..] =>
            sconcat_recursive(rest).map(|tail| head.clone().append(tail)),
    }
}

Type Signatures

Concept	OCaml	Rust
Trait/signature	`module type SEMIGROUP`	`trait Semigroup`
Operation	`val append : t -> t -> t`	`fn append(self, other: Self) -> Self`
Instance selection	First-class module `(module MinSemigroup)`	Generic type parameter `<S: Semigroup>`
Reduce function	`sconcat : (module SEMIGROUP) -> 'a list -> 'a`	`fn sconcat<S: Semigroup + Clone>(items: &[S]) -> Option<S>`
Empty-list failure	`failwith "sconcat: empty list"`	`Option::None`

Key Insights

First-class modules → generics: OCaml passes modules as values at runtime; Rust resolves the instance at compile time via generics — zero runtime overhead.

Newtypes solve coherence: Rust cannot have two Semigroup impls for i64 (one for Min, one for Max). Newtypes (Min(i64), Max(i64)) give each instance a distinct type, making both valid and co-existing.

**Option instead of exceptions:** OCaml's failwith for empty input is a runtime panic; Rust's Option<S> return type forces callers to handle the empty case at compile time.

Associativity enables both fold directions: The iterative (fold_left) and recursive (right-associative) versions of sconcat must agree by the semigroup law — the test test_sconcat_and_recursive_agree verifies this directly.

Ownership semantics: append(self, other: Self) consumes both arguments. This is natural for newtypes wrapping Copy types (Min, Max) and forces explicit Clone when operating on slices.

When to Use Each Style

Use idiomatic Rust when: reducing a slice in a hot path — split_first + fold is a single iterator pass with no recursion overhead.

Use recursive Rust when: mirroring an OCaml original for pedagogical comparison, or when the right-associative fold is semantically meaningful (e.g., building a right-associative data structure).

Exercises

Implement a NonEmptyVec<T> type and give it a Semigroup instance (concatenation); verify that unlike Vec, the semigroup has no identity element so it cannot form a monoid.

Define a Max<T: Ord> and Min<T: Ord> semigroup (not monoid — no identity for unbounded types) and implement sconcat over a non-empty list to find the maximum/minimum.

Implement the free semigroup: a non-empty list type, and prove that any semigroup homomorphism from it is uniquely determined by the image of each generator.

Open Source Repos

functional-rust

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

Rust