ExamplesBy LevelBy TopicLearning Paths
1124 Intermediate
← 11241125 →

List.sort — Sort with Custom Comparator

Functional Programming

Tutorial

The Problem

Sort a list of strings in three ways: lexicographically, by length, and in descending order. Implement a generic sort_with that accepts a custom comparator, mirroring OCaml's List.sort.

🎯 Learning Outcomes

  • • How OCaml's List.sort cmp xs maps to Rust's slice::sort_by(|a, b| cmp(a, b))
  • • Pass comparison functions as closures in both languages
  • • Chain comparators: sort by length first, then alphabetically to break ties

    • Code Example

    #![allow(clippy::all)]
//! 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]);
    }
}

    Key Differences

  • In-place vs. persistent: OCaml's List.sort returns a new sorted list (lists are immutable); Rust sort_by sorts in place — the sort_with wrapper clones first to match OCaml semantics
  • Comparator type: OCaml comparators return int (negative/zero/positive); Rust uses std::cmp::Ordering enum — same semantics, different representation
  • Stability: Both List.sort and Rust's sort_by are stable (preserve relative order of equal elements)

    • OCaml Approach

    List.sort String.compare words uses the built-in string comparison. List.sort (fun a b -> compare (String.length a) (String.length b)) words uses an anonymous function. OCaml's sort is guaranteed stable; Rust's sort_by is also stable.

    Full Source

    #![allow(clippy::all)]
//! 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]);
    }
}
    ✓ 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]);
    }
}

    Exercises

  • Implement sort_by_key that takes a key extraction function f: Fn(&T) -> K where K: Ord, mirroring OCaml's List.sort_uniq
  • Sort a list of (String, i32) pairs: first by the integer descending, then by string ascending
  • Implement is_sorted that checks whether a slice is already sorted with respect to a given comparator

    • Open Source Repos

    functional-rust

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

    Rust