# Rust and Pure Functional Programming: Square Peg, Round Hole # Introduction --- For the last few weeks since the announcement of [Rats](https://github.com/rust-rats/rats) we've been fast at work exploring how to write pure FP in Rust. The original strategy based on [this blog post from Michael Snoyman](https://www.fpcomplete.com/blog/monads-gats-nightly-rust/) took us quite far. It works relatively well as far as you know which types you are working with. As soon as you try to write generic code that could work with, say, any `Functor` problems show. In this post we will explore the problems that we've encountered with the current encoding of typeclasses, alternatives we've come up with and the final encoding we are going with (at least until more things break). # Motivation --- Here is a snipped version of our typeclass hierarchy: ```rust pub trait Functor { type Inner; type Outter: Functor; fn fmap<...>(self, ...) -> Self::Outter<...>; } pub trait Apply: Functor { fn apply<...>(self, ...) -> Self::Outter<...>; } pub trait Applicative: Apply { fn pure<...>(...) -> Self::Outter<...>; } ``` It looks nice at a first glance. And we can implement it quite easily for `Option` ```rust impl Functor for Option { type Inner = T; type Outter = Option; fn fmap<...>(self, ...) -> Option<...> { ... } } impl Apply for Option { fn apply<...>(self, ...) -> Option<...> { ... } } impl Applicative for Option { fn pure<...>(...) -> Option<...> { ... } } ``` That looks nice and clean, and usage is equally as simple. ```rust let foo: Option = Option::::pure(0).fmap(|i| i.to_string()); ``` An important topic when talking about typeclasses are laws. The implementation of each typeclass should follow a set of laws for them to be properly formed. Something useful then would be to encode these laws in functions so we can reuse it for different implementations. ```rust fn applicative_homomorphism(a: A, mut f: T::Outter) where T: Applicative, F: Copy + FnMut(A) -> B, // other bounds { assert_eq!(T::pure(a).apply(f), f.apply(T::pure(|mut fun: F| fun(a)))); } ``` Looks nice enough. Sadly it won't work. Let's zoom in to the left side of the `assert_eq!` call: ```rust T::pure(a).apply(f) ``` We know `T: Applicative`, so we are able to call `pure`. What do we know about the return type? Remember, this function doesn't know the concrete implementation of `T`, it should work for any `T` that implements our definition of `Applicative`: ```rust fn pure<...>(...) -> Self::Outter<...>; ``` And where does `Outter` comes from? ```rust pub trait Functor { type Outter: Functor; ... } ``` Finally, what is `apply` expecting? ```rust fn apply<...>(self, Self::Outter<...>) -> Self::Outter<...> { ... } ``` You see the problem? We aren't able to specify that `Outter` from `Applicative` should also be `Apply`, therefore `apply` can't be called on it. We didn't encounter this problem before because we knew we were working with `Option`s. Now all we know is that we have a `T` that implements `Applicative`, and the call top `pure` returns something that is `Functor`, and that's it. This limitation would make this API pretty much useless. If you know the concrete types you are working with upfront you might as well rely on the `std` methods, since most of the functional typeclass concepts are encoded there (even if with other names). What we want is the power of implementing things in terms of typeclasses, and let the user decide which concrete type should be used. But complaining is easy, now it is time to fix it. Notice: Some of these issues were pointed out in the original post we based our implementation, but at the time it was a good starting point for the exploration of the design. # Exploring Solutions --- ### Encoding per Typeclass The obvious solution would be to reencode the the typeclasses as: ```rust pub trait Functor { type Inner; type Outter: Functor; ... } pub trait Apply { type Inner; type Outter: Functor + Apply; ... } pub trait Applicative { type Inner; type Outter: Functor + Apply + Applicative; ... } ``` In this scheme the trait hierarchy is encoded in the associated type instead of the trait itself. Lets see how far it can get us: ```rust fn applicative_homomorphism(a: A, f: F) where T: Applicative + Apply + Functor, F: FnMut(A) -> B, // other bounds { assert_eq!(T::pure(a).apply(T::pure(f)), T::pure(f(a))); } ``` All that changed was the need to specify the full hierarchy on the `T` bounds. That looks good. Again, this won't work, but it is closer to what we want. To understand why that is we need to look how would the `apply` and `pure` signatures look: ```rust trait Apply { type Inner; type Outter: Functor + Apply; fn apply T, T>(self, other: Self::Outter) -> Self::Outter; } trait Applicative { type Inner; type Outter: Functor + Apply + Applicative; fn pure(val: A) -> Self::Outter; } ``` There is no simple way to tell the compiler that the `Self::Outter` from `Applicative` is the same `Self::Outter` from `Apply` and therefore the call to `apply` on the left side of the `assert_eq!` ```rust T::pure(a).apply(T::pure(f)) ``` Fails because it wait a `Apply::Outter` but it is receiving an `Applicative::Outter`. ### Kind Constructors We need to carry forward the information about the compatibility of the types throughout the API. First, let's define a way to indicate that a type is capable of being used as a functor: ```rust pub trait FunctorTy { type Cons; } ``` `Cons` here stands for `type CONStructor` , this is essentialy encoding that a type that is `Functor` must be a type with one type parameter. Next, we need to provide the implementation for `fmap` in a general manner: ```rust pub trait FunctorInstance { type Kind: FunctorTy = Self>; fn fmap(self, f: impl Fn(T) -> B) -> ::Cons; } ``` Not the prettiest, but functional. With this `FunctorTy` can enforce the that a type that is capable if being a functor must provide a `FunctorInstance` of the correct kind: ```rust type Cons: FunctorInstance; ``` Finally, we encode the annotation of Kind through an empty type that is only used as a "type carrier". For example, for `Option` we can do something like: ```rust pub struct OptionKind; impl FunctorTy for OptionKind { type Cons = Option; } impl FunctorInstance for Option { type Kind = OptionKind; fn fmap(self, f: impl Fn(T) -> B) -> Option { self.map(f) } } ``` Well, that's quite a lot of work for something that should be simpler. We will soon see the benefits (especially on the "Generic API Usage" topic). Note: This is pretty much the idea of "type families" that motivates the usage for GAT as a HKT alternative: [http://smallcultfollowing.com/babysteps/blog/2016/11/03/associated-type-constructors-part-2-family-traits/](http://smallcultfollowing.com/babysteps/blog/2016/11/03/associated-type-constructors-part-2-family-traits/) ### Typeclass Hierarchy But did all of this solve our initial problem? How would `Apply` look? ```rust pub trait ApplyTy { type Cons: ApplyInstance + FunctorInstance; } pub trait ApplyInstance { type Kind: ApplyTy = Self>; fn apply(self, f: ::Cons) -> ::Cons where F: Fn(T) -> B; } ``` While that does look really ugly, notice that at the implementation site we can substitute the ugliness for the concrete type: ```rust impl ApplyTy for OptionKind { type Cons = Option; } impl ApplyInstance for Option { type Kind = OptionKind; fn apply(self, f: Option) -> Option where F: Fn(T) -> B { ... } } ``` `Applicative` would be similar. With this we can implement `applicative_homomorphism` as ```rust fn applicative_homomorphism(a: A, f: F) where K: ApplicativeTy + ApplyTy + FunctorTy, F: FnMut(A) -> B, // other bounds { let other_a = ::Cons::::pure(a); let other_f = ::Cons::::pure(f); let foo = other_a.apply(other_f); let bar = ::Cons::::pure(f(a)); assert_eq!(foo, bar); } ``` More verbose and ugly, but it works! We will soon see how we can improve the API. Notice that the encoding of the type in the `Ty` types (i.e. the types ended in `Ty`) needs to contain an instance of the full typeclass hierarchy plus itself. # Ensuring Consistency --- What is more fun than building something? Breaking it! Let's try to define an apply for a type that does not have an implementation of `Functor` ```rust pub struct VecKind; // Oops, I forgot to define Functor impl ApplyTy for VecKind { type Cons = Vec } impl ApplyInstance for Vec { ... } ``` The compiler correctly points out that you do not have a `FunctorInstance` for `Vec`: ```rust error[E0277]: the trait bound `VecKind: FunctorTy` is not satisfied --> src/lib.rs:45:5 | 45 | type Kind = VecKind; | ^^^^^^^^^^^^^^^^^^^^ the trait `FunctorTy` is not implemented for `VecKind` ... 101 | type Kind: ApplyTy + FunctorTy; | -------- required by this bound in `ApplyInstance::Kind` ``` What about passing the wrong kind to the `Instance` types? ```rust pub struct VecKind; impl FunctorTy for VecKind { type Cons = Vec } impl FunctorInstance for Vec { type Kind = OptionKind; // oops //... } ``` Once again, the compiler helps us: ```rust error[E0271]: type mismatch resolving `::Cons == Vec` --> src/lib.rs:45:5 | 21 | type Kind: FunctorTy = Self>; | ---------------- required by this bound in `FunctorInstance::Kind` ... 45 | type Kind = OptionKind; | ^^^^^^^^^^^^^^^^^^^^^^^ expected struct `Vec`, found enum `Option` | = note: expected struct `Vec` found enum `Option` ``` Notice that if you define `Cons` in `FunctorTy` with the wrong type, there is not that can be done (and that's a pro since that's how we encode the `Id` type). # Facilitating Generic API Usage --- If you know the types you are working with beforehand the encoding presented (and in fact, the encoding we started out with) is simple to use: ```rust Option::pure(0i32).fmap(|i| i + 1); // Some(1) ``` But as we've seen above, implementing the same thing generically looks complicated: ```rust fn generic_function(a: A, f: F) where K: ApplicativeTy + ApplyTy + FunctorTy, F: FnMut(A) -> B { let other_a = ::Cons::::pure(a); let foo = other_a.fmap(f); } ``` This is especially true for methods that do not have receives (i.e. `self` parameter) like `pure`. At the call site this function does not look great either: ```rust let foo = generic_function(0i32, |i: i32| i + 1); ``` So we will help out the Rust compiler to identify what we want to do. For each typeclass we will add a module containing the set of functions available to the type: ```rust pub mod functor { pub fn fmap( _: Kind, fa: impl FunctorInstance, f: F, ) -> Kind::Cons where F: FnOnce(A) -> B, { fa.fmap(f) } } pub mod applicative { pub fn pure(_: Kind, value: A) -> Kind::Cons { Kind::Cons::::pure(value) } } ``` Notice that now we pass the `Kind` type as a parameter but never use it, and is only there to help out the type system. Since `Kind` is meant to only carry the associated type information and is indeed never bound we shouldn't get any runtime penalties (but we haven't checked). This way, the `applicative_homomorphism` becomes ```rust fn applicative_homomorphism(kind: Kind, a: A, f: F) where K: ApplicativeTy + ApplyTy + FunctorTy, F: FnMut(A) -> B, // other bounds { let other_a = applicative::pure(kind, a); let other_f = applicative::pure(kind, f); let foo = apply::ap(kind, other_a, other_f); let bar = applicative::pure(kind, f(a)); assert_eq!(foo, bar); } ``` Which is much, much cleaner. At the call site it is as simple as ```rust applicative_homomorphism(OptionKind, 0i32, |i: i32| i + 1); ``` # Practical Considerations --- The API presented above is (almost) exactly the one currently being implemented on the Rats library. The only distinction is what is the signature of the functions we accept for typeclasses like `Apply` and `Functor`. On our implementation the signature receives a reference to the contained type instead of passing by value (`Fn(&A) → B`). We decided this approach was better than forcing types to be `Clone` in for types like `Apply` (think about how you would implement it for `Vec` for instance). # Limitations --- But we are still not there. I'm sure there will still be a lot of corner cases that this API is not suited for. But at the time of this writing this are the two major issues we face: ### Nightly Only I don't see the GAT implementation getting into stable Rust any time soon. There is a fairly strong push to stabilize a version containing only lifetime parameters, but the general case is still up in the air. ### Tooling `rustfmt` doesn't like some of the new syntax introduced by GATs. In particular this: ```rust type Kind: FunctorTy = Self>; ``` Always gets overwritten to ```rust type Kind: FunctorTy; ``` `rust-analyzer` also isn't ready to handle GATs and during development we get a quite limited usage of it, so we end up relying mostly on the write + `cargo check` loop. # Where to Go From Here --- AT this point we have many of the main typeclasses implemented for the basic Rust `std` types, namely `Vec`, `Option`, and `Result`. Now we are focusing on a implementation of functional data types based on these API. In you can find this project under the [ratadata](https://github.com/rust-rats/ratadata) name in our Repos. A first test of fire will be writing a proof of concept `IO` to wrap effectful operations, with a sample usable application (say, something akin to [console4cats](https://console4cats.profunktor.dev/)). # Conclusion --- Rust's type system is fantastic, but it isn't quite as flexible as something like Scala or Haskell. The lack of encodings for HKT out of the box makes writing pure functional code cumbersome. Further, there is a reason why FP focused languages are garbage collected: to efficiently weave the data through these function calls it is much more efficient to pass pointers around and let the memory be managed by your runtime. I believe that as soon as we try to implement any kind of bigger codebase based on this APIs we will need to rely extensively on `Rc`s and `Arc`s. This will probably make the API cumbersome to use, but we will get there when we get there. Thank you [@luizchagasjardim](https://github.com/luizchagasjardim) for reviewing this post. # Prior Work --- [https://github.com/kitsuneninetails/rust-effects](https://github.com/kitsuneninetails/rust-effects) [https://github.com/JasonShin/fp-core.rs](https://github.com/JasonShin/fp-core.rs) [https://github.com/algermissen/rustz](https://github.com/algermissen/rustz) [https://github.com/TeaEntityLab/fpRust](https://github.com/TeaEntityLab/fpRust) [https://github.com/j5ik2o/rust-fp](https://github.com/j5ik2o/rust-fp)