187

Could anyone give some pointers on why the impure computations in Haskell are modelled as monads?

I mean monad is just an interface with 4 operations, so what was the reasoning to modelling side-effects in it?

Viet
  • 17,944
  • 33
  • 103
  • 135
bodacydo
  • 75,521
  • 93
  • 229
  • 319
  • 15
    Monads just define two operations. – Dario Mar 21 '10 at 21:26
  • 3
    but what about return and fail? (besides (>>) and (>>=)) – bodacydo Mar 21 '10 at 22:53
  • 56
    The two operations are `return` and `(>>=)`. `x >> y` is the same as `x >>= \\_ -> y` (i.e. it ignores the result of the first argument). We don't talk about `fail`. – porges Mar 22 '10 at 00:30
  • 2
    @Porges Why not talk about fail? Its somewhat useful in ie Maybe, Parser, etc. – alternative Jul 27 '11 at 16:24
  • 17
    @monadic: `fail` is in the `Monad` class because of a historical accident; it really belongs in `MonadPlus`. Take note that its default definition is unsafe. – JB. Aug 17 '11 at 09:13
  • Actually they define three map, wrap or return, and unwrap or join. Map is inherited from Functor. Map is like the function call operator, but it runs a function through a container like a list, tree, or just. UnwrapMap runs a function that already wraps values and lets you chain together values. UnwrapMap is also called monadic bind, but unlike map or the function call operator its arts are backwards. In JavaScript futures or promises call then which is also UnwrapMap, but Haskell does it for both synchronous and async code unifying them also unifying lists. – aoeu256 Aug 06 '19 at 01:04
  • Unwrapmap is just unwrap . map btw. – aoeu256 Aug 06 '19 at 01:16
  • (Note that `fail` is now part of `MonadFail`, which has `Monad` as a superclass.) – chepner Nov 30 '22 at 18:18

8 Answers8

309

Suppose a function has side effects. If we take all the effects it produces as the input and output parameters, then the function is pure to the outside world.

So, for an impure function

f' :: Int -> Int

we add the RealWorld to the consideration

f :: Int -> RealWorld -> (Int, RealWorld)
-- input some states of the whole world,
-- modify the whole world because of the side effects,
-- then return the new world.

then f is pure again. We define a parametrized data type type IO a = RealWorld -> (a, RealWorld), so we don't need to type RealWorld so many times, and can just write

f :: Int -> IO Int

To the programmer, handling a RealWorld directly is too dangerous—in particular, if a programmer gets their hands on a value of type RealWorld, they might try to copy it, which is basically impossible. (Think of trying to copy the entire filesystem, for example. Where would you put it?) Therefore, our definition of IO encapsulates the states of the whole world as well.

Composition of "impure" functions

These impure functions are useless if we can't chain them together. Consider

getLine     :: IO String            ~            RealWorld -> (String, RealWorld)
getContents :: String -> IO String  ~  String -> RealWorld -> (String, RealWorld)
putStrLn    :: String -> IO ()      ~  String -> RealWorld -> ((),     RealWorld)

We want to

  • get a filename from the console,
  • read that file, and
  • print that file's contents to the console.

How would we do it if we could access the real world states?

printFile :: RealWorld -> ((), RealWorld)
printFile world0 = let (filename, world1) = getLine world0
                       (contents, world2) = (getContents filename) world1 
                   in  (putStrLn contents) world2 -- results in ((), world3)

We see a pattern here. The functions are called like this:

...
(<result-of-f>, worldY) = f               worldX
(<result-of-g>, worldZ) = g <result-of-f> worldY
...

So we could define an operator ~~~ to bind them:

(~~~) :: (IO b) -> (b -> IO c) -> IO c

(~~~) ::      (RealWorld -> (b,   RealWorld))
      ->                    (b -> RealWorld -> (c, RealWorld))
      ->      (RealWorld                    -> (c, RealWorld))
(f ~~~ g) worldX = let (resF, worldY) = f worldX
                   in g resF worldY

then we could simply write

printFile = getLine ~~~ getContents ~~~ putStrLn

without touching the real world.

"Impurification"

Now suppose we want to make the file content uppercase as well. Uppercasing is a pure function

upperCase :: String -> String

But to make it into the real world, it has to return an IO String. It is easy to lift such a function:

impureUpperCase :: String -> RealWorld -> (String, RealWorld)
impureUpperCase str world = (upperCase str, world)

This can be generalized:

impurify :: a -> IO a

impurify :: a -> RealWorld -> (a, RealWorld)
impurify a world = (a, world)

so that impureUpperCase = impurify . upperCase, and we can write

printUpperCaseFile = 
    getLine ~~~ getContents ~~~ (impurify . upperCase) ~~~ putStrLn

(Note: Normally we write getLine ~~~ getContents ~~~ (putStrLn . upperCase))

We were working with monads all along

Now let's see what we've done:

  1. We defined an operator (~~~) :: IO b -> (b -> IO c) -> IO c which chains two impure functions together
  2. We defined a function impurify :: a -> IO a which converts a pure value to impure.

Now we make the identification (>>=) = (~~~) and return = impurify, and see? We've got a monad.


Technical note

To ensure it's really a monad, there's still a few axioms which need to be checked too:

  1. return a >>= f = f a

     impurify a                =  (\world -> (a, world))
    (impurify a ~~~ f) worldX  =  let (resF, worldY) = (\world -> (a, world )) worldX 
                                  in f resF worldY
                               =  let (resF, worldY) =            (a, worldX)       
                                  in f resF worldY
                               =  f a worldX
    
  2. f >>= return = f

    (f ~~~ impurify) worldX  =  let (resF, worldY) = f worldX 
                                in impurify resF worldY
                             =  let (resF, worldY) = f worldX      
                                in (resF, worldY)
                             =  f worldX
    
  3. f >>= (\x -> g x >>= h) = (f >>= g) >>= h

    Left as exercise.

Mateen Ulhaq
  • 24,552
  • 19
  • 101
  • 135
kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
  • 7
    +1 but I want to note that this specifically covers the IO case. http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html is pretty similar, but generalizes `RealWorld` into... well, you'll see. – ephemient Mar 22 '10 at 16:46
  • 5
    Note that this explanation cannot really apply to Haskell's `IO`, because the latter supports interaction, concurrency, and nondeterminism. See my answer to this question for some more pointers. – Conal Aug 16 '11 at 00:23
  • Very good summary of the surface. With this and with the category theory basics I think I'm a bit closer to have an intuition of the real possibilities... though still too far:) thanks – ch0kee Dec 15 '11 at 03:42
  • 4
    @Conal GHC actually does implement `IO` this way, but `RealWorld` doesn't actually represent the real world, it's just a token to keep the operations in order (the "magic" is that `RealWorld` is GHC Haskell's only uniqueness type) – Jeremy List Oct 30 '15 at 07:15
  • 2
    @JeremyList As I understand it, GHC implements `IO` via a combination of this representation and *non-standard compiler magic* (reminiscent of the [Ken Thompson's famous C compiler virus](http://c2.com/cgi/wiki?TheKenThompsonHack)). For other types, the truth is in the source code along with the usual Haskell semantics. – Conal Oct 30 '15 at 17:21
  • 1
    @Clonal My comment was due to me having read the relevant parts of the GHC source code. – Jeremy List Oct 31 '15 at 00:14
  • @kennytm I think there's a mistake in the proof of (2) `f >>= return = f`. I think it should be the following: `(f ~~~ impurify) worldX` = `let (resF, worldY) = f worldX in impurify resF worldY` = `let (resF, worldY) = f worldX in (resF, worldY)` = `f worldX` – Gorisanson May 15 '20 at 15:55
  • 2
    @Gorisanson I think you're right, it shouldn't be applied to `a`, just to `worldX`. I'll re-check this some more, and then will edit. Good catch! :) In *SO-as-it-should-have-been*, you'd be awarded huge rep bonus for this fix! – Will Ness May 17 '20 at 16:02
  • @WillNess Thank you! And thanks for your edit too! In fact, I [edited it several months ago](https://stackoverflow.com/review/suggested-edits/24209865), but the edit was rejected. So I commented it just after getting the ["comment everywhere"](https://stackoverflow.com/help/privileges/comment) privilege, which requires more than 50 reputation:) – Gorisanson May 17 '20 at 22:44
43

Could anyone give some pointers on why the unpure computations in Haskell are modeled as monads?

This question contains a widespread misunderstanding. Impurity and Monad are independent notions. Impurity is not modeled by Monad. Rather, there are a few data types, such as IO, that represent imperative computation. And for some of those types, a tiny fraction of their interface corresponds to the interface pattern called "Monad". Moreover, there is no known pure/functional/denotative explanation of IO (and there is unlikely to be one, considering the "sin bin" purpose of IO), though there is the commonly told story about World -> (a, World) being the meaning of IO a. That story cannot truthfully describe IO, because IO supports concurrency and nondeterminism. The story doesn't even work when for deterministic computations that allow mid-computation interaction with the world.

For more explanation, see this answer.

Edit: On re-reading the question, I don't think my answer is quite on track. Models of imperative computation do often turn out to be monads, just as the question said. The asker might not really assume that monadness in any way enables the modeling of imperative computation.

Community
  • 1
  • 1
Conal
  • 18,517
  • 2
  • 37
  • 40
  • But GHC does define `IO` as `newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))` (Ref: http://www.haskell.org/ghc/docs/latest/html/libraries/ghc-prim-0.2.0.0/src/GHC-Types.html#IO) where `State#` is a [thread-local type](http://www.haskell.org/ghc/docs/latest/html/libraries/ghc-prim-0.2.0.0/GHC-Prim.html#t:State-35-). – kennytm Aug 16 '11 at 04:55
  • 2
    @KennyTM: But `RealWorld` is, as the docs say, "deeply magical". It's a token that represents what the runtime system is doing, it doesn't actually mean anything about the real world. You can't even conjure up a new one to make a "thread" without doing extra trickery; the naive approach would just create a single, blocking action with a lot of ambiguity about when it will run. – C. A. McCann Aug 16 '11 at 13:03
  • 4
    Also, I would argue that monads *are* essentially imperative in nature. If the functor represents some structure with values embedded in it, a monad instance means you can build and flatten new layers based on those values. So whatever meaning you assign to a single layer of the functor, a monad means you can create an unbounded number of layers with a strict notion of causality going from one to the next. Specific instances may not have intrinsically imperative structure, but `Monad` in general really does. – C. A. McCann Aug 16 '11 at 13:19
  • KennyTM. Yes, I suspect that many are misled by this "definition". It could not really be the definition of `IO` for the reasons I've given. Rather it is *part* of a definition, the rest of which lives in the compiler internals, which I think is what some people mean by "deeply magical". – Conal Aug 17 '11 at 07:25
  • C.A.McC: I don't know what you mean by "Specific instances may not have intrinsically imperative structure, but Monad in general really does." (Does in general but not in particular??) Nor what collapsing functor nesting has to do with imperative computation. Maybe "imperative" has a meaning for you that I wouldn't expect. – Conal Aug 17 '11 at 07:57
  • 3
    By "`Monad` in general" I mean roughly `forall m. Monad m => ...`, i.e., working on an arbitrary instance. The things you can do with an arbitrary monad are almost exactly the same things you can do with `IO`: receive opaque primitives (as function arguments, or from libraries, respectively), construct no-ops with `return`, or transform a value in an irreversible manner using `(>>=)`. The essence of programming in an arbitrary monad is generating a list of irrevocable actions: "do X, then do Y, then...". Sounds pretty imperative to me! – C. A. McCann Aug 17 '11 at 14:17
  • C.A.McC: I read "do X, then do Y, then..." as your own interpretation/bias showing through, rather than anything actually in the nature of arbitrary monads. I wouldn't use these terms or this mindset for many of my favorite monads, e.g., `(->) a`, `(,) a`, `Maybe`, `Id`, `Stream`, `[]`, and all trie types. Bias aside, monadness is nothing more than two generic operations and their three laws. There is nothing intrinsically imperative there, and if there were, they wouldn't hold for the monads I mentioned (unless one is willing to argue that everything is imperative, even if trivially). – Conal Aug 17 '11 at 21:20
  • 2
    No, you're still missing my point here. Of course you wouldn't use that mindset for any of those specific types, because they have clear, meaningful structure. When I say "arbitrary monads" I mean "you don't get to pick which one"; the perspective here is from inside the quantifier, so thinking of `m` as existential might be more helpful. Furthermore, my "interpretation" is a *rephrasing* of the laws; the list of "do X" statements is precisely the free monoid on the unknown structure created via `(>>=)`; and the monad laws are just monoid laws on endofunctor composition. – C. A. McCann Aug 18 '11 at 07:04
  • 3
    In short, the greatest lower bound on what all monads together describe is a blind, meaningless march into the future. `IO` is a pathological case precisely because it offers *almost nothing more* than this minimum. In specific cases, types may reveal more structure, and thus have actual meaning; but otherwise the essential properties of a monad--based on the laws--are as antithetical to clear denotation as `IO` is. Without exporting constructors, exhaustively enumerating primitive actions, or something similar, the situation is hopeless. – C. A. McCann Aug 18 '11 at 07:15
  • Ah, maybe I'm taking your words literally when you meant them in some sort of figurative way (that I haven't guessed), particularly the words "do", "then", "actions" and "irrevocable", all of which I relate to specifically "imperative" monads rather than to arbitrary monads. (And even imperative computational models can be revocable with a little help--just not the common ones.) – Conal Aug 18 '11 at 18:10
  • A total function with the explicitly quantified type `forall a. a -> a -> a` can do one of two things; return its first argument, or its second. Either way, it has to discard something. Do you think the existence of functions such as `(+)`, with types similar to `a -> a -> a` for a specific `a` but which use both arguments, makes the previous statement in any way inaccurate? – C. A. McCann Aug 18 '11 at 19:04
  • @C.A.McCann let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/2636/discussion-between-conal-and-c-a-mccann) – Conal Aug 18 '11 at 19:55
  • @C.A.McCann I've read a bit from your chat room. What do you suggest as an alternative to IO monads then? Specifically I've found it difficult to understand what it means for the IO monad or world passing style in Mercury to work with concurrency? – CMCDragonkai Feb 20 '15 at 04:36
  • @CMCDragonkai: I don't know, and I don't think anyone does for sure. Figuring out the Right Way to handle this stuff is something of an open question, as far as I know. – C. A. McCann Feb 21 '15 at 02:41
  • I don't see threading as a problem. Each thread interacts with the real world, of which other threads are a part. The only truly magic thing about the RealWorld object is that you can never access it directly, only through API calls like "putStrLn". – Paul Johnson Aug 06 '19 at 10:36
  • Since you don't yet see the problem, take your intuition and make it precise in terms of the purported meaning `World -> (a, World)`. What does `forkIO` mean in this model? What do the other `IO` primitives mean in this model? As with many things, without making our intuitions into precise claims and then trying to prove those claims rigorously, we can't know how they fail to hold water and what to try next. – Conal Aug 12 '19 at 18:53
13

As I understand it, someone called Eugenio Moggi first noticed that a previously obscure mathematical construct called a "monad" could be used to model side effects in computer languages, and hence specify their semantics using Lambda calculus. When Haskell was being developed there were various ways in which impure computations were modelled (see Simon Peyton Jones' "hair shirt" paper for more details), but when Phil Wadler introduced monads it rapidly became obvious that this was The Answer. And the rest is history.

Paul Johnson
  • 17,438
  • 3
  • 42
  • 59
  • 4
    Not quite. It has been known that a monad can model interpretation for a very long time (at least since "Topoi: A Categorical Analysis of Logic). On the other hand, it wasn't possible to clearly express the types for monads until strongly typed functional languages came around, and then Moggi put two and two together. – nomen Dec 04 '12 at 02:10
8

Could anyone give some pointers on why the unpure computations in Haskell are modeled as monads?

Well, because Haskell is pure. You need a mathematical concept to distinguish between unpure computations and pure ones on type-level and to model programm flows in respectively.

This means you'll have to end up with some type IO a that models an unpure computation. Then you need to know ways of combining these computations of which apply in sequence (>>=) and lift a value (return) are the most obvious and basic ones.

With these two, you've already defined a monad (without even thinking of it);)

In addition, monads provide very general and powerful abstractions, so many kinds of control flow can be conveniently generalized in monadic functions like sequence, liftM or special syntax, making unpureness not such a special case.

See monads in functional programming and uniqueness typing (the only alternative I know) for more information.

Dario
  • 48,658
  • 8
  • 97
  • 130
8

As you say, Monad is a very simple structure. One half of the answer is: Monad is the simplest structure that we could possibly give to side-effecting functions and be able to use them. With Monad we can do two things: we can treat a pure value as a side-effecting value (return), and we can apply a side-effecting function to a side-effecting value to get a new side-effecting value (>>=). Losing the ability to do either of these things would be crippling, so our side-effecting type needs to be "at least" Monad, and it turns out Monad is enough to implement everything we've needed to so far.

The other half is: what's the most detailed structure we could give to "possible side effects"? We can certainly think about the space of all possible side effects as a set (the only operation that requires is membership). We can combine two side effects by doing them one after another, and this will give rise to a different side effect (or possibly the same one - if the first was "shutdown computer" and the second was "write file", then the result of composing these is just "shutdown computer").

Ok, so what can we say about this operation? It's associative; that is, if we combine three side effects, it doesn't matter which order we do the combining in. If we do (write file then read socket) then shutdown computer, it's the same as doing write file then (read socket then shutdown computer). But it's not commutative: ("write file" then "delete file") is a different side effect from ("delete file" then "write file"). And we have an identity: the special side effect "no side effects" works ("no side effects" then "delete file" is the same side effect as just "delete file") At this point any mathematician is thinking "Group!" But groups have inverses, and there's no way to invert a side effect in general; "delete file" is irreversible. So the structure we have left is that of a monoid, which means our side-effecting functions should be monads.

Is there a more complex structure? Sure! We could divide possible side effects into filesystem-based effects, network-based effects and more, and we could come up with more elaborate rules of composition that preserved these details. But again it comes down to: Monad is very simple, and yet powerful enough to express most of the properties we care about. (In particular, associativity and the other axioms let us test our application in small pieces, with confidence that the side effects of the combined application will be the same as the combination of the side effects of the pieces).

lmm
  • 17,386
  • 3
  • 26
  • 37
4

It's actually quite a clean way to think of I/O in a functional way.

In most programming languages, you do input/output operations. In Haskell, imagine writing code not to do the operations, but to generate a list of the operations that you would like to do.

Monads are just pretty syntax for exactly that.

If you want to know why monads as opposed to something else, I guess the answer is that they're the best functional way to represent I/O that people could think of when they were making Haskell.

Noah Lavine
  • 793
  • 5
  • 7
3

AFAIK, the reason is to be able to include side effects checks in the type system. If you want to know more, listen to those SE-Radio episodes: Episode 108: Simon Peyton Jones on Functional Programming and Haskell Episode 72: Erik Meijer on LINQ

Gabriel Ščerbák
  • 18,240
  • 8
  • 37
  • 52
2

Above there are very good detailed answers with theoretical background. But I want to give my view on IO monad. I am not experienced haskell programmer, so May be it is quite naive or even wrong. But i helped me to deal with IO monad to some extent (note, that it do not relates to other monads).

First I want to say, that example with "real world" is not too clear for me as we cannot access its (real world) previous states. May be it do not relates to monad computations at all but it is desired in the sense of referential transparency, which is generally presents in haskell code.

So we want our language (haskell) to be pure. But we need input/output operations as without them our program cannot be useful. And those operations cannot be pure by their nature. So the only way to deal with this we have to separate impure operations from the rest of code.

Here monad comes. Actually, I am not sure, that there cannot exist other construct with similar needed properties, but the point is that monad have these properties, so it can be used (and it is used successfully). The main property is that we cannot escape from it. Monad interface do not have operations to get rid of the monad around our value. Other (not IO) monads provide such operations and allow pattern matching (e.g. Maybe), but those operations are not in monad interface. Another required property is ability to chain operations.

If we think about what we need in terms of type system, we come to the fact that we need type with constructor, which can be wrapped around any vale. Constructor must be private, as we prohibit escaping from it(i.e. pattern matching). But we need function to put value into this constructor (here return comes to mind). And we need the way to chain operations. If we think about it for some time, we will come to the fact, that chaining operation must have type as >>= has. So, we come to something very similar to monad. I think, if we now analyze possible contradictory situations with this construct, we will come to monad axioms.

Note, that developed construct do not have anything in common with impurity. It only have properties, which we wished to have to be able to deal with impure operations, namely, no-escaping, chaining, and a way to get in.

Now some set of impure operations is predefined by the language within this selected monad IO. We can combine those operations to create new unpure operations. And all those operations will have to have IO in their type. Note however, that presence of IO in type of some function do not make this function impure. But as I understand, it is bad idea to write pure functions with IO in their type, as it was initially our idea to separate pure and impure functions.

Finally, I want to say, that monad do not turn impure operations into pure ones. It only allows to separate them effectively. (I repeat, that it is only my understanding)

Dmitrii Semikin
  • 2,134
  • 2
  • 20
  • 25
  • 1
    They help you type check your program by letting you type check effects, and you can define your own DSLs by creating monads to restrict the effects that your functions can do so compiler can check your sequencing errors. – aoeu256 Aug 06 '19 at 01:20
  • This comment from aoeu256 is the "why" that's missing in all the explanations given so far. (i.e: monads are not for humans, but for compilers) – João Otero Jul 09 '20 at 13:27
  • Monads are also for humans in that a they let you represent in types what your sort of side-effects can be allowed in a certain piece of code or function. In Haskell a type is a "compiler enforced comment". They were originally pioneered by Moggi so that you could let the analyze by types what a sequence of statements mean. Like Either is the reification of if-else statements into the type system. – aoeu256 Mar 23 '21 at 14:48
  • Map,filter, fold are the reifications of loop strategies, structured programming (while, subroutines, break, if-else) are reifications of goto. Pure functions are reification of non-contextual computations. Monads are the reification of contextual computations, semicolons, statements, computations, catanable applicatives, semantics of languages with statements, and languages with statements. – aoeu256 Mar 23 '21 at 15:06