028 — Sorting a List of Lists According to Length
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
sort_by_key and sort_by with custom comparison functionsHashMap<usize, usize> for the secondary sortsort_by_key(|l| l.len()) for length-based sorting and a HashMap<usize, usize> frequency map for the secondary frequency sortCode Example
#![allow(clippy::all)]
// Placeholder — pending conversionKey Differences
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.sort_by_key is stable. OCaml's List.sort is also stable. Both preserve relative order of equal elements.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.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.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)]
// Placeholder — pending conversionDeep 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
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))).sort_by_length_desc(lists: &mut Vec<Vec<i32>>) that sorts longest-first using sort_by_key(|l| std::cmp::Reverse(l.len())).sort_by(|a, b| a.len().cmp(&b.len()).then_with(|| a.cmp(b))).map → sort → map — annotate each list with its frequency, sort, then strip the annotation.