Lambda the Ultimate

Here is the longer quotation from Jonathan M. D. Hill and Keith Clarke: An Introduction to Category Theory, Category Theory Monads, and Their Relationship to Functional Programming. 1994.

Monads are typically equated with single-threadedness, and are therefore used as a technique for incorporating imperative features into a purely functional language. Category theory monads have little to do with single-threadedness; it is the sequencing imposed by composition that ensures single-threadedness. In a Wadler-ised monad this is a consequence of bundling the Kleisli star and flipped compose into the bind operator. There is nothing new in this connection. Peter Landin in his Algol 60 used functional composition to model semi-colon.

Please see http://okmij.org/ftp/Computation/IO-monad-history.html
for the full quotation and exposition of Peter Landin's remarkable and remarkably prescient contributions.

Therefore, it is a mistake to think of any construction that enforces the execution order as a monad. Incidentally, Applicatives also enforce execution order, and some applicatives are not monads (for example, code-generating applicatives, sort of an antiquotation facilities). To see if something is a monad, identify the two necessary operations and check the monad laws. By the same token, to see if something is a monoid, find an operation that combines the two instances of the thing and check if it is an associative and there is the unit element.

I'm not ever-so sure whether you mean 'nested' or just sequenced?

• Sequenced SQL statements might be implemented through monads -- which is like taking semi-colon as function composition, as Oleg refers to. That's because they must be single-threaded in the sense that the first statement must update the database in case the second depends on its result. (Using monads was the approach for example in 'Domain-Specific Embedded Compilers' Meijer & Leijen 1999.)

  [This is more complex than sequential statements in procedural languages, because SQL typically operates in a multi-user environment. So as well as making the updated database 'available' to the next statement in sequence, it must also be 'published' to all other users of the database. That is, each statement is evaluated in the IO monad. And then we'd have to start into talking about commitment control ...]

• But no, nested SQL doesn't need monads any more than any nested term within an expression. For instance:

  UPDATE r SET x = MAX(SELECT z FROM s WHERE r.y = s.y)

  There's no implied order of execution of the sub-select, and the server is at liberty (for example) to tackle the rows of r in parallel, and could scan the rows of s 'at random'.

In Haskell:
x = max (max z1 z2) (max z3 z4)

There's no implied order of execution. Again, the code could evaluate the z's and the max's in parallel.

x = maximum (map z ys) -- where z is a field selector

In the Haskell there's no monad in sight, but there's a kinda order of execution because both maximum and map are folds, so apply from head to tail as it were. (And maximum has to evaluate the whole list to find the geatest element -- but the folds only generate thunks; the order of evaluation thereof is undefined.)

There is a close correspondence between the core of SQL (not including aggregation or sorting) and a monad, and hence between SQL and list comprehensions. This was originally observed by Trinder and Wadler, and exploited by Buneman, Libkin, Tannen, and Wong to define the influential database languages NRC (theory) and Kleisli (practice). The same insights underly Microsoft's LINQ.

P Trinder, P Wadler. Improving list comprehension database queries. TENCON'89. Fourth IEEE Region 10 International Conference, 186-192

P. Buneman, L. Libkin, D. Suciu, V. Tannen, and L. Wong. Comprehension Syntax. SIGMOD Record, 23(1):87-96, March 1994.

Limsoon Wong. Kleisli, a functional query system. Journal of Functional Programming 10(1): 19-56 (2000).

Erik Meijer, Brian Beckman, Gavin M. Bierman: LINQ: reconciling object, relations and XML in the .NET framework. SIGMOD Conference 2006: 706.

The following paper is probably relevant:

www.informatik.uni-kiel.de/~mh/papers/PADL08.pdf

In the paper they use an I/O monad to model inserts/updates.