Implementing a generic Schwartzian transform in Rust for fun and learning

6 min readJul 17, 2025

–

Press enter or click to view image in full size

Photo by Trophim Laptev on Unsplash Do you know about the Schwartzian Transform? If yes, skip this paragraph. If you don’t and before your head straight to Wikipedia, the short version is that it’s an idiom uncovered by Randal L. Schwartz which allows sorting by an expansive key, using a specific comparison.

I hear you say: “yes but we already have [sort\_by\_cached\_key](https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by_cached_key) “. There’s a catch though: the key that’s computed must implement [Ord](https://doc.rust-lang.org/std/cmp/trait.Ord.html).

I stumble into this because I wanted to sort a Vec<Stuff> where Stuff has an expensive fn to_f64(&self) -> f64 function:

use itertools::Itertools;#[derive(Debug)]struct Stuff(f64);impl Stuff {    fn to_f64(&self) -> f64 {        // pretend there are costly        // computations here.        self.0    }}fn main() {    let vs: Vec<Stuff> = vec![Stuff(3.0), Stuff(2.0), Stuff(1.0)];    println!("Unsorted: {:?}", vs);    /*    //  ?? How do we do this ??    let sorted = vs.iter().sorted_by_cached_key(|&s| s.to_f64()).collect_vec();                            ^^^^^^^^^^^^^^^^^^^^ the trait `Ord` is not implemented for `f64`    println!("Sorted: {:?}", sorted);    */}

That does not compile, as Ord is not implemented by f64

Schwartzian transform to the rescue

The above problem is a typical case where reaching to the Schwartzian idiom saves the day. The idea is that you “attach” the sort key to each value (using a tuple is classic) with a straight map, do the sorting and then project it to get back a collection of values, sorted by the key. In Rust, for our f64 key example, here’s what it looks like:

fn main() {    let vs: Vec<Stuff> = vec![Stuff(3.0), Stuff(1.0), Stuff(2.0)];    println!("Unsorted: {:?}", vs);    // Use the Schwartz:    let sorted = vs        .iter()        // Expensive 'to_f64' done only once by item        .map(|s| (s.to_f64(), s))        // The custom sort, just using the key        .sorted_by(|(ka, _), (kb, _)| ka.total_cmp(kb))        // Projecting back to a collection of &Stuff        .map(|(_, s)| s)        .collect_vec();    println!("Sorted: {:?}", sorted);}

This happily prints:

Unsorted: [Stuff(3.0), Stuff(1.0), Stuff(2.0)]Sorted: [Stuff(1.0), Stuff(2.0), Stuff(3.0)]

That could have been the happy ending, if as a Rust beginner, I got caught by my thirst to learn more about Rust.

Ideally I’d like to be able to reach to this pattern each time I need this transformation, without having to type those 3 lines of code.

I want a generic implementation schwartzian that I can call on any Iterator .

Adventures in generics traits

where our protagonist learns many things about Rust in one swoop.

For our Schwartzian transform, and from our example above, we need two fundamental things to perform the transformation:

• A function that given an Item returns the sorting key
• A function that takes two sorting key and return an [Ordering](https://doc.rust-lang.org/std/cmp/enum.Ordering.html) With these two functions or closure, we should be able to re-write our example as:

let sorted = vs.iter()             .schwarzian(|s| s.to_f64(),                         |a,b| a.total_cmp(b)).collect_vec();

And of course, use the schwartzian method on any type of original object and any type of key.

But first, we need to be able to “add the method” to anything that implements [Iterator](https://doc.rust-lang.org/std/iter/trait.Iterator.html).

To start simple, let’s solve the first problem. Let’s say I want to implement a “method” that return the string “Hello” on any type implementing Iterator.

Here’s how to do it:

// Greeter trait needs// the implementor to also implement// Iteratortrait Greeter: Iterator {    fn greet(&self) -> String {        // In here, self is of type Self        // which implements Iterator        "Hello".into()    }}// Implementation is parametrized by a type T,// and is implemented on T as long as T// implements Iterator, respecting the trait contract.impl<T> Greeter for T where T: Iterator {}fn main(){   let vs: Vec<Stuff> = vec![Stuff(3.0), Stuff(1.0), Stuff(2.0)];   // We can now call greet on any Iterator   let hello = vs.iter().greet();   assert_eq!(hello, "Hello");}

With that out of the way, it’s time to implement our generic Schwartzian transform.

The schwartziansignature

Remember, we need to make our transform generic on:

• The type of key the expensive key function produces. Let’s call this type K
• The type of the 2 functions the one that produces a K and the one that takes 2 K values and produces an Ordering . Respectively, let’s call them F (like function..) and O (like ordering) This last point was a bit of learning curve experience for me, asfunctions types in Rust are quite different from C++. In short, the function type must be generic and implement one of theRust function traits. I don’t intend to go into the details of function traits here, so we’ll stick to the safest Fn variant.

With this in mind, plus the blanket implementation technique seen earlier, our Schwartz trait is starting to take shape:

trait Schwartz: Iterator {trait Schwartz: Iterator {    /// Generic on    /// K: The key type    /// F: A function returning a K    /// O: A function ordering the K    ///    /// The returned type implements Iterator (of course)    /// where the Item type is the same as this Self.    fn schwartzian<K, F, O>(self, key: F, ord: O) -> impl Iterator<Item = <Self as Iterator>::Item>    where        // No constraint on K        F: Fn(&Self::Item) -> K, // The Item type from this Iterator        O: Fn(&K, &K) -> Ordering,    {        // Just a placeholder.        // The todo!() macro does not work here, because it doesnt know        // what type of Iterator to pick, as the return type is generic.        // But we know:        std::iter::empty()    }}impl<T> Schwartz for T where T: Iterator {}fn main() {    let vs: Vec<Stuff> = vec![Stuff(3.0), Stuff(1.0), Stuff(2.0)];    println!("Unsorted: {:?}", vs);     // Much nicer!    let sorted = vs        .iter()        .schwartzian(|&v| v.to_f64(), f64::total_cmp)        .collect_vec();    println!("Sorted: {:?}", sorted);

This obviously prints the following:

Unsorted: [Stuff(3.0), Stuff(1.0), Stuff(2.0)]Sorted: []

Implementation

As usual in programming inspired by functional principles with a strong type system, the generic implementation naturally derives from the earlier ad-hoc implementation so here’s the full solution:

use itertools::Itertools;use std::cmp::Ordering;#[derive(Debug)]struct Stuff(f64);impl Stuff {    fn to_f64(&self) -> f64 {        // pretend there are expensive        // computations here.        self.0    }}trait Schwartz: Iterator {    /// Generic on    /// K: The key type    /// F: A function returning a K    /// O: A function ordering the K    ///    /// The returned type implements Iterator (of course)    /// where the Item type is the same as this Self.    fn schwartzian<K, F, O>(self, key: F, ord: O) -> impl Iterator<Item = <Self as Iterator>::Item>    where        // No constraint on K        // Our functions constraints:        F: Fn(&Self::Item) -> K,        O: Fn(&K, &K) -> Ordering,        // we consume self, so its size must be known at compile time        Self: Sized,    {        self.map(|i| (key(&i), i))            .sorted_by(|(ka, _), (kb, _)| ord(ka, kb))            .map(|(_, i)| i)    }}impl<T> Schwartz for T where T: Iterator {}fn main() {    let vs: Vec<Stuff> = vec![Stuff(3.0), Stuff(1.0), Stuff(2.0)];    println!("Unsorted: {:?}", vs);    let sorted = vs        .iter()        .schwartzian(|&v| v.to_f64(), f64::total_cmp)        .collect_vec();    println!("Sorted: {:?}", sorted);}

And that prints as expected:

Unsorted: [Stuff(3.0), Stuff(1.0), Stuff(2.0)]Sorted: [Stuff(1.0), Stuff(2.0), Stuff(3.0)]

Epilogue

Some reflections on what I learned and some pain points

I cannot praise the Rust compiler enough. For some tricky situations, it just told me what to do. For example, I was really scratching my head about the return type for the schwarzian function. I had gone though the pain of defining exactly what type it was from the implementation and was ending up with some monstrosity like:

Map<   std::vec::IntoIter<(K, <Self as Iterator>::Item)>,   impl FnMut((K, <Self as Iterator>::Item)) -> <Self as Iterator>::Item, >

Fortunately, after I removed the return type and kept the implementation, rust literally told me what to do:

Press enter or click to view image in full size

impl Trait as a return type Rust is a life saver.

Implementing this sent me through a good number of rabbit holes. I certainly learned a lot of details about aspects of Rust making this possible. As an example here’s the ordering of the tuple holding the key along side the original value: (key(&value), value).

Can you guess why it’s this way and cannot be the other way around?

The best is to try it for yourself on the Rust playground, and maybe come up with an even better solution.

Let me know in the comments. Got to go eat some crab sticks.