10

In blog posts and examples by Mark Seemann, I got a first glimpse of free monads as a way to structure the boundary between pure code and IO code. My basic understanding is that a free monad lets you build a program (an abstract syntax tree - AST) of pure functions that an interpreter then translates into a sequence of impure procedure calls. Hence, this interpreter turns the pure operations of the AST into a sequence of monadic IO actions.

I'm wondering if this is duplicating what the Haskell runtime is already doing with the IO monad. If I view IO as nothing special, but a regular Monad whose bind function >>= sequences the state of the "Real World" through all monadic operations in IO, then this sequencing does not provide any computation on its own (as explained for free monads in the excellent answer here). I can then view all IO actions like getLine, writeFile and the like as operations in the free IO monad, and the Haskell runtime as the interpreter. The runtime interprets each IO action by means of some underlying system call, C FFI call or the like, which is obviously impure.

So, in this view, functions that return IO actions are simply building up the AST that then gets interpreted by the Haskell runtime. But up to this point, everything is pure. In this view, a function a -> IO b is not impure, in the same way that an operation of in a free monad is not impure.

Is this intuition correct? If not, where does it fall short?

Ulrich Schuster
  • 1,670
  • 15
  • 24
  • the key distinction here is that new program can be built according to the value produced by *running* the previous one, *after* that program was interpreted and actually run. so it's not like one combined tree known upfront in full (that would be an Applicative, not a Monad); it's being built as we go. – Will Ness May 15 '20 at 15:41
  • @WillNess This is true for both `IO` and free monads – Fyodor Soikin May 15 '20 at 15:54
  • just wanted to stress that point. – Will Ness May 15 '20 at 16:07

1 Answers1

13

Your intuition is correct: the IO-typed functions do indeed build up a tree of actions, which is then interpreted by the runtime. Well, at least this is a valid way of looking at it (see also Will Ness's comment).

The difference from a free monad is that there is just one interpreter. You can't pick another one, and you can't implement your own if you wanted to.

The AST of the free monad has two principal properties: first, it's compositional; second, it's analyzable. The interpreter can analyze the AST by matching on its constructors, and perform the interpretation accordingly.

The IO monad shares the first of these properties, but not the second. If you have a value IO String, there is no way to tell if it was created by calling readLn or pure "foo" or something else.

Fyodor Soikin
  • 78,590
  • 9
  • 125
  • 172
  • Regarding the second property, isn't that because there is only one constructor (buried in the depths of the implementation), and things like `readLn` (if you think of it as a type-level function with kind `Type -> IO Type` and `pure` just use that constructor? – chepner May 15 '20 at 13:51
  • 2
    @chepner Yes, that's another semi-valid way of looking at it: you can say that `IO` is a free monad with [only one operation](https://www.stackage.org/haddock/lts-15.12/ghc-prim-0.5.3/src/GHC-Types.html#line-187), which is named "_call this function_". I would argue that it's precisely the fact that all possible operations are represented as one that makes it lack the second property. – Fyodor Soikin May 15 '20 at 14:04