6 ms·

Monads in Scheme

104 points by amirouche 11y ago

davexunit 11y ago
This was a helpful article for me because I am more familiar with Scheme than I am ML, which most monad articles use. For those that want to see a Scheme monad implementation that is being used for real work on a regular basis, check out the (guix monads) module in GNU Guix: http://git.savannah.gnu.org/cgit/guix.git/tree/guix/monads.scm http://git.savannah.gnu.org/cgit/guix.git/tree/guix/monads.s...
lispm 11y ago
but why?
- davexunit 11y ago
  Because they are a very useful abstraction?
  - agumonkey 11y ago
    Who else enjoy understanding abstractions in less abstract languages ? [1] I never really click about a paradigm or a concept until I see two encodings of it. Most of the time a system designed around a particular concept doesn't help me at all, it's like asking a fish about water. [1] needed ADA to get a feel of public / private in Java, needed recursive and purely functional to finally stay alive in the stateful world of C and the like, and Monads in Haskell were always obfuscated by its glorious type system, so learning about them in elisp (sic) was of a great help.
  - sago 11y ago
    > Because they are a very useful abstraction? Doesn't that beg the question? Saying they're useful just invites another 'but why?'. Other than being familiar to Haskell programmers, what do monads allow a programmer to do in scheme that isn't more simply implemented in another way? (Not passive aggressive rhetorical questions, genuine ones).
    - davexunit 11y ago
      This bit of the Guix documentation provides a better explanation of why monads are useful than I could give: The procedures that operate on the store described in the previous sections all take an open connection to the build daemon as their first argument. Although the underlying model is functional, they either have side effects or depend on the current state of the store. The former is inconvenient: the connection to the build daemon has to be carried around in all those functions, making it impossible to compose functions that do not take that parameter with functions that do. The latter can be problematic: since store operations have side effects and/or depend on external state, they have to be properly sequenced. This is where the (guix monads) module comes in. This module provides a framework for working with monads, and a particularly useful monad for our uses, the store monad. Monads are a construct that allows two things: associating “context” with values (in our case, the context is the store), and building sequences of computations (here computations include accesses to the store.) Values in a monad—values that carry this additional context—are called monadic values; procedures that return such values are called monadic procedures. https://gnu.org/software/guix/manual/html_node/The-Store-Monad.html#The-Store-Monad https://gnu.org/software/guix/manual/html_node/The-Store-Mon...
    - gamegoblin 11y ago
      One reason is that they allow you to write general, primitive functions, and then compose them together or hoist them up into the same category. Consider this example, written in Java 8. // Maybe<T> can be Nothing(), representing failure, or Just(X) representing success. public abstract class Maybe<T> {} public class Just<T> extends Maybe<T> { public final T value; public Just(T value) { this.value = value; } } public class Nothing<T> extends Maybe<T> {} Now consider these function signatures: // Returns Nothing() if argument is negative public Maybe<Double> squareRoot(double x); // Returns Nothing() if divisor is 0 public Maybe<Double> divide(double x, double y); What do I do if I want to chain these functions together to write a "square root and divide" function? // Returns Nothing() if dividend is negative or divisor is 0 public Maybe<Double> squareRootAndDivide(double x, double y) { Maybe<Double> sqrt = squareRoot(x); if(sqrt instanceof Just<Double>) { return divide(sqrt.value, y); } else { return new Nothing(); } } This is kind of ugly. And if I want to compose lots of Maybe values, all of this instanceof nonsense (or having a tagged union in C or whatever) becomes extremely tedious. Better is to define a function to contain this logic: // Returns Nothing() if x is Nothing(), otherwise returns f(unwrapped x) public <A, B> Maybe<B> bind(Maybe<A> x, Function<A, Maybe<B>> f) { if(x instanceof Just<A>) { return f.apply(x.value); } else { return new Nothing(); } } Now I can write the above squareRootAndDivide code like: public Maybe<Double> squareRootAndDivide(double x, double y) { return bind(squareRoot(x), ::divide); } Now I can chain any number of calls that may all end in failure, not having to worry where the failure takes place: return bind(bind(foo(x), ::bar), ::baz); That looks kind of stupid. We could define `bind` to be a member of the abstract class Maybe, and refer to `this` instead of `x`, then we could rewrite that like: return x.bind(::foo).bind(::bar).bind(::baz); Which in Haskell would look like foo x >>= bar >>= baz Quite clean in both languages! Of course, Java might be a bad example, because you might say "Well, I would just throw an exception for any of those illegal arguments, and that would also short-circuit the computation". This is true. In Haskell, there is the Either type, which is similar to the Maybe type except instead of Nothing and Just you have Left and Right. The difference in Left and Nothing is Left can contain some information (such as a string explaining what failure happened, like a Java exception). Like Maybe, Either is also a monad, and can be chained together in much the same way, except instead of short circuiting on Nothing, it short circuits on Left. So in Java, it's almost as if you are always living in the Either monad without even knowing it! Of course, this is a gross abuse of terminology. There is also far more that can be done with monads than representing failure (although they are great for that in the above examples, or in parsers, etc). This is just a simple example. It also might be interested to note that you cannot construct a Monad interface in Java that has this `bind` function, because Java lacks Higher-Kinded Types. Consider a type in java Foo<A, B, C>. It doesn't make sense to talk about Foo<A, B>, because Foo takes 3 type parameters. In Haskell we can talk about Foo<A, B> as a "higher kinded" type that takes another type as an argument (C) to produce a concrete type of Foo<A, B, C>. As such, we have to code an ad-hoc monadic interface for every type we want to have one, but this means we can't write functions that operate on any generic monadic type. Rust is currently running into this -- they have monad-like interfaces for Result and Option (Rust versions of Either and Maybe) where the function and_then is their bind. I would like to write a function which can say, go from Vec<Option<u32>> to Option<Vec<u32>. Where it returns None if any of the elements of the Vec were None. I would also like to write a function that goes from Vec<Result<Err, u32>> to Result<Err, Vec<u32>>, giving me Err if any of the elements of the Vec were Err. You can see how this is the same pattern as above. In Haskell, with Higher-Kinded types, we can write this function generlized to all monads (called `sequence` in the standard library), but in Rust or Java, I would have to write this function for each particular instance. You might find it valuable to read something like [1], but it might use too much Haskell syntax to be particularly readable. Give it a shot, anyway. Specifically for Monads, the section about the Kleisli category is the most applicable. [1] http://www.haskellforall.com/2012/08/the-category-design-pattern.html http://www.haskellforall.com/2012/08/the-category-design-pat...
  - cmiles74 11y ago
    The article talks about creating a tree with a unique tag for each node. IMHO, their proposed solution (using a monad) makes the tree creation code simpler by removing the need to thread the counter through the functions that create the nodes. The code they end up with is conise and readable.
    - _delirium 11y ago
      To me even more concise and readable is the imperative solution the article also mentions: just refer to a "global" counter and increment it (it doesn't have to actually be global, for that matter, just scoped around the tree-building code). The article doesn't even really argue against that solution. Instead the goal here seems to be more of an intellectual challenge problem: find a functional solution that, unlike the straightforward functional solution (thread state through every function call), is not that much clunkier than the imperative solution.
nicklaf 11y ago
Oleg's entire site is a veritable gold mine of Scheme and Haskell treasures. Poke around--you won't be disappointed.
kenko 11y ago
There are several monad libraries for Clojure---mine (of which I'm fond) is here: https://github.com/bwo/monads/ https://github.com/bwo/monads/
fierycatnet 11y ago
Since it's a LISP, does that mean it would be useful in Clojure as well? Any thoughts on this?

104 points by amirouche 11y ago

This was a helpful article for me because I am more familiar with Scheme than I am ML, which most monad articles use. For those that want to see a Scheme monad implementation that is being used for real work on a regular basis, check out the (guix monads) module in GNU Guix: http://git.savannah.gnu.org/cgit/guix.git/tree/guix/monads.scm http://git.savannah.gnu.org/cgit/guix.git/tree/guix/monads.s...

lispm 11y ago

but why?

davexunit 11y ago
Because they are a very useful abstraction?
- agumonkey 11y ago
  Who else enjoy understanding abstractions in less abstract languages ? [1] I never really click about a paradigm or a concept until I see two encodings of it. Most of the time a system designed around a particular concept doesn't help me at all, it's like asking a fish about water. [1] needed ADA to get a feel of public / private in Java, needed recursive and purely functional to finally stay alive in the stateful world of C and the like, and Monads in Haskell were always obfuscated by its glorious type system, so learning about them in elisp (sic) was of a great help.
- sago 11y ago
  > Because they are a very useful abstraction? Doesn't that beg the question? Saying they're useful just invites another 'but why?'. Other than being familiar to Haskell programmers, what do monads allow a programmer to do in scheme that isn't more simply implemented in another way? (Not passive aggressive rhetorical questions, genuine ones).
  - davexunit 11y ago
    This bit of the Guix documentation provides a better explanation of why monads are useful than I could give: The procedures that operate on the store described in the previous sections all take an open connection to the build daemon as their first argument. Although the underlying model is functional, they either have side effects or depend on the current state of the store. The former is inconvenient: the connection to the build daemon has to be carried around in all those functions, making it impossible to compose functions that do not take that parameter with functions that do. The latter can be problematic: since store operations have side effects and/or depend on external state, they have to be properly sequenced. This is where the (guix monads) module comes in. This module provides a framework for working with monads, and a particularly useful monad for our uses, the store monad. Monads are a construct that allows two things: associating “context” with values (in our case, the context is the store), and building sequences of computations (here computations include accesses to the store.) Values in a monad—values that carry this additional context—are called monadic values; procedures that return such values are called monadic procedures. https://gnu.org/software/guix/manual/html_node/The-Store-Monad.html#The-Store-Monad https://gnu.org/software/guix/manual/html_node/The-Store-Mon...
  - gamegoblin 11y ago
    One reason is that they allow you to write general, primitive functions, and then compose them together or hoist them up into the same category. Consider this example, written in Java 8. // Maybe<T> can be Nothing(), representing failure, or Just(X) representing success. public abstract class Maybe<T> {} public class Just<T> extends Maybe<T> { public final T value; public Just(T value) { this.value = value; } } public class Nothing<T> extends Maybe<T> {} Now consider these function signatures: // Returns Nothing() if argument is negative public Maybe<Double> squareRoot(double x); // Returns Nothing() if divisor is 0 public Maybe<Double> divide(double x, double y); What do I do if I want to chain these functions together to write a "square root and divide" function? // Returns Nothing() if dividend is negative or divisor is 0 public Maybe<Double> squareRootAndDivide(double x, double y) { Maybe<Double> sqrt = squareRoot(x); if(sqrt instanceof Just<Double>) { return divide(sqrt.value, y); } else { return new Nothing(); } } This is kind of ugly. And if I want to compose lots of Maybe values, all of this instanceof nonsense (or having a tagged union in C or whatever) becomes extremely tedious. Better is to define a function to contain this logic: // Returns Nothing() if x is Nothing(), otherwise returns f(unwrapped x) public <A, B> Maybe<B> bind(Maybe<A> x, Function<A, Maybe<B>> f) { if(x instanceof Just<A>) { return f.apply(x.value); } else { return new Nothing(); } } Now I can write the above squareRootAndDivide code like: public Maybe<Double> squareRootAndDivide(double x, double y) { return bind(squareRoot(x), ::divide); } Now I can chain any number of calls that may all end in failure, not having to worry where the failure takes place: return bind(bind(foo(x), ::bar), ::baz); That looks kind of stupid. We could define `bind` to be a member of the abstract class Maybe, and refer to `this` instead of `x`, then we could rewrite that like: return x.bind(::foo).bind(::bar).bind(::baz); Which in Haskell would look like foo x >>= bar >>= baz Quite clean in both languages! Of course, Java might be a bad example, because you might say "Well, I would just throw an exception for any of those illegal arguments, and that would also short-circuit the computation". This is true. In Haskell, there is the Either type, which is similar to the Maybe type except instead of Nothing and Just you have Left and Right. The difference in Left and Nothing is Left can contain some information (such as a string explaining what failure happened, like a Java exception). Like Maybe, Either is also a monad, and can be chained together in much the same way, except instead of short circuiting on Nothing, it short circuits on Left. So in Java, it's almost as if you are always living in the Either monad without even knowing it! Of course, this is a gross abuse of terminology. There is also far more that can be done with monads than representing failure (although they are great for that in the above examples, or in parsers, etc). This is just a simple example. It also might be interested to note that you cannot construct a Monad interface in Java that has this `bind` function, because Java lacks Higher-Kinded Types. Consider a type in java Foo<A, B, C>. It doesn't make sense to talk about Foo<A, B>, because Foo takes 3 type parameters. In Haskell we can talk about Foo<A, B> as a "higher kinded" type that takes another type as an argument (C) to produce a concrete type of Foo<A, B, C>. As such, we have to code an ad-hoc monadic interface for every type we want to have one, but this means we can't write functions that operate on any generic monadic type. Rust is currently running into this -- they have monad-like interfaces for Result and Option (Rust versions of Either and Maybe) where the function and_then is their bind. I would like to write a function which can say, go from Vec<Option<u32>> to Option<Vec<u32>. Where it returns None if any of the elements of the Vec were None. I would also like to write a function that goes from Vec<Result<Err, u32>> to Result<Err, Vec<u32>>, giving me Err if any of the elements of the Vec were Err. You can see how this is the same pattern as above. In Haskell, with Higher-Kinded types, we can write this function generlized to all monads (called `sequence` in the standard library), but in Rust or Java, I would have to write this function for each particular instance. You might find it valuable to read something like [1], but it might use too much Haskell syntax to be particularly readable. Give it a shot, anyway. Specifically for Monads, the section about the Kleisli category is the most applicable. [1] http://www.haskellforall.com/2012/08/the-category-design-pattern.html http://www.haskellforall.com/2012/08/the-category-design-pat...
- cmiles74 11y ago
  The article talks about creating a tree with a unique tag for each node. IMHO, their proposed solution (using a monad) makes the tree creation code simpler by removing the need to thread the counter through the functions that create the nodes. The code they end up with is conise and readable.
  - _delirium 11y ago
    To me even more concise and readable is the imperative solution the article also mentions: just refer to a "global" counter and increment it (it doesn't have to actually be global, for that matter, just scoped around the tree-building code). The article doesn't even really argue against that solution. Instead the goal here seems to be more of an intellectual challenge problem: find a functional solution that, unlike the straightforward functional solution (thread state through every function call), is not that much clunkier than the imperative solution.

nicklaf 11y ago

Oleg's entire site is a veritable gold mine of Scheme and Haskell treasures. Poke around--you won't be disappointed.

kenko 11y ago

There are several monad libraries for Clojure---mine (of which I'm fond) is here: https://github.com/bwo/monads/ https://github.com/bwo/monads/

fierycatnet 11y ago

Since it's a LISP, does that mean it would be useful in Clojure as well? Any thoughts on this?