Nice read. I'm not familiar with Lucid, so invocations of "fby" and so forth went over my head, but finding that there's an abstraction available to encapsulate and explain a lot of behaviour in a consistent way is always a good win.

The "output monad" described is usually called the Writer monad - you can append to a log, but you can't do anything based on what was in it. It can be generalised from strings to any monoid - a domain that has an empty value and an associative concatenation function.

The IO monad, as another commenter said, is a kind of state monad where the state is something ineffable from within the computing environment: it's the state of the world outside the program. But there's no need to rush to trying to fit the IO monad to this model - we can start with the "reader monad".

An element of D* for the reader monad is a function from an element of some specified domain R to an element of D. The mapping from D to D* is a constant function that produces D no matter what the argument to the function in D* is. D's elements are functions from R to D* so the collapse is function composition and therefore associative. Likewise, f* from D* to E* is function composition, which composes, obeys the embedding of D into D* and since both collapse and embedding functions is function composition f* * (s')V == f* (s'V).

The reader monad is sometimes called the environment monad, because there's some environment (the value from R) that is available to all computation. The key thing it gives us for this article's model of monads is that elements of D* don't have to just be pairs, they can be functions.

Sort of combining the Reader and Writer monads gives us a monad where an element of D* is a function from an element of the domain S to a pair from (D, S). The embedding from D to D* is the function that copies its input state to its output pair. The collapse from D is composition with application. An element of D* * is a function S -> (D* , S), or S -> (S -> (D, S), S); apply the function in the pair to the state in the pair and you get S -> (D, S). D* * * is the further nesting of this structure, S -> (S -> (S -> (D, S), S), S). Evaluating this is associative: either way you will pass the initial state through each function in the same order to get the final output state. Embedding a function also satisfies the laws; effectively it will transform the final output D and leave the state S alone.

The collapsing of State to ensure its functions are always evaluated in the same order is how the IO monad provides sequentiality of effects. The state is "everything outside the program" - the user, the keyboard, the network, the operating system, even parts of the interpreter state that are not typically open to program inspection, perhaps allocations or bit-level representations.

An element of D* for the IO monad can read from the state of "everything outside", seeing whether the operating system has a character in its console input buffer perhaps. It can modify the state of "everything outside" by writing a character to the OS console buffer. And it preserves the order of these things because of how collapse is defined.

It also needs a magic interpreter that can provide the initial state of the world and maintain it as the program updates that state, along with magic primitives that can make changes to an ineffable "real world" state.