<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:'times new roman', 'new york', times, serif;font-size:12pt"><div></div><div style="font-family:times new roman, new york, times, serif;font-size:12pt"><div style="font-family:arial, helvetica, sans-serif;font-size:10pt"><font size="2" face="Tahoma"><b><span style="font-weight: bold;"><meta charset="utf-8"><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif; font-weight: normal; font-size: 13.3333px; ">></span>From:</span></b> Conor McBride <conor@strictlypositive.org><br><b><span style="font-weight: bold;"><meta charset="utf-8"><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif; font-weight: normal; font-size: 13.3333px; ">></span>To:</span></b> Mark Snyder <muddsnyder@yahoo.com>; haskell Cafe <haskell-cafe@haskell.org><br><b><span style="font-weight: bold;"><meta
charset="utf-8"><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif; font-weight: normal; font-size: 13.3333px; ">></span>Sent:</span></b> Mon, April 12, 2010 5:34:05 AM<br><b><span style="font-weight: bold;"><meta charset="utf-8"><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif; font-weight: normal; font-size: 13.3333px; ">></span>Subject:</span></b> Re: [Haskell] Monads Terminology Question<br></font><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Hi<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>(Redirecting to cafe, for general chat.)<br><meta charset="utf-8"><span class="Apple-style-span"
style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>On 12 Apr 2010, at 01:39, Mark Snyder wrote:<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> Hello,<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>> <br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>> I'm wondering what the correct terminology is for the extra functions that we define with monads. For instance, <span class="Apple-style-span" style="font-size: 13.3333px; ">><span class="Apple-style-span" style="font-size: 13.3333px; ">State has get and put, Reader has ask and local, etc. Is there a good name for
these?</span></span></div><meta charset="utf-8"><div style="font-family:arial, helvetica, sans-serif;font-size:10pt"><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Yes. Indeed, quite a lot of energy has been expended on the matter.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>It's worth checking out work by Plotkin and others on "Algebraic<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Effects" (often transmitted around Haskell-land by helpful citizens<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>like Dan Piponi and Heinrich Apfelmus).<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span></div><div
style="font-family:arial, helvetica, sans-serif;font-size:10pt"><span class="Apple-style-span" style="font-size: 13.3333px; "></span><meta charset="utf-8"><span class="Apple-style-span" style="font-family: 'times new roman', 'new york', times, serif; font-size: 15.8333px; "><div><br></div><div>Thanks! I wasn't aware of that work. It certainly does split things up nicely, I hadn't really thought of looking at them as two distinct groups of functionality. It also clears things up in my mind to look at them as the maximum-arity functions and seeing whether any arguments are computations, or whether the function just constructs a computation.</div><div style="font-family: 'times new roman', 'new york', times, serif; font-size: 12pt; "><br><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt; "><font size="2" face="Tahoma"></font></div></div></span><meta charset="utf-8"><span class="Apple-style-span" style="font-size:
13.3333px; ">></span>This work distinguishes two kinds of "extra function": operations<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>(e.g. get, put, ask, throwError, etc) and control operators (local,<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>catchError, etc).<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>*Operations* have types like<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> s1 -> ... sn -> M t<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span
class="Apple-style-span" style="font-size: 13.3333px; ">></span>where the s's and t are thought of as "value" types, and M is yer<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>monad. You can think of M as describing an "impure capability",<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>permitting impure functions on values. You might even imagine<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>specifying M's collection of operations by a signature, with this<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>made up notation.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> sig M where<br><meta
charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> f s1 ... sn :: t<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Note that I'm careful to mark with :: where the inputs stop and<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>the outputs start, as higher-order functions make this ambiguous.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>For example<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> sig State
s where<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> get :: s<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> put s :: ()<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> sig Reader r where<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> ask :: r<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> sig Maybe where<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> throw :: a<br><meta
charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Many popular monads can be characterized exactly by the signature<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>of their operations and the equational theory those operations<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>must obey (e.g. laws like put s >> get >>= f == put s >> f s).<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>The point of these monads is to deliver the capability specified<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>by the operations and equations. The similiarity between the<br><meta charset="utf-8"><span
class="Apple-style-span" style="font-size: 13.3333px; ">></span>signatures above and the typeclasses often declared to support<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>monadic functionality is no coincidence.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Note that every (set of) signature(s) induces a datatype of<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>command-response trees whose nodes are labelled with a choice<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>of operation and inputs, whose edges are labelled with outputs,<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>and whose leaves
carry return values. Such a tree represents<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>a "client strategy" for interacting with a server which offers the<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>capability, at each step selecting an operation to perform and<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>explaining how to continue as a function of the value returned.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>The equational theory of the operations induces an equivalence<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>on strategies. Command-response trees up to operational<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>equivalence give the
most general implementation of the specified<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>monad: return makes leaves, >>= pastes trees together, and each<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>operation creates a node. The monad comes from its operations!<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>But what of local, catchError, and other such things? These are<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>*control operators*, and they operate on "computations", with<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>types often involving resembling<br><meta charset="utf-8"><span
class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span> a -> (b -> M c) -> M d<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Typically, the job of a control operator is to make local changes<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>to the meaning of the operations in M's signature. A case in<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>point is "local", whose job is to change the meaning of "ask".<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>It's really shadowing one reader capability with another.<br><meta
charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Similarly, catchError can be thought of as offering a local<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>exception.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>Old LISPheads (like me!) might think of operations as EXPRs and<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>control operators as FEXPRs. Haskell does a neat job of hiding<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>the distinction between the two, but it may be conceptually<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>helpful to dig it out a bit.
Control operators don't give<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>rise to nodes in command-response trees; rather, they act as<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>tree transformers, building new strategies from old.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>I could start a pantomime about why operations are heroes and<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>control operators are villains, but I won't. But I will suggest<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>that characterising monads in terms of the operations and/or<br><meta charset="utf-8"><span
class="Apple-style-span" style="font-size: 13.3333px; ">></span>control operators they support is a useful (and increasingly<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>modular) way to manage effects in programming. After all,<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>most end-user applications effectively equip a bunch of<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>user-operations with a semantics in terms of system-operations.<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span>All the best<br><meta charset="utf-8"><span class="Apple-style-span" style="font-size: 13.3333px; ">></span><br><meta charset="utf-8"><span class="Apple-style-span"
style="font-size: 13.3333px; ">></span>Conor<br><br></div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt">So in this line of thought, where we have the operations and the control operators, I guess my original question wasn't aware of the distinction, and was looking for a name for all of them combined. In Haskell (specifically in the mtl), we see them lumped together into the typeclass. If we are talking about an implementation, is it good practice to try and use the most theoretically correct language, even if an implementation diverges somewhat while getting things done? I.e., should they be referred to as the operations and control operators, or more simply as the "type-class-provided functions"? I like the idea of trying to use more formal names, but I don't want to be implying that an implementation is an exact representation of the underlying concept. For instance, the functional dependency
in the mtl library is seen as an implementation choice, and I think some people prefer versions without the dependency. In what sense is it fair to say that Control.Monad.State _is_ a monad, as opposed to saying that it _represents_ a monad? Maybe it just suffices to say the (e.g. MonadState) typeclass represents the operations and control operators. </div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt"><br></div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt">Thanks for shining a light on the question!</div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt"><br></div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt">~Mark</div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt"><br></div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt"><br></div><meta charset="utf-8"><meta charset="utf-8"><meta
charset="utf-8"></div><div style="position:fixed"></div>
</div><br>
</body></html>