1124 Intermediate

List.sort — Sort with Custom Comparator

Functional Programming

Tutorial

The Problem

Sort a list of strings in three different ways: lexicographically, by string length (with ties broken alphabetically), and in descending order. The core challenge is implementing a generic sort_with function that accepts a custom comparator, directly mirroring the signature and behavior of OCaml's List.sort. This example demonstrates how first-class comparison functions enable flexible, reusable sorting without duplicating traversal logic.

🎯 Learning Outcomes

• How OCaml's List.sort cmp xs maps to Rust's slice::sort_by(|a, b| cmp(a, b)) and why the comparator return type differs

• How to pass comparison closures as arguments in both languages, and the trait bounds (Fn(&T, &T) -> Ordering) Rust requires

• How to compose and chain comparators in Rust using .then() on Ordering — equivalent to the OCaml pattern compare (key a) (key b)

• The distinction between in-place mutation (Rust slices) and persistent return values (OCaml lists), and how a clone-first wrapper reconciles the two models

• Why both List.sort and Rust's sort_by guarantee stability, and what that means for tie-breaking

Code Example

pub fn sort_strings<'a>(words: &[&'a str]) -> Vec<&'a str> {
    let mut result = words.to_vec();
    result.sort();
    result
}

let words = ["banana"; "apple"; "cherry"; "date"]

(* Idiomatic: sort lexicographically using String.compare *)
let sorted = List.sort String.compare words

(* Sort by string length, ties broken lexicographically *)
let by_length = List.sort (fun a b ->
  compare (String.length a) (String.length b)) words

(* Sort in descending order by reversing the comparator *)
let descending = List.sort (fun a b -> String.compare b a) words

Key Differences

Comparator return type: OCaml comparators return int (negative/zero/positive), following the C convention; Rust uses the std::cmp::Ordering enum — same three-way semantics expressed as a typed value rather than a numeric convention.

In-place vs. persistent: OCaml's List.sort returns a new list because lists are immutable; Rust's sort_by sorts the slice in place, requiring an explicit .to_vec() clone to achieve value-returning behavior.

Comparator chaining: OCaml typically chains via if compare_first = 0 then compare_second else compare_first; Rust provides .then() and .then_with() on Ordering, making multi-key comparisons concise and branch-free.

Trait bounds vs. structural typing: OCaml accepts any function of the right type automatically; Rust requires the closure to implement Fn(&T, &T) -> std::cmp::Ordering, which the compiler enforces at the call site.

OCaml Approach

OCaml's List.sort takes a comparison function returning a negative integer, zero, or a positive integer — the same convention as C's qsort. For lexicographic order, String.compare is passed directly as a first-class function value. For length-based ordering, an anonymous function fun a b -> compare (String.length a) (String.length b) extracts the key before delegating to the polymorphic compare. Descending order simply reverses the argument order: fun a b -> String.compare b a. OCaml lists are immutable, so List.sort always returns a new list; no mutation is observable at the call site.

Full Source

#![allow(dead_code)]
//! List.sort — Sort with Custom Comparator
//! See example.ml for OCaml reference
//!
//! OCaml's `List.sort cmp xs` sorts using a comparison function that returns negative/zero/positive.
//! Rust's `slice::sort_by` takes an `Ordering`-returning comparator.

/// Sort a slice of strings lexicographically (ascending).
/// Mirrors OCaml: `List.sort String.compare words`
pub fn sort_strings<'a>(words: &[&'a str]) -> Vec<&'a str> {
    let mut result = words.to_vec();
    result.sort();
    result
}

/// Sort by string length (ascending), ties broken by lexicographic order.
/// Mirrors OCaml: `List.sort (fun a b -> compare (String.length a) (String.length b)) words`
pub fn sort_by_length<'a>(words: &[&'a str]) -> Vec<&'a str> {
    let mut result = words.to_vec();
    result.sort_by(|a, b| a.len().cmp(&b.len()).then(a.cmp(b)));
    result
}

/// Sort in descending lexicographic order.
/// Mirrors OCaml: `List.sort (fun a b -> String.compare b a) words`
pub fn sort_descending<'a>(words: &[&'a str]) -> Vec<&'a str> {
    let mut result = words.to_vec();
    result.sort_by(|a, b| b.cmp(a));
    result
}

/// Generic sort with a custom comparator — mirrors OCaml's `List.sort f xs`.
pub fn sort_with<T: Clone, F>(items: &[T], compare: F) -> Vec<T>
where
    F: Fn(&T, &T) -> std::cmp::Ordering,
{
    let mut result = items.to_vec();
    result.sort_by(compare);
    result
}

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

    #[test]
    fn test_sort_strings() {
        let words = vec!["banana", "apple", "cherry", "date"];
        assert_eq!(sort_strings(&words), vec!["apple", "banana", "cherry", "date"]);
    }

    #[test]
    fn test_sort_by_length() {
        let words = vec!["banana", "apple", "cherry", "date"];
        // "date"(4), "apple"(5), "banana"(6), "cherry"(6) — ties broken alphabetically
        assert_eq!(sort_by_length(&words), vec!["date", "apple", "banana", "cherry"]);
    }

    #[test]
    fn test_sort_descending() {
        let words = vec!["banana", "apple", "cherry", "date"];
        assert_eq!(sort_descending(&words), vec!["date", "cherry", "banana", "apple"]);
    }

    #[test]
    fn test_sort_empty() {
        let empty: Vec<&str> = vec![];
        assert_eq!(sort_strings(&empty), Vec::<&str>::new());
    }

    #[test]
    fn test_sort_with_custom() {
        let nums = vec![3i32, 1, 4, 1, 5, 9, 2, 6];
        let sorted = sort_with(&nums, |a, b| a.cmp(b));
        assert_eq!(sorted, vec![1, 1, 2, 3, 4, 5, 6, 9]);
    }

    #[test]
    fn test_sort_with_reverse() {
        let nums = vec![3i32, 1, 4, 1, 5];
        let sorted = sort_with(&nums, |a, b| b.cmp(a));
        assert_eq!(sorted, vec![5, 4, 3, 1, 1]);
    }
}

let words = ["banana"; "apple"; "cherry"; "date"]
let sorted = List.sort String.compare words
let by_length = List.sort (fun a b -> compare (String.length a) (String.length b)) words
let descending = List.sort (fun a b -> String.compare b a) words
let () = List.iter (fun s -> Printf.printf "%s " s) sorted

✓ Tests Rust test suite

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

    #[test]
    fn test_sort_strings() {
        let words = vec!["banana", "apple", "cherry", "date"];
        assert_eq!(sort_strings(&words), vec!["apple", "banana", "cherry", "date"]);
    }

    #[test]
    fn test_sort_by_length() {
        let words = vec!["banana", "apple", "cherry", "date"];
        // "date"(4), "apple"(5), "banana"(6), "cherry"(6) — ties broken alphabetically
        assert_eq!(sort_by_length(&words), vec!["date", "apple", "banana", "cherry"]);
    }

    #[test]
    fn test_sort_descending() {
        let words = vec!["banana", "apple", "cherry", "date"];
        assert_eq!(sort_descending(&words), vec!["date", "cherry", "banana", "apple"]);
    }

    #[test]
    fn test_sort_empty() {
        let empty: Vec<&str> = vec![];
        assert_eq!(sort_strings(&empty), Vec::<&str>::new());
    }

    #[test]
    fn test_sort_with_custom() {
        let nums = vec![3i32, 1, 4, 1, 5, 9, 2, 6];
        let sorted = sort_with(&nums, |a, b| a.cmp(b));
        assert_eq!(sorted, vec![1, 1, 2, 3, 4, 5, 6, 9]);
    }

    #[test]
    fn test_sort_with_reverse() {
        let nums = vec![3i32, 1, 4, 1, 5];
        let sorted = sort_with(&nums, |a, b| b.cmp(a));
        assert_eq!(sorted, vec![5, 4, 3, 1, 1]);
    }
}

Deep Comparison

OCaml vs Rust: List.sort — Sort with Custom Comparator

Side-by-Side Code

OCaml

let words = ["banana"; "apple"; "cherry"; "date"]

(* Idiomatic: sort lexicographically using String.compare *)
let sorted = List.sort String.compare words

(* Sort by string length, ties broken lexicographically *)
let by_length = List.sort (fun a b ->
  compare (String.length a) (String.length b)) words

(* Sort in descending order by reversing the comparator *)
let descending = List.sort (fun a b -> String.compare b a) words

Rust (idiomatic)

pub fn sort_strings<'a>(words: &[&'a str]) -> Vec<&'a str> {
    let mut result = words.to_vec();
    result.sort();
    result
}

Rust (functional — sort_by with custom comparator)

pub fn sort_by_length<'a>(words: &[&'a str]) -> Vec<&'a str> {
    let mut result = words.to_vec();
    result.sort_by(|a, b| a.len().cmp(&b.len()).then(a.cmp(b)));
    result
}

pub fn sort_descending<'a>(words: &[&'a str]) -> Vec<&'a str> {
    let mut result = words.to_vec();
    result.sort_by(|a, b| b.cmp(a));
    result
}

Type Signatures

Concept	OCaml	Rust
Basic sort	`val sort : ('a -> 'a -> int) -> 'a list -> 'a list`	`fn sort_strings<'a>(words: &[&'a str]) -> Vec<&'a str>`
Comparator type	`'a -> 'a -> int` (negative/zero/positive)	`FnMut(&T, &T) -> Ordering`
Return type	New `'a list` (persistent)	`Vec<T>` (new owned vector)
Custom comparator	`List.sort (fun a b -> ...) xs`	`slice.sort_by(\\|a, b\\| ...)`
Stable sort	`List.stable_sort cmp xs`	`slice.sort_by(...)` (stable by default)

Key Insights

Comparator return type: OCaml comparators return int (negative/zero/positive); Rust comparators return std::cmp::Ordering (Less/Equal/Greater). The Ordering type is more explicit and eliminates off-by-one bugs from integer comparisons.

Mutation vs persistence: OCaml's List.sort returns a new list (lists are immutable linked structures). Rust's sort/sort_by mutates a Vec in place — you clone first if you need the original.

Stability: Rust's standard sort/sort_by is guaranteed stable (merge sort). OCaml's List.sort is also stable; List.fast_sort may not be.

Chained comparisons: Rust's Ordering::then / then_with chains multiple sort keys cleanly — equivalent to OCaml's nested compare calls but reads left-to-right without nesting.

Borrowing: The Rust functions take &[&str] (a borrowed slice of borrowed strings) and return Vec<&str> (owned vector of the same borrowed strings). No string data is copied — only the pointers.

When to Use Each Style

**Use sort() when:** sorting types that implement Ord naturally — strings, integers, tuples. Zero boilerplate, same as OCaml's List.sort String.compare.

**Use sort_by(\|a, b\| ...) when:** you need a custom comparator — sorting by a field, reversing order, or chaining multiple criteria. Equivalent to OCaml's List.sort (fun a b -> ...).

**Use sort_by_key(\|x\| ...) when:** sorting by a single extracted key — cleaner than sort_by for simple cases like sort_by_key(\|s\| s.len()).

Exercises

Implement sort_by_key that takes a key extraction function f: Fn(&T) -> K where K: Ord, mirroring OCaml's common idiom List.sort (fun a b -> compare (f a) (f b)) xs. Verify it produces the same output as sort_with with an equivalent comparator.

Sort a list of (String, i32) pairs: first by the integer descending, then by string ascending for ties. Express the comparator using .then() chaining rather than an if expression.

Implement is_sorted_by that takes a slice and a comparator and returns bool — true if every adjacent pair satisfies cmp(a, b) != Ordering::Greater. Write tests covering empty, single-element, ascending, and descending inputs.

Open Source Repos

functional-rust

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

Rust