What other ways can state be handled in a pure functional language besides with Monads?

So I started to wrap my head around Monads (used in Haskell). I'm curious what other ways IO or state can be handled in a pure functional language (both in theory or reality). For example, there is a logical language called "mercury" that uses "effect-typing". In a program such as haskell, how would effect-typing work? How does other systems work?

Solution 1:

There are several different questions involved here.

First, IO and State are very different things. State is easy to do yourself: Just pass an extra argument to every function, and return an extra result, and you have a "stateful function"; for example, turn a -> b into a -> s -> (b,s).

There's no magic involved here: Control.Monad.State provides a wrapper that makes working with "state actions" of the form s -> (a,s) convenient, as well as a bunch of helper functions, but that's it.

I/O, by its nature, has to have some magic in its implementation. But there are a lot of ways of expressing I/O in Haskell that don't involve the word "monad". If we had an IO-free subset of Haskell as-is, and we wanted to invent IO from scratch, without knowing anything about monads, there are many things we might do.

For example, if all we want to do is print to stdout, we might say:

type PrintOnlyIO = String

main :: PrintOnlyIO
main = "Hello world!"

And then have an RTS (runtime system) which evaluates the string and prints it. This lets us write any Haskell program whose I/O consists entirely of printing to stdout.

This isn't very useful, however, because we want interactivity! So let's invent a new type of IO which allows for it. The simplest thing that comes to mind is

type InteractIO = String -> String

main :: InteractIO
main = map toUpper

This approach to IO lets us write any code which reads from stdin and writes to stdout (the Prelude comes with a function interact :: InteractIO -> IO () which does this, by the way).

This is much better, since it lets us write interactive programs. But it's still very limited compared to all the IO we want to do, and also quite error-prone (if we accidentally try to read too far into stdin, the program will just block until the user types more in).

We want to be able to do more than read stdin and write stdout. Here's how early versions of Haskell did I/O, approximately:

data Request = PutStrLn String | GetLine | Exit | ...
data Response = Success | Str String | ...
type DialogueIO = [Response] -> [Request]

main :: DialogueIO
main resps1 =
    PutStrLn "what's your name?"
  : GetLine
  : case resps1 of
        Success : Str name : resps2 ->
            PutStrLn ("hi " ++ name ++ "!")
          : Exit

When we write main, we get a lazy list argument and return a lazy list as a result. The lazy list we return has values like PutStrLn s and GetLine; after we yield a (request) value, we can examine the next element of the (response) list, and the RTS will arrange for it to be the response to our request.

There are ways to make working with this mechanism nicer, but as you can imagine, the approach gets pretty awkward pretty quickly. Also, it's error-prone in the same way as the previous one.

Here's another approach which is much less error-prone, and conceptually very close to how Haskell IO actually behaves:

data ContIO = Exit | PutStrLn String ContIO | GetLine (String -> ContIO) | ...

main :: ContIO
main =
    PutStrLn "what's your name?" $
    GetLine $ \name ->
    PutStrLn ("hi " ++ name ++ "!") $
    Exit

The key is that instead of taking a "lazy list" of responses as one big argument at he beginning of main, we make individual requests that accept one argument at a time.

Our program is now just a regular data type -- a lot like a linked list, except you can't just traverse it normally: When the RTS interprets main, sometimes it encounters a value like GetLine which holds a function; then it has to get a string from stdin using RTS magic, and pass that string to the function, before it can continue. Exercise: Write interpret :: ContIO -> IO ().

Note that none of these implementations involve "world-passing". "world-passing" isn't really how I/O works in Haskell. The actual implementation of the IO type in GHC involves an internal type called RealWorld, but that's only an implementation detail.

Actual Haskell IO adds a type parameter so we can write actions that "produce" arbitrary values -- so it looks more like data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | .... That gives us more flexibility, because we can create "IO actions" that produce arbitrary values.

(As Russell O'Connor points out, this type is just a free monad. We can write a Monad instance for it easily.)

Where do monads come into it, then? It turns out that we don't need Monad for I/O, and we don't need Monad for state, so why do we need it at all? The answer is that we don't. There's nothing magical about the type class Monad.

However, when we work with IO and State (and lists and functions and Maybe and parsers and continuation-passing style and ...) for long enough, we eventually figure out that they behave pretty similarly in some ways. We might write a function that prints every string in a list, and a function that runs every stateful computation in a list and threads the state through, and they'll look very similar to each other.

Since we don't like writing a lot of similar-looking code, we want a way to abstract it; Monad turns out to be a great abstraction, because it lets us abstract many types that seem very different, but still provide a lot of useful functionality (including everything in Control.Monad).

Given bindIO :: IO a -> (a -> IO b) -> IO b and returnIO :: a -> IO a, we could write any IO program in Haskell without ever thinking about monads. But we'd probably end up replicating a lot of the functions in Control.Monad, like mapM and forever and when and (>=>).

By implementing the common Monad API, we get to use the exact same code for working with IO actions as we do with parsers and lists. That's really the only reason we have the Monad class -- to capture the similarities between different types.

Solution 2:

Another major approach is uniqueness typing, as in Clean. The short story is that handles to state (including the real world) can only be used once, and functions that access mutable state return a new handle. This means that an output of the first call is an input of a second, forcing the sequential evaluation.

Effect typing is used in the Disciple Compiler for Haskell, but to the best of my knowledge it would take considerable compiler work to enable it in, say, GHC. I shall leave discussion of the details to those better-informed than myself.

Solution 3:

Well, first what is state? It can manifest as a mutable variable, which you don't have in Haskell. You only have memory references (IORef, MVar, Ptr, etc.) and IO/ST actions to act on them.

However, state itself can be pure as well. To acknowledge that review the 'Stream' type:

data Stream a = Stream a (Stream a)

This is a stream of values. However an alternative way to interpret this type is a changing value:

stepStream :: Stream a -> (a, Stream a)
stepStream (Stream x xs) = (x, xs)

This gets interesting when you allow two streams to communicate. You then get the automaton category Auto:

newtype Auto a b = Auto (a -> (b, Auto a b))

This is really like Stream, except that now at every instant the stream gets some input value of type a. This forms a category, so one instant of a stream can get its value from the same instant of another stream.

Again a different interpretation of this: You have two computations that change over time and you allow them to communicate. So every computation has local state. Here is a type that is isomorphic to Auto:

data LS a b =
    forall s.
    LS s ((a, s) -> (b, s))