Is IO a Free Monad?

Question

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?

Answer 1

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.