16 ms·
Idiomatic Monads in Rust
- misnome 8y agoMods: Suspecting the fragment part of the URL wasn't meant to be submitted here? It jumps to some nonsensical part of the page...
- sctb 8y agoRemoved. Thanks!
- eatbitseveryday 8y agoThis article might do better by actually explaining what a monad is in layman’s terms, rather than deferring the reader to Wikipedia via a footnote. I read 1/3 of the article hoping to gain an understanding but gave up and didn’t read further :(
- amelius 8y agohttp://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html http://blog.sigfpe.com/2006/08/you-could-have-invented-monad...
- leshow 8y agoThere are a million and a half monad blogs out there. I, for one, am happy not to have to read another "a monad is..." blog post.
- ivanbakel 8y agoThat's because it's a technical article about monad implementation, building on previous technical discussion. The author could spend time explaining what monads are, but that's a notoriously tricky thing to teach, and if you don't understand them fully, the article as a whole won't be worth anything to you anyways.
- eatbitseveryday 8y agoPerhaps the author could have put such a disclaimer? "Note: it is beyond the scope of this blog post to explain what a monad is. Please refer to x,y,z for background material." Anyway, I understand.
- Certhas 8y agoThe article says in the introduction: > 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.
- skocznymroczny 8y agomonad is a monoid in the category of endofunctors
- cesarb 8y ago> monad is a monoid in the category of endofunctors For those who hadn't seen this before, here's an explanation: https://stackoverflow.com/questions/3870088/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-whats-the-problem https://stackoverflow.com/questions/3870088/a-monad-is-just-...
- deathanatos 8y agoThat quote is linked to in the article. (At "Famously", under "Functors".)
- mruts 8y agoThere already are way too many articles explaining monads on the internet. For some reason, it's many bloggers favorite subject. 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.
- nybble41 8y ago> Also you need applicatives, which is just a way to box things. i.e turning a Int into a List<Int>. 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-sensitive-languages-with-applicative/ https://byorgey.wordpress.com/2012/01/05/parsing-context-sen...
- zackmorris 8y agoI agree with eatbitseveryday and don't think that this should have been downvoted. I've tried to learn some of the more esoteric concepts in computer science (like monads, and ycombinators for that matter) but eventually forget how they work each time. 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: https://news.ycombinator.com/item?id=19040455 https://news.ycombinator.com/item?id=19040455
- mruts 8y agoMonads in my experience are less likely used for IO than people think. Of course Haskell developers use monads in this way, but OCaml and Scala programmers generally avoid this. 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.
- mesarvagya 8y agoI am not sure about whether the functor definition in article is correct or not. 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
- ivanbakel 8y agoThe definitions are identical. You could define one in terms of the other by just reversing the arguments.
- mesarvagya 8y agoThe first definition is says it takes a normal function and returns a function in category f. But second definition says it takes a value fa and a function and return fb. Does the order of defining arguments matters or its just a taste of matter? Thanks.
- ivanbakel 8y agoDon't make the mistake of thinking that translating a type signature into written English gives a canonical description of the function. The first definition says "(a -> b) -> f a -> f b" - that is it. 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
- majewsky 8y agoOr, more succinctly, map' = flip map'' map'' = flip map'
- feanaro 8y agoYou're thinking in terms of currying, which Rust doesn't support. If you could partially apply arguments to functions in Rust, your reasoning would be correct, though the functions would still be equivalent since you can define `flip` (as in Haskell).
- leshow 8y agoDoes any of this actually compile? Even with generalised_associated_types enabled I couldn't get the Functor definition to compile with a `trait MapFn...` 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?
- deleted 8y ago[deleted]
- JeremyBanks 8y agoI think the main point of the article isn't exactly "monads are feasible in Rust", but rather, "monads are a viable motivating case for these potential developments in Rust". The author is on the Rust compiler team and has several posts from similar angles.
- leshow 8y agoPretty misleading to write "... I want to demonstrate that monads are feasible in Rust." if that's not actually the case
- estebank 8y agoFeasible as in "can be reasonably added to the language", not as in "can be mimicked with current language features".
- leshow 8y agoThere's no discussion of implementation, we have no idea how "reasonable" an implementation would or wouldn't be. My assumption from reading this is it would require a ton of non trivial additions to the type system
- JeremyBanks 8y agoYou are not the target audience.
- Ericson2314 8y agoRust should get Higher kinded types so these experiments can come up with something practical.
- steveklabnik 8y agoPlease note that these are musings about possible language extensions that would let us express monads; this is not even at the stage of a proposal yet, and we haven’t all agreed that enabling this kind of code is actually useful.
- chenglou 8y agoWhere would you say that Rust core folks stand, regarding usage/overusage of such patterns? Sugar for common unwrappings? Appreciate the pragmatism =)
- steveklabnik 8y agoThe lang team would be in charge of these kinds of features, and I'm not on it, so I can't totally say. There are certainly members who do want this stuff. However, community sentiment is all over the map. https://www.reddit.com/r/rust/comments/b6bu2c/idiomatic_monads_in_rust_a_pragmatic_new_design/ https://www.reddit.com/r/rust/comments/b6bu2c/idiomatic_mona... is the reddit thread on this post, you can see a number of different opinions expressed there. 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.
- ldng 8y agoWell, I hope they don't. Functional extremism killed Scala for the wider public (IMHO)
- hombre_fatal 8y agoimo the early explosion of language complexity is what doomed Scala. There were a lot of failed and semi-failed experiments in the language. They even tried and gave up on structural typing and regressed to some half-assed attempt. Jumped on bandwagons they regretted like xml literals. There was also that research-based scala v2 rewrite. http://dotty.epfl.ch/ http://dotty.epfl.ch/ -- These kinds of endeavors suck a lot of thought power from the community. 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.
- tempodox 8y agoIf taking monads to Rust takes such convoluted code, my conclusion would be that it probably isn't a good fit. Compared to this, Haskell is a breeze.
- nine_k 8y agoOne of the purposes of publishing such papers, as see it, is triggering responses with simpler, easier proposals. They may cover the important 90% of the original, doing away with the most complexity-inducing 10%.
- empath75 8y agoImplementing monads will be convoluted, using them is relatively easy. It wouldn’t change any of the existing code, but it would allow you to write a function like this: 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.
- truth_seeker 8y agoWow. Does that monad abstraction also cost free ?
- lucozade 8y agoHe only suggesting adding associated traits to trait definitions from what I can see. 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.
- devit 8y agoCompilation time is the other potential issue, although it's hard to predict it.
- mruts 8y agoI'm not that familiar with Rust, but what is the rational against higher-kinded types? Is it a technical limitation that everyone agrees is a limitation, or is there some rationale why higher-kinded types in Rust are not useful? 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.
- steveklabnik 8y ago> what is the rational against higher-kinded types? 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"?
- comex 8y agoGeneric associated types are equally expressive to higher-kinded types while being more straightforward to implement on top of Rust's existing syntax. Adding true higher-kinded types in the future is not out of the question, but you'd need to add new syntax to declare them, which represents a fair bit of complexity for something that may not be necessary. There are also questions about ambiguities with respect to default parameters. If you have struct Foo<A = i32>(A); you can currently write `Foo` to refer to `Foo<i32>`, but what if you meant to refer to the higher-kinded type `Foo` itself? It could be determined based on context, but that would be somewhat confusing, and might not be possible in all situations (like when declaring type aliases, or if a way is ever added for a parameter to accept multiple kinds).
- tinco 8y agoWhen this was released I posted this comment on the Haskell subreddit, thinking I was on the rust subreddit. It's got some musings about what the dangers of becoming like Haskell are: 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.
- Animats 8y agoUm, yes. C++ went down that rathole, and it's not pretty. 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.
- comex 8y ago> 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? 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
- ainar-g 8y agoOne question I almost never see addressed with monads is the question of the stack. The stack is not endless, and may actually be quite small on some devices. How is that fact reconciled with the fact that do-notation is essentially doStuff >>= (\a -> doMoreStuff >>= (\b -> doEvenMoreStuff >>= (\c -> -- Ad nauseam. ) ) ) Depending on the data being transferred, that looks like a lot of stack to me.
- _hardwaregeek 8y agoCouldn't you apply standard tail call optimization and turn it into a trampoline?
- ainar-g 8y agoThat is assuming that your compiler knows about such optimisations and can apply them in non-recursive situations. As far as I know, Go doesn't apply tail-call optimisation. Haskell probably does. Not sure about Rust. Either way, depending on the compiler making one particular optimisation just so that your code works seems rather fragile to me.
- steveklabnik 8y agoRust does not currently guarantee TCO, though llvm may choose to do it if it wishes.
- eslaught 8y agoThere are languages where TCO is defined as part of the language spec, specifically to give programmers permission to write this sort of code. Some Lisps (Scheme, I think) and Lua work this way. TCO is a relatively well-understood optimization that isn't prone to being brittle the way e.g. auto-parallelizers or auto-vectorizers can be. So it's less fragile than you'd think.
- ainar-g 8y agoDidn't know about Lua[1], thanks! Although I think I would prefer an explicit syntax, like Tcl's “tailcall”[2], Perl's “goto &sub”[3], or “become”[4], with the compiler checking that this is actually a tail-call. [1]: https://www.lua.org/pil/6.3.html https://www.lua.org/pil/6.3.html [2]: https://wiki.tcl-lang.org/page/tailcall https://wiki.tcl-lang.org/page/tailcall [3]: https://perldoc.perl.org/functions/goto.html https://perldoc.perl.org/functions/goto.html [4]: Which was used in a C-family language I can't remember.
- chmln 8y agoCall me closed-minded, but I seriously hope something like this never makes it into Rust. Not only is the complexity overbearing, but the motivation for this solution is rather thin.
- b0rsuk 8y agoWhat would performance be like compared to imperative style i/o ?
- Buttons840 8y agoMonads are not about I/O.
- b0rsuk 8y agoParent comment is not about answer.