Idiomatic Monads in Rust
varkor.github.io
varkor.github.io
I wonder, were the Rust community be given the same power as the Haskell community, would they use it to create a complex more advanced idiomatic Rust that you could only read and understand after months of training?
There is this weird phenomenon in Haskell, I attribute it to Haskell having a syntax that feels limiting, but a type system that seems almost limitless.
There are two branches of idiomatic Haskell. One is the style anyone would recognize as generic "functional programming" and would be able to work with and be productive after a week or two of practice.
The other is where a dozen language features are enabled, and the latest and greatest utility libraries are imported and Haskell shows itself to be as flexible and alienating as Lisp. An expert can wield extreme expression under purity and safety. A beginner stands no chance.
It would be interesting to see more expressive power come to Rust. But it would be a bad thing if it would come at the cost of being beginner friendly. Rust might be challenging to write as a beginner due to the borrow checker, but at least it's easy enough to read.
The functional people have been able to hammer Rust into a functional language, sort of. Now they want a Haskell-like "do" construct so they can get imperative sequentiality back. Is that right?
I'm not a huge fan of extensible languages. I've had to debug LISP code written by others.
Not really, in that even before the blog gets to do notation, it depends on features that don't exist yet: generic associated types, which are RFC-accepted but not yet implemented, and associated traits, which haven't even been proposed. For now the whole thing is just a sketch. However, since associated traits aren't critical to the design (and would be a good feature to add anyway), at least some version of it will presumably be implementable in the future.
Overall, Rust has always been inspired by functional languages to some extent, e.g. Rust traits are based on Haskell typeclasses, and Rust has pattern matching and full type inference. But I don't see `Monad` ever becoming idiomatic. I also don't see `do` notation being accepted, because its use cases largely overlap with other features, namely async/await and generators.
On the other hand, it would require only minor changes to generators to allow implementing `do` notation on top of them, something I'm highly interested in mainly just because I want to prove it's possible. ;p
Appreciate the pragmatism =)
I personally want to see examples of real Rust code that has a problem that this solves. I get monads, I like monads in Haskell, but I'm unconvinced that the additional complexity is worth it in Rust.
There was functional extremism in Tony Morris and his scalaz pet project, but Scala was already doomed.
Of course, these are all things Rust has seemed to avoid and hopefully continues to avoid.
Was? Last I heard, Dotty is ongoing and will transition into Scala 3.
I like to think of Scala as the C++ of the JVM world. It's a complex language with a lot of features, but it can be extremely powerful if you know what idioms to use and where to use them. For example, template abuse in C++ is akin to implicit abuse in Scala.
Maybe this is something that helped grow Go's popularity by being simpler ? (I don't know, just wondering)
But, on the other hand, a balance has to be found if Rust ever want to be widely adopted. Let's be honest 2s here, Rust is already hard enough to learn for the average developer, adding higher order function on top of that will not help adoption.
IMHO, right now Rust the just enough amount of complexity to still be interesting to the majority. It really depends on who Rust want to target in the long run.
Making things compact and focused helps. Of mixed-approach languages, I see Kotlin's approach to integrating FP as more successful.
I think it is a matter of choice of audience. If you want pure functional languages, there are plenty that will rock your boat (Haskell, OCaml ...).
But, to my mind, I see Rust as a somewhat "modernised" C/C++ with, like Python, the most interesting and accessible parts of FP backed in. It is a balance and it is fragile. So, as I said, I hope that Rust will keep that fine line.
All that said, it only is my opinion, I might be wrong and the wider audience might be ready for "harder" FP. But I doubt it.
With C++, I can't say the same is true. Some libraries try to alleviate that, of course.
The influence of "FP" on rust is really more like the influence of Haskell's type system. Rust is pretty far from a functional language but it does share a lot of type system features with Haskell: type classes, sum and product types, HM type inference
Haskell and Rust are different enough that this is definitely a concern. Lazy evaluation and GC used throughout, vs. eager evaluation in a language which uses affine typing and regions to avoid GC... I can see how general monads might not work very well, and the OP does touch on this a little bit.
This is probably not relevant, but as a professional Scala programmer, I find higher-kinded types absolutely indispensable. Without them, writing truly generic (and imo, beautiful) code is almost impossible. Programming with higher-kinded types does really feel like some "next level shit." higher-kinded types are to types as first-order functions are functions: the natural and logical extension that unlocks simplicity, genericity, and beauty.
There isn't so much a rationale against them, but rather, nobody has put forward a coherent proposal for them. Changes only happen when proposals are made and accepted, and there's never really been one for HKT.
That said, there are arguments that apply fairly generally that would apply there too, namely "is the additional complexity worth it"?
There are also questions about ambiguities with respect to default parameters. If you have
struct Foo<A = i32>(A);
fn double_inner<M: Monad<u64>>(m: M) -> M { m.bind(|x| M::unit(x * 2)) }
Which takes anything wrapping an integer and doubles it, whether it’s an option or result or iterator.
edit: If the main point of the article is to show that 'monads are feasible in rust' shouldn't you not be assuming a bunch of language features exist that don't?
When not taken out of context, I don't think it's misleading at all.
> You see, there’s a problem with talking about whether monads would be useful or not, and it’s this: there are a large number of design challenges to overcome to have any hope of implementing them at all — to the best of my knowledge, there currently exists no realistic (that is, practical) design for monads in Rust. In fact, there are so many obstacles that some people express doubt that it’s even possible.
> In general, I don’t think it’s worth talking about the virtue of a language feature if we think there’s no way we could actually implement it. However, I think there are arguments to be made in favour of higher-level abstractions in Rust. Thus, to facilitate discussion, I want to demonstrate that monads are feasible in Rust.
Except if the main point is "monads are feasible in rust if we add these features".
This is just showing imaginary syntax though, it doesn't speak at all to whether implementing these features is actually possible. Just because you make up some syntax doesn't mean it can actually be done (or how difficult it is etc)
That was my first reading, your reading didn't occur to me, so I don't see that the title is especially misleading.
Support for monads in Rust is not possible to be added easily to the language, nor is it particularly probable. The features that come with the imagined syntax in the blog post are non-trivial additions to the type system.
Isn't it supposed to lift function as below:
class Functor f where map :: (a -> b) -> f a -> f b
instead of: class Functor f where map :: f a -> (a -> b) -> f b
You can translate one into the other easily
map' :: (a -> b) -> f a -> f b
map' i j = map'' j i
map'' :: f a -> (a -> b) -> f b
map'' m n = map' n m map' = flip map''
map'' = flip map'It's only a matter of taste or convenience. Haskell is a curried language, so you put the callback first to help partial application, and reversing the order is just a `flip` away.
Rust is uncurried and uses a C-style syntax, so you generally put lambdas in tail position, for a more block-y usage:
foo.bar(x, |y| {
// body
}); map :: Functor m => m a -> (a -> b) -> m b
ap :: Applicative m => m a -> m (a -> b) -> m b
bind :: Monad m => m a -> (a -> m b) -> m b doStuff >>= (\a ->
doMoreStuff >>= (\b ->
doEvenMoreStuff >>= (\c ->
-- Ad nauseam.
)
)
)
Either way, depending on the compiler making one particular optimisation just so that your code works seems rather fragile to me.
[1]: https://www.lua.org/pil/6.3.html
[2]: https://wiki.tcl-lang.org/page/tailcall
[3]: https://perldoc.perl.org/functions/goto.html
[4]: Which was used in a C-family language I can't remember.
In fact, the main reason to have a keyword like `become` is to signal to the compiler to do this kind of analysis, because it's so easy to accidentally break the ability to do TCO when you can't lean on a GC to clean things up later.
Anyway, I understand.
> I am going to be assuming some familiarity with monads (and to a certain extent, do notation). There are enough introductions to monads out there as it is.
For those who hadn't seen this before, here's an explanation: https://stackoverflow.com/questions/3870088/a-monad-is-just-...
But I'll give it a go, I suppose. A functor is a type that represents turning something into something else. For example, for example turning a List<Int> into a List<Double>.
A monad is a functor that also has a bind or flatMap method attached to it. Both essentially allow you flatten or "chain" the values inside. So the monad defines a way to map things (inherited from functors), and flatten things (via bind or flatMap depending on how you want to define it). Also you need applicatives, which is just a way to box things. i.e turning a Int into a List<Int>.
There are also some laws associated with them, but you probably get the idea.
Examples of useful monads: lists, options, futures, database transactions, logging, parsing, etc.
Applicative functions do have that property, but their key attribute is the ability to two things together, e.g. turning a List<Int> and a List<Double> into a List<Pair<Int,Double>>. A functor which also has the ability to put arbitrary things into the functor context, but not the ability to combine two contexts, is sometimes referred to as a pointed functor. (There is no official Haskell typeclass for pointed functors; the main reason, besides historical baggage, is that non-applicative pointed functors don't have any real laws aside from the ones which apply to functors.)
Applicatives are sufficient for sequencing effects but the List<Double> in the previous example can't depend on the Int values in the List<Int>. This is great for static analysis of effects but it limits the kinds of programs you can write to those whose effects are known in advance. A monad lifts this restriction and allows effects (not just values) to be computed dynamically from the values of prior effects.
Finite[1] applicative parsers can only parse context-free languages. Monadic parsers, on the other hand, can handle context-sensitive languages (without resorting to an infinite set of production rules).
[1] https://byorgey.wordpress.com/2012/01/05/parsing-context-sen...
Personally, I think that monads are a sore spot for functional programmers, because they are the crux of why FP runs into difficulties in the real world when dealing with things like mutable state, side effects and logic that happens over multiple steps (imperatively).
Here is a relatively nontechnical discussion about how monads bridge functional and imperative programming, by treating IO sort of like an imaginary number that can be passed along as a black box until it can finally be computed:
Instead monads are used to unify the foundation of many types: options, lists, trees, etc. Also monads are really nice for futures and parsers.
The point I’m trying to make I guess is that monads are very useful for other things than dealing with impurity, which I think a lot of people just learning them miss.
So there shouldn't be any extra abstraction cost. And any actual cost shouldn't be any larger than it is for traits generally.
I believe most of the controversy in this space is about language complexity cost.