Following the program of Moggi, the semantics of a simple non-deterministic functional language with recursion and failure is described by a monad. We show that this monad cannot be any of the known power domain constructions, because they do not handle non-termination properly. Instead, a novel construction is proposed and investigated. It embodies both non-determinism (choice and failure) and possible non-termination caused by recursion.
[Paper.ps.gz (17p, 74k)]