Worstsort yet again: polymorphic recursion

A long time ago, I wrote a couple of posts about a maximally slow (but still non-pathological) sorting algorithm which I’d tried to port to Rust. It compiled fine, until I tried to write a test for it and it suddenly blew up a recursion limit when trying to compile it. Eventually I realised this was due to Rust’s usage of monomorphisation meaning that it couldn’t statically compile infinitely many different instances of the function each time we wanted a version for a more nested list type. I was somewhat happy with that explanation, but I was left a little confused about why Brent Yorgey’s Haskell implementation worked fine. I concluded:

So, there are two key questions: why was this not a problem for Haskell, and is there a way to get round it in Rust? At the moment, I don’t know! I hope to get some free time to investigate this at some point, and I’ll definitely write up whatever I find on here.

That day has, apparently, and by complete chance, finally come, when I stumbled upon the key phrase: “polymorphic recursion”. Wikipedia defines it as “a recursive parametrically polymorphic function where the type parameter changes with each recursive invocation made, instead of staying constant”. In the case of Worstsort, the generic type is changing with each call from T or a (in the Rust and Haskell respectively) to &mut [T] or [a]. It’s actually mentioned in Brent Yorgey’s original post in an aside that I must have glossed over at the time, or not thought of it as a set term with a particular technical meaning. But the other day, somewhere, I encountered a link to a StackOverflow question (I forget where now) asking about polymorphic recursion in Rust and the penny dropped that this is the name of the property that’s missing from Rust. It seems to be an issue that a few people have run into: there’s an issue that’s been open for a while asking for better error messages (possibly even including the term!) when the compiler detects it, and there is a steady stream of other issues being marked as duplicates of it.

My initial thoughts now I revisit this 6 years later is that there’s nothing intrinsic to Rust’s type system that would prevent this from being compiled, and it’s more an implementation artifact. However, it definitely feels against the spirit of Rust to wrap all the type information up somewhere behind indirection and let functions work on pointers to things. I wonder if it’d be possible to work around it at the programmer level somehow, although since it’d all have to be at run-time you’d be working entirely round the type checker. Another side project to look into at some point I suppose.