[Haskell-cafe] Re: [Haskell] Monads Terminology Question

[Conor McBride]

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