Hi (Redirecting to cafe, for general chat.) On 12 Apr 2010, at 01:39, Mark Snyder wrote:
Hello,
I'm wondering what the correct terminology is for the extra functions that we define with monads. For instance, State has get and put, Reader has ask and local, etc. Is there a good name for these?
Yes. Indeed, quite a lot of energy has been expended on the matter. It's worth checking out work by Plotkin and others on "Algebraic Effects" (often transmitted around Haskell-land by helpful citizens like Dan Piponi and Heinrich Apfelmus). This work distinguishes two kinds of "extra function": operations (e.g. get, put, ask, throwError, etc) and control operators (local, catchError, etc). *Operations* have types like s1 -> ... sn -> M t where the s's and t are thought of as "value" types, and M is yer monad. You can think of M as describing an "impure capability", permitting impure functions on values. You might even imagine specifying M's collection of operations by a signature, with this made up notation. sig M where f s1 ... sn :: t Note that I'm careful to mark with :: where the inputs stop and the outputs start, as higher-order functions make this ambiguous. For example sig State s where get :: s put s :: () sig Reader r where ask :: r sig Maybe where throw :: a Many popular monads can be characterized exactly by the signature of their operations and the equational theory those operations must obey (e.g. laws like put s >> get >>= f == put s >> f s). The point of these monads is to deliver the capability specified by the operations and equations. The similiarity between the signatures above and the typeclasses often declared to support monadic functionality is no coincidence. Note that every (set of) signature(s) induces a datatype of command-response trees whose nodes are labelled with a choice of operation and inputs, whose edges are labelled with outputs, and whose leaves carry return values. Such a tree represents a "client strategy" for interacting with a server which offers the capability, at each step selecting an operation to perform and explaining how to continue as a function of the value returned. The equational theory of the operations induces an equivalence on strategies. Command-response trees up to operational equivalence give the most general implementation of the specified monad: return makes leaves, >>= pastes trees together, and each operation creates a node. The monad comes from its operations! But what of local, catchError, and other such things? These are *control operators*, and they operate on "computations", with types often involving resembling a -> (b -> M c) -> M d Typically, the job of a control operator is to make local changes to the meaning of the operations in M's signature. A case in point is "local", whose job is to change the meaning of "ask". It's really shadowing one reader capability with another. Similarly, catchError can be thought of as offering a local exception. Old LISPheads (like me!) might think of operations as EXPRs and control operators as FEXPRs. Haskell does a neat job of hiding the distinction between the two, but it may be conceptually helpful to dig it out a bit. Control operators don't give rise to nodes in command-response trees; rather, they act as tree transformers, building new strategies from old. I could start a pantomime about why operations are heroes and control operators are villains, but I won't. But I will suggest that characterising monads in terms of the operations and/or control operators they support is a useful (and increasingly modular) way to manage effects in programming. After all, most end-user applications effectively equip a bunch of user-operations with a semantics in terms of system-operations. All the best Conor