Category Theory for Programmers hopeless in Rust?

It’s called a “challenge” for a reason.

A good starting point however would be to move from Rust’s function trait to some (appropriate) concrete function type. That could be Box<dyn Fn(A) -> B>. Or maybe in better analogy to the typical GCd (and shared) approach of the comparison to Haskell, use Rc<dyn Fn(A) -> B>. (If you want to have it particularly easy, then work with Box<dyn FnMut(A) -> B>, and you can even skip the requirement for interior mutability.) Also as another hint: You shouldn’t need any static variables, and in fact trying to use a static should only make it harder since generic statics don’t exist in Rust.

With that, given interior mutability and non-pureness is easily available in Rust, it might end up even easier to write memoize here, compared to Haskell… where you’d need to “unsafely” encapsulate the side-effects around the memoization process (and possibly worry about thread-safety of the result, too).

Just like in Haskell, you’ll also need to introduce some trait constraints to be able to do the memoization. For the input type you will need Eq and furthermore something like Ord or Hash in order to be able to use an appropriate map type and for the output since Rust cannot support duplicating values of arbitrary types, you’ll need e.g. Clone to be able to do that.

6 Likes