5 ms·

I haven't worked much with Haskell, but at first blush, monads to me seem almost like a perverse functional converse to Greenspun's 10th Law. Haskell is purely

by lmkg 17y ago

I haven't worked much with Haskell, but at first blush, monads to me seem almost like a perverse functional converse to Greenspun's 10th Law. Haskell is purely functional, which imposes programing constraints, but of course it's turing-complete so it can still do anything a procedural language can. In the limit case, it can use denotational semantics to describe an emulation of a state-based program. And that's what a monad is (or at least, that's what they look like to me): a DSL for denotational semantics. Altogether, that's probably for the better. If people are going to use denotational semantics to emulate a state-capabale environment, it's better if the method for doing so is standardized, well-specified, and optimized.

blasdel 17y ago
That's a pretty good way of thinking about it (if still a bit state-ist), but the reality in Haskell is not quite optimal. Since Monads aren't really built-in, there's no semantics-checking -- the compiler can't confirm that your 'monads' actually follow the Monad Laws.
- jganetsk 17y ago
  If you can confirm that your monads follow the Monad Laws, you've solved the halting problem.
  - blasdel 17y ago
    That's demonstrably false (Coq will do this for you handily), but furthermore you're missing the point entirely! Any worthwhile type-checking algorithm (like Haskell's) would have to Scoop the Loop Snooper to accept every valid formula and deny all invalid or undecidable ones. Of course they don't actually do that, instead accepting incompleteness -- that there will be valid code that they reject.
    - jganetsk 17y ago
      I agree, but that's not too practical. I mean, give me a system that will show [] to satisfy monad laws. You won't, because the definition of >>= for [] involves concat and map... both functions are recursive, and you know your system is going to reject that because it's not part of your strongly normalizing language, consequently rejecting [] as a monad. Yes, it will work if you redefine the list constructors as functions... (:) x xs = \f z -> f x (xs f z) [] = \f z -> z ... and then we can define fold in a non-recursive way... but can this work in Haskell?
  - dons 17y ago
    Seriously, no. You are wrong. By a large margin. Monad laws are fairly straight forward.
gchpaco 17y ago
The problem with Haskell monad tutorials is that they focus on one thing that monads can do--in your case state. Monads can do more than that, though; nondeterministic computation comes to mind, as does simple error handling through the Maybe monad, and you can do continuations through a monad. It's a very abstract concept, and because of that people have a lot of trouble with it.
- whatajoke 17y ago
  Monads can do more than that, though; nondeterministic computation comes to mind, as does simple error handling through the Maybe monad, and you can do continuations through a monad. Please correct me if I am wrong, but all the examples you cite are about hiding mutable state using monads. 1. Non deterministic computation -> remembering last value of m and n. I assume you are talikng pseudo random generators here. 2. error handling with Maybe -> remembering last value or Nothing. Almost like passing along a single error code variable. 3. continuations -> Remember what state your computation variable and PC were last at. If I am seeing this wrong, then I will be happy to take a second look at monads :)
  - jerf 17y ago
    There's no "remembering" the last value or Nothing; it immediately short-circuits, and not because Haskell is lazy, but because that's how monads are defined. If you don't understand why "monads are programmable semi-colons", take that second look. See also the list monad; the key is not the "storing in a list" but the way it does "nondeterministic computations".
    - stonemetal 17y ago
      That is how maybe is defined not all monads.
      - jerf 17y ago
        No, I'm talking about the definition of Monad themselves. They don't work the way most people think they do, especially most of the critics. Monads have that function application step, and at every point that function can be applied one, zero, or many times. There is no "remembering" of a Nothing; the Monad definition is such that it calls the next application function zero times and immediately returns Nothing, which short-circuits the remainder of the monadic computation. That is, it doesn't "keep running" anyhow the way you might expect an imperative language would (or might, anyhow). This is why I also point out the list monad; fully understanding that is necessary to be sure you understand monads. I have seen numerous "monad" implementations in $YOUR_FAVORITE_LANGUAGE that can't do the list monad correctly because they can do 0 and 1 applications of a function, but can't correctly do arbitrarily many, because the people implementing the Monad interface didn't actually understand the interface. (In fact when I see such an implementation the first thing I look for now is the list monad, and so far of the four or five I've seen only one has gotten it right.)
jrockway 17y ago
If people are going to use denotational semantics to emulate a state-capabale environment, it's better if the method for doing so is standardized, well-specified, and optimized. I am not following you here. State is nothing special, except that it is something made special by most popular programming languages. (Where it causes lots of fun problems.) I am also not sure that "Monads" are optimized any more than any other function application. Monadic state-passing is syntax sugar more than anything else. (With other languages, state is "something else"; lexical environments, dynamic environments, and so on.)
- whatajoke 17y ago
  State is nothing special, except that it is something made special by most popular programming languages. (Where it causes lots of fun problems.) With very elementary design decisions, mutable state is very much manageable in the most popular languages. Hiding state maintenance through a monad solves very little, while throwing performance out of the window. Yeah, you can get performance out of a lazy functional language, but the hoops you have to jump through are not worth it. Ocaml is eager functional, and IMHO is a very nice compromise between expressibility and purity. Now if only its type system was as capable as haskell, and only if it had multi processor support :(
  - loup-vaillant 17y ago
    "Now if only its type system was as capable as haskell" One of the reasons is precisely the "impurity" of the language. I am referring to the value restriction, which inserts `'_a` (which means "because of possible side effects, this value won't have a polymorphic type, sorry") sometimes when you do partial applications (even ones without any side effect). It bit me once when I tried to do FRP (Yampa-style) in Ocaml. I couldn't define some of the operators (time) in a modular way (in terms of integral) without losing polymorphism. Another reason has to do with the fact that Ocaml is strict. I tried to define a mini "batteries" module with purely functional lazy lists instead of destructive streams (the enumeration). There is simply no way to define map or filter in terms of fold without losing laziness, or seriously polluting the type of fold, map, and filter. This can still be regarded as a type system issue : if strict and lazy types were compatible, as they are in Haskell, it wouldn't have been such a problem.

by lmkg 17y ago

blasdel 17y ago

That's a pretty good way of thinking about it (if still a bit state-ist), but the reality in Haskell is not quite optimal. Since Monads aren't really built-in, there's no semantics-checking -- the compiler can't confirm that your 'monads' actually follow the Monad Laws.

jganetsk 17y ago
If you can confirm that your monads follow the Monad Laws, you've solved the halting problem.
- blasdel 17y ago
  That's demonstrably false (Coq will do this for you handily), but furthermore you're missing the point entirely! Any worthwhile type-checking algorithm (like Haskell's) would have to Scoop the Loop Snooper to accept every valid formula and deny all invalid or undecidable ones. Of course they don't actually do that, instead accepting incompleteness -- that there will be valid code that they reject.
  - jganetsk 17y ago
    I agree, but that's not too practical. I mean, give me a system that will show [] to satisfy monad laws. You won't, because the definition of >>= for [] involves concat and map... both functions are recursive, and you know your system is going to reject that because it's not part of your strongly normalizing language, consequently rejecting [] as a monad. Yes, it will work if you redefine the list constructors as functions... (:) x xs = \f z -> f x (xs f z) [] = \f z -> z ... and then we can define fold in a non-recursive way... but can this work in Haskell?
- dons 17y ago
  Seriously, no. You are wrong. By a large margin. Monad laws are fairly straight forward.

gchpaco 17y ago

The problem with Haskell monad tutorials is that they focus on one thing that monads can do--in your case state. Monads can do more than that, though; nondeterministic computation comes to mind, as does simple error handling through the Maybe monad, and you can do continuations through a monad. It's a very abstract concept, and because of that people have a lot of trouble with it.

whatajoke 17y ago
Monads can do more than that, though; nondeterministic computation comes to mind, as does simple error handling through the Maybe monad, and you can do continuations through a monad. Please correct me if I am wrong, but all the examples you cite are about hiding mutable state using monads. 1. Non deterministic computation -> remembering last value of m and n. I assume you are talikng pseudo random generators here. 2. error handling with Maybe -> remembering last value or Nothing. Almost like passing along a single error code variable. 3. continuations -> Remember what state your computation variable and PC were last at. If I am seeing this wrong, then I will be happy to take a second look at monads :)
- jerf 17y ago
  There's no "remembering" the last value or Nothing; it immediately short-circuits, and not because Haskell is lazy, but because that's how monads are defined. If you don't understand why "monads are programmable semi-colons", take that second look. See also the list monad; the key is not the "storing in a list" but the way it does "nondeterministic computations".
  - stonemetal 17y ago
    That is how maybe is defined not all monads.
    - jerf 17y ago
      No, I'm talking about the definition of Monad themselves. They don't work the way most people think they do, especially most of the critics. Monads have that function application step, and at every point that function can be applied one, zero, or many times. There is no "remembering" of a Nothing; the Monad definition is such that it calls the next application function zero times and immediately returns Nothing, which short-circuits the remainder of the monadic computation. That is, it doesn't "keep running" anyhow the way you might expect an imperative language would (or might, anyhow). This is why I also point out the list monad; fully understanding that is necessary to be sure you understand monads. I have seen numerous "monad" implementations in $YOUR_FAVORITE_LANGUAGE that can't do the list monad correctly because they can do 0 and 1 applications of a function, but can't correctly do arbitrarily many, because the people implementing the Monad interface didn't actually understand the interface. (In fact when I see such an implementation the first thing I look for now is the list monad, and so far of the four or five I've seen only one has gotten it right.)

jrockway 17y ago

If people are going to use denotational semantics to emulate a state-capabale environment, it's better if the method for doing so is standardized, well-specified, and optimized. I am not following you here. State is nothing special, except that it is something made special by most popular programming languages. (Where it causes lots of fun problems.) I am also not sure that "Monads" are optimized any more than any other function application. Monadic state-passing is syntax sugar more than anything else. (With other languages, state is "something else"; lexical environments, dynamic environments, and so on.)

whatajoke 17y ago
State is nothing special, except that it is something made special by most popular programming languages. (Where it causes lots of fun problems.) With very elementary design decisions, mutable state is very much manageable in the most popular languages. Hiding state maintenance through a monad solves very little, while throwing performance out of the window. Yeah, you can get performance out of a lazy functional language, but the hoops you have to jump through are not worth it. Ocaml is eager functional, and IMHO is a very nice compromise between expressibility and purity. Now if only its type system was as capable as haskell, and only if it had multi processor support :(
- loup-vaillant 17y ago
  "Now if only its type system was as capable as haskell" One of the reasons is precisely the "impurity" of the language. I am referring to the value restriction, which inserts `'_a` (which means "because of possible side effects, this value won't have a polymorphic type, sorry") sometimes when you do partial applications (even ones without any side effect). It bit me once when I tried to do FRP (Yampa-style) in Ocaml. I couldn't define some of the operators (time) in a modular way (in terms of integral) without losing polymorphism. Another reason has to do with the fact that Ocaml is strict. I tried to define a mini "batteries" module with purely functional lazy lists instead of destructive streams (the enumeration). There is simply no way to define map or filter in terms of fold without losing laziness, or seriously polluting the type of fold, map, and filter. This can still be regarded as a type system issue : if strict and lazy types were compatible, as they are in Haskell, it wouldn't have been such a problem.