028 Intermediate GitHub

028 — Sorting a List of Lists According to Length

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "028 — Sorting a List of Lists According to Length" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Sorting a list of lists by the length of each sublist (OCaml 99 Problems #28) demonstrates custom comparators — one of the most practical uses of higher-order functions. Key difference from OCaml: 1. **Comparator interface**: OCaml uses `int`

Tutorial

The Problem

Sorting a list of lists by the length of each sublist (OCaml 99 Problems #28) demonstrates custom comparators — one of the most practical uses of higher-order functions. The problem has two parts: sort by length directly, and sort by length frequency (shorter lists whose length appears more often come first).

Custom comparators are everywhere: sorting database records by multiple fields, sorting search results by relevance score, ordering tasks by priority, and comparing compound keys in B-trees. The functional approach passes a comparator function to the sort algorithm, keeping sort logic separate from comparison logic.

🎯 Learning Outcomes

• Use sort_by_key and sort_by with custom comparison functions

• Compute length frequency using a HashMap<usize, usize> for the secondary sort

• Apply stable sorting to preserve relative order of equal-length lists

• Compare the functional (sort_by_key) and imperative (Schwartzian transform) approaches

• Understand why frequency-based sorting requires a two-pass algorithm

• Use sort_by_key(|l| l.len()) for length-based sorting and a HashMap<usize, usize> frequency map for the secondary frequency sort

• Use stable sort to preserve relative order of equal-length lists

Code Example

#![allow(clippy::all)]
// Sort a list of lists by length (OCaml 99 Problems #28) — direct and frequency variants.
use std::collections::HashMap;

pub fn sort_by_length(lists: &[Vec<i32>]) -> Vec<Vec<i32>> {
    let mut v = lists.to_vec();
    v.sort_by_key(|l| l.len());
    v
}

pub fn sort_by_length_freq(lists: &[Vec<i32>]) -> Vec<Vec<i32>> {
    let mut freq: HashMap<usize, usize> = HashMap::new();
    for l in lists {
        *freq.entry(l.len()).or_insert(0) += 1;
    }
    let mut v = lists.to_vec();
    v.sort_by_key(|l| freq[&l.len()]);
    v
}

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

    #[test]
    fn test_sort_by_length() {
        let lists = vec![vec![1, 2, 3], vec![1], vec![1, 2]];
        assert_eq!(sort_by_length(&lists), vec![vec![1], vec![1, 2], vec![1, 2, 3]]);
    }

    #[test]
    fn test_sort_by_length_is_stable() {
        let lists = vec![vec![1, 1], vec![2, 2], vec![3]];
        // both length-2 lists keep their relative order
        assert_eq!(sort_by_length(&lists), vec![vec![3], vec![1, 1], vec![2, 2]]);
    }

    #[test]
    fn test_sort_by_length_freq() {
        let lists = vec![
            vec![1, 2, 3],
            vec![1, 2],
            vec![1, 2, 3, 4],
            vec![1, 2],
            vec![1, 2, 3, 4, 5],
            vec![1, 2],
            vec![1],
        ];
        // lengths 3,2,4,2,5,2,1 -> freq(3)=1, freq(2)=3, freq(4)=1, freq(5)=1, freq(1)=1
        assert_eq!(
            sort_by_length_freq(&lists),
            vec![
                vec![1, 2, 3],
                vec![1, 2, 3, 4],
                vec![1, 2, 3, 4, 5],
                vec![1],
                vec![1, 2],
                vec![1, 2],
                vec![1, 2],
            ]
        );
    }
}

(* Sort By Length *)
(* OCaml 99 Problems #28 *)

let sort_by_length lists =
  List.stable_sort (fun a b -> compare (List.length a) (List.length b)) lists

let sort_by_length_freq lists =
  let freq = Hashtbl.create 16 in
  List.iter
    (fun l ->
       let len = List.length l in
       let count = try Hashtbl.find freq len with Not_found -> 0 in
       Hashtbl.replace freq len (count + 1))
    lists;
  List.stable_sort
    (fun a b -> compare (Hashtbl.find freq (List.length a)) (Hashtbl.find freq (List.length b)))
    lists

(* Tests *)
let () =
  assert (sort_by_length [[1; 2; 3]; [1]; [1; 2]] = [[1]; [1; 2]; [1; 2; 3]]);
  assert (sort_by_length [[1; 1]; [2; 2]; [3]] = [[3]; [1; 1]; [2; 2]]);

  let lists =
    [ [1; 2; 3]; [1; 2]; [1; 2; 3; 4]; [1; 2]; [1; 2; 3; 4; 5]; [1; 2]; [1] ]
  in
  assert (
    sort_by_length_freq lists
    = [ [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]; [1]; [1; 2]; [1; 2]; [1; 2] ]);

  print_endline "✓ OCaml tests passed"

Key Differences

Comparator interface: OCaml uses int-returning comparators (negative/zero/positive). Rust uses Ordering enum (Less/Equal/Greater) with sort_by, or key functions with sort_by_key.

**sort_by_key vs sort_by**: Rust's sort_by_key(f) calls f once per element before sorting (Schwartzian transform under the hood). sort_by(cmp) calls cmp O(n log n) times. OCaml's List.sort calls the comparator O(n log n) times.

Stability: Rust's sort_by_key is stable. OCaml's List.sort is also stable. Both preserve relative order of equal elements.

In-place vs functional: Rust's sort_by_key mutates the Vec. OCaml's List.sort returns a new sorted list.

**sort_by_key vs comparator:** Rust's sort_by_key(|l| l.len()) is cleaner than sort_by(|a, b| a.len().cmp(&b.len())) when the key is simple. OCaml always takes a comparator function.

Stability: Rust's sort_by_key is stable (preserves order of equal elements). OCaml's List.sort is also stable. Use sort_unstable_by_key for better performance when stability is not needed.

**Frequency sort requires HashMap:** The two-pass algorithm (count lengths, then sort by count) uses a HashMap<usize, usize> in Rust. OCaml uses Hashtbl with the same two-pass approach.

OCaml Approach

OCaml's version: List.sort (fun a b -> compare (List.length a) (List.length b)) lists. For frequency sort: compute a frequency map, then List.sort (fun a b -> compare (freq (List.length a)) (freq (List.length b))) lists. OCaml's List.sort takes a comparison function 'a -> 'a -> int where negative means "less than". This is the standard compare-function interface used in C's qsort and Java's Comparator.

OCaml's sort by length: let sort_by_length lists = List.sort (fun l1 l2 -> compare (List.length l1) (List.length l2)) lists. The comparison function takes the lengths and uses compare for ordering. For sort by frequency: first count lengths with a Hashtbl, then sort using the counts as keys. OCaml's List.sort is a merge sort — stable and O(n log n).

Full Source

#![allow(clippy::all)]
// Sort a list of lists by length (OCaml 99 Problems #28) — direct and frequency variants.
use std::collections::HashMap;

pub fn sort_by_length(lists: &[Vec<i32>]) -> Vec<Vec<i32>> {
    let mut v = lists.to_vec();
    v.sort_by_key(|l| l.len());
    v
}

pub fn sort_by_length_freq(lists: &[Vec<i32>]) -> Vec<Vec<i32>> {
    let mut freq: HashMap<usize, usize> = HashMap::new();
    for l in lists {
        *freq.entry(l.len()).or_insert(0) += 1;
    }
    let mut v = lists.to_vec();
    v.sort_by_key(|l| freq[&l.len()]);
    v
}

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

    #[test]
    fn test_sort_by_length() {
        let lists = vec![vec![1, 2, 3], vec![1], vec![1, 2]];
        assert_eq!(sort_by_length(&lists), vec![vec![1], vec![1, 2], vec![1, 2, 3]]);
    }

    #[test]
    fn test_sort_by_length_is_stable() {
        let lists = vec![vec![1, 1], vec![2, 2], vec![3]];
        // both length-2 lists keep their relative order
        assert_eq!(sort_by_length(&lists), vec![vec![3], vec![1, 1], vec![2, 2]]);
    }

    #[test]
    fn test_sort_by_length_freq() {
        let lists = vec![
            vec![1, 2, 3],
            vec![1, 2],
            vec![1, 2, 3, 4],
            vec![1, 2],
            vec![1, 2, 3, 4, 5],
            vec![1, 2],
            vec![1],
        ];
        // lengths 3,2,4,2,5,2,1 -> freq(3)=1, freq(2)=3, freq(4)=1, freq(5)=1, freq(1)=1
        assert_eq!(
            sort_by_length_freq(&lists),
            vec![
                vec![1, 2, 3],
                vec![1, 2, 3, 4],
                vec![1, 2, 3, 4, 5],
                vec![1],
                vec![1, 2],
                vec![1, 2],
                vec![1, 2],
            ]
        );
    }
}

(* Sort By Length *)
(* OCaml 99 Problems #28 *)

let sort_by_length lists =
  List.stable_sort (fun a b -> compare (List.length a) (List.length b)) lists

let sort_by_length_freq lists =
  let freq = Hashtbl.create 16 in
  List.iter
    (fun l ->
       let len = List.length l in
       let count = try Hashtbl.find freq len with Not_found -> 0 in
       Hashtbl.replace freq len (count + 1))
    lists;
  List.stable_sort
    (fun a b -> compare (Hashtbl.find freq (List.length a)) (Hashtbl.find freq (List.length b)))
    lists

(* Tests *)
let () =
  assert (sort_by_length [[1; 2; 3]; [1]; [1; 2]] = [[1]; [1; 2]; [1; 2; 3]]);
  assert (sort_by_length [[1; 1]; [2; 2]; [3]] = [[3]; [1; 1]; [2; 2]]);

  let lists =
    [ [1; 2; 3]; [1; 2]; [1; 2; 3; 4]; [1; 2]; [1; 2; 3; 4; 5]; [1; 2]; [1] ]
  in
  assert (
    sort_by_length_freq lists
    = [ [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]; [1]; [1; 2]; [1; 2]; [1; 2] ]);

  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_sort_by_length() {
        let lists = vec![vec![1, 2, 3], vec![1], vec![1, 2]];
        assert_eq!(sort_by_length(&lists), vec![vec![1], vec![1, 2], vec![1, 2, 3]]);
    }

    #[test]
    fn test_sort_by_length_is_stable() {
        let lists = vec![vec![1, 1], vec![2, 2], vec![3]];
        // both length-2 lists keep their relative order
        assert_eq!(sort_by_length(&lists), vec![vec![3], vec![1, 1], vec![2, 2]]);
    }

    #[test]
    fn test_sort_by_length_freq() {
        let lists = vec![
            vec![1, 2, 3],
            vec![1, 2],
            vec![1, 2, 3, 4],
            vec![1, 2],
            vec![1, 2, 3, 4, 5],
            vec![1, 2],
            vec![1],
        ];
        // lengths 3,2,4,2,5,2,1 -> freq(3)=1, freq(2)=3, freq(4)=1, freq(5)=1, freq(1)=1
        assert_eq!(
            sort_by_length_freq(&lists),
            vec![
                vec![1, 2, 3],
                vec![1, 2, 3, 4],
                vec![1, 2, 3, 4, 5],
                vec![1],
                vec![1, 2],
                vec![1, 2],
                vec![1, 2],
            ]
        );
    }
}

Deep Comparison

OCaml vs Rust: Sort By Length

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Multi-level sort: Sort a Vec<Vec<i32>> first by length, then lexicographically within equal-length groups. Use sort_by(|a, b| a.len().cmp(&b.len()).then(a.cmp(b))).

Reverse sort: Write sort_by_length_desc(lists: &mut Vec<Vec<i32>>) that sorts longest-first using sort_by_key(|l| std::cmp::Reverse(l.len())).

Topological sort by frequency: Given a text document, split into words, group by first letter, and sort those groups by frequency of the first letter across the whole document.

Sort by multiple keys: Implement sorting by (length, alphabetically within same-length groups) using sort_by(|a, b| a.len().cmp(&b.len()).then_with(|| a.cmp(b))).

Schwartzian transform: Implement the Schwartzian transform for the frequency sort: map → sort → map — annotate each list with its frequency, sort, then strip the annotation.

Open Source Repos

functional-rust

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

Rust