Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is IO a Free Monad?

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?

like image 696
Ulrich Schuster Avatar asked May 15 '20 13:05

Ulrich Schuster


People also ask

What is the IO monad?

The Quantum IO monad is a purely functional interface to quantum programming implemented as a Haskell library. At the same time it provides a constructive semantics of quantum programming.

Why free monads?

A Free Monad allows you to sequence an operation 'functor' as though it were a monad. This means you can control the operation order. You can pass to subsequent operations any return values from previous operations.

Is Io A impure?

The presence of the IO type constructor means a function is impure, just as the absence of the const keyword in C/C++ means data might be modified. Loosely speaking, within a do block, the output of one line becomes the input of the next.

What is state monad?

The state monad is a built in monad in Haskell that allows for chaining of a state variable (which may be arbitrarily complex) through a series of function calls, to simulate stateful code.


1 Answers

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.

like image 65
Fyodor Soikin Avatar answered Oct 07 '22 19:10

Fyodor Soikin