Lambda the Ultimate

One that can return multiple answers. The identity monad's valid, as is the one that just sends everything to _|_.

Is that an agreement or a disagreement?

My original statement doesn't cover all the cases. You might have several answers for a given query, different answers for the same query depending on a state, etc. I have in mind a decomposed automata description where each partition has one state if possible, otherwise more than one. The single state partitions correspond to pure functions. This seems like a complete picture of a computation and therefore it should correspond to the monad view of a system. Yes. No. would really like to get to the bottom of this.

Apparently a reading error on my part :-) We appear to be agreeing violently - still, quirky monad examples're useful to have around.

Yea! Yea!

Well, maybe he wants to make an introduction to Monads for 'imperative' programmers which doesn't start by "in the category theory", a sure way to loose the reader..

Where do I mention category theory? (Really curious now because I know only very little of CT) I didn't even start 'A monad is a type constructor ...'.

Another way to lose readers is to make it so simple that you make them believe it's just a crutch to be able to do in a pure functional language what you can do in an imperative one any time of the day. I just think that sequencing is one of the less interesting things about monads, and I say that as a long long time imperative programmer.

I'd say that the structure's support for sequencing is pretty fundamental - but the number of different notions of sequencing you can work with is much more interesting! State, Reader and List all behave rather differently.

Just what I meant. When I said 'less interesting' I did not mean to imply it's not important or a minor aspect.

I think most of the other things that're interesting about monads apply to things like Arrows and Applicative Functors too (they support sequencing too though, just not in a way that by default allows higher-order computations the way monads do).

Analogizing something I can manipulate mechanically but can't say I understand with other stuff I can manipulate mechanically but can't say I understand. This does not bode well...

My early introduction to OO style was very frustrating, with the magic of inheritance, then I read 'how' it was implemented which allowed me to understand it better and then I read OOSC from B. Meyer and I understood 'why': I doubt I would have been receptive to the 'why' until I've read 'how'.
Other couldn't care less about the implementation details: to each his own.

[And no, I don't 'truly' understand monad but the 'imperative view' is good enough for me]

Actually functions and function composition do form a monad (specifically, the identity monad). Hope that helps!

Oh...

Ok, i need to read up on Identity monad. Thx.

No the question is not "what's so special.." but rather "what's so general..". Monads doesn't do any specific thing, but is more of an implementation method that can be used for well, nearly everything.

While it is true that some specific monads can be used to hide internal mutable state (for some sense of 'hide', 'internal', 'mutable' and 'state'), there is no necessary connection between monads and mutable state. For example there is no mutable state associated with the list, continuation, probability, Identity, Maybe and Reader monads.

Monads are an abstraction that capture a design pattern. It's a common design pattern that appears in many different contexts. But don't confuse the specific applications with monads in general.

There is (except perhaps in cases like Identity) something that smells a lot like the state of an abstract machine associated with monads as used in Haskell though.

...but I think that this 'smell' might be a trivial observation. There are many types that are instances of Monad. All instances of Monad share a common interface (return and >>=) and (are supposed to) exhibit the monad laws. Therefore, given your favourite Monad m, then any other random Monad, m', is going to have similarities to m, and appear to justify the view that all Monads are like m.

Hence we have people who think that Monads are about sequencing, state, computations and so on.

But a properly 'Copernican' view would be that all of these things have something in common, but no one is more fundamental than the others.

Identity is a rather specific case though - Derek and I found a couple more examples kicking the idea around on IRC (both variations on the Const monad where everything gets sent to the same value). But we didn't find any non-trivial monads it made no sense at all for, the big change to the model was that rather than adding state to the machine it's modifying it - List clones/branches it, Identity leaves it untouched, Const eliminates it.

There is (except perhaps in cases like Identity) something that smells a lot like the state of an abstract machine associated with monads as used in Haskell though.

Of course any monadic computation can be expressed as an abstract machine, but that doesn't automatically correspond to mutable state (which is what sigfpe was talking about). For example, a monadic model of a pure lambda calculus evaluator might use an environment monad, but there's no mutable state there.

OK, so i got it wrong that having internal state is a defining characteristics of monad. But, Maybe monad, doesn't it hide the error/fail state so that the error state can be "propagate up" implicitly?

I re-read the monad stuff (in Haskell). Please correct me if I got any of the following things wrong:

At its minimal,
1. An instance of Monad is a type constructor
2. It needs to define at least the (>>=) operator
3. and the return functions.

To me, I can easily relate these to
1. An ADT (or object) constructor
2. a "wrap" method
3. an "unbox" method. (as in C#)

Hence, i got the "is just like Object" analogy.

As others in this thread have intimated, one of the reasons there are so many "what is a monad?" threads is that monads are a very general idea with many specific uses that unfortunately all go by the same name as the general one.

Imagine if you will a world where monoids, linear grammars, regular expressions (as a general concept) and the specific notation of Perl regular expressions were all referred to as "monoids" and you would have a rough analogy.

We take it for granted that each of these things can be understood independently, and that it requires a lot of thought and study to see how they are related. This is made easier by the distinct terminology.

With monads, when you ask "What is the essence of monads?" you get very confusing responses because the term "monad" is used indiscriminately to describe a very general mathematical structure rooted in Category Theory, a theoretical PLT concept based on the former, but with a strong functional programming grounding, as well as particular constructs implemented in particular languages, most notably Haskell.

Unless you know which one your interested in, it is hard to give a pithy explanation to suit your purposes.

Furthermore, someone who has never programmed in an FP language will probably not appreciate either of the latter two uses of the term.

For this reason, trying to explain monads to "imperative programmers" (i.e. people unwilling to learn an FP language or spend the time on the theory) is probably a waste of time.

It's worth bearing in mind that Haskell's idea of a monad is an instance of the PLT concept and the mathematical structure - even if (sometimes aggravatingly) the Monad typeclass doesn't capture all possible instances in Haskell. The addition of >>= is perhaps a little more confusing.

Philippa, what do you mean by "The addition of >>= is perhaps a little more confusing"?

The categorical definition uses the equivalents of fmap and join instead - you can define >>= in terms of fmap and join, and you can define fmap and join in terms of >>=.

But wouldn't an "imperative programmer" inevitably discover monads when he'd reason about design pattern for generic programming? The basic problem for understanding is IMO the step from a type parameter b to a very general opaque type m b depending on b. You can't spell this in C#, Java or C++. These languages with their template parameters are not expressive enough to give meaning to such a notion. You can't say: "here I hand out a general abstraction of a class depending on two type parameters T and V" but you need a concrete class depending on these type parameters.

Of course the monadic definition contains an element of functional programming since it defines machinery for restoring function composition for functions f : a -> m b. Once the programmer sees that this machinery is available and gained even syntactical support she will look for use cases and those give the impression of arbitrariness ( because there is one for each type class m ). FP is not really the hurdle for proper understanding.

If a language ( god beware us of C++ ) would start dealing with class abstractions and consider classes with type parameters as instantiations of metaclasses with type parameters we had sooner or later monads for the masses ( maybe Haskell will be faster and the masses are programming in Haskell? Fortunately I'm not in language advocation business. )

But wouldn't an "imperative programmer" inevitably discover monads when he'd reason about design pattern for generic programming?

To me this doesn't make any more sense than, to continue my analogy, saying that any programmer who thinks about regular expressions will inevitably discover monoids.

Many people master the former without having an inkling of the latter, or if they have such an inkling, why they are related and why they should care.

FP is not really the hurdle for proper understanding

Without an understanding of accumulator passing (and why you want to do it), or the constraint of statefulness (and what that gives you), I don't think you can have any sensible intuitions about what (PLT) monads are all about.

For an imperative programmer, the easiest way to do what monads do is going to be using unconstrained stateful operations; to understand the motivations for them, you need to have a basic idea about FP, how it works and why you want to use it.

To me this doesn't make any more sense than, to continue my analogy, saying that any programmer who thinks about regular expressions will inevitably discover monoids.

Right, but there was nothing inductive in my remark. It was you who insisted in the need of lots of concrete intuitions about PLT use cases to understand a very particular algebraic structure. I claimed quite the opposite and said that people have to be accustomed to deal and play with an expressive type system to make sense of particular pattern. Some of them may be important to the needs of purely functional programming. It's easy to see why and there is even syntactical support. So what?

So, what's relationship between monad and continuation?

Incidentally, this paper I was just reading may have your answer. It discusses monadic, continuation-based, and A-normal form-based intermediate languages.

So, what's relationship between monad and continuation? Is it just monad provides a way to implement continuation style of chaining?

Monads use continuation-passing style to make control flow explicit. This allows them to enforce sequencing (particularly in a lazy language like Haskell), and also to manipulate control flow in other ways (e.g. the Maybe monad, the Continuation monad).

Monads in the PL context are a kind of generalization of CPS: values passed to continuations in monadic computations are wrapped in an arbitrary container datatype which can contain additional information, and the 'bind' operation provides a datatype-specific hook to unwrap the values in these containers and possibly perform additional operations whenever a continuation is invoked. This is a very general pattern — it's actually a purely functional way to represent interpreters, which is the context in which monads originally arose in PL theory. As a result, the possible applications of monads are very broad.

Having said that, I'd like to suggest that these sort of "help me understand monads" threads are a little offtopic for LtU. There's plenty of material on the web about monads — see the Monad tutorials timeline. Monads are an interesting topic with a lot of relevance to PL theory and practice, but for an initial understanding of them there's no substitute for a bit of studying and writing code using monads in an appropriate language (which practically speaking, probably means Haskell). There's plenty of material on the LtU Getting Started page about these topics.

I've been kind of wondering whether the emphasis on "how useful monads can be" has short-circuited the question of language design? That is, are there ways to design PLs that make monads easier to manipulate and/or easier to learn (or tutorialize)? And is having one generalized way to construct monads better than having language constructs that have specific monads built in (states/worlds, etc...)?

I've been kind of wondering whether the emphasis on "how useful monads can be" has short-circuited the question of language design?

Perhaps in threads like these. But I doubt that the insatiable desire of programmers to find a problem for every solution is significantly affecting people working in PL research any more than it usually does.

That is, are there ways to design PLs that make monads easier to manipulate and/or easier to learn (or tutorialize)?

Monads provide a kind of balance between rigor and formal simplicity. The relationship between rigor and ease of use is usually an inverse one. Even formal simplicity doesn't necessarily translate into ease of use outside of a (meta)mathematical context — if it did, then the pure untyped lambda calculus would be one of the easiest to use programming languages. I suspect that if you want to retain both properties, that there may not be much room for ease of use improvements when using monads directly.

OTOH, a typical imperative language can be modeled as a monad which carries an environment, a store, and various other bits and pieces (depending on the language). Manipulating this monad is pretty easy: people do it in all the usual imperative languages, all the time. So we already know one way to make monads easier to use. I guess one question is whether there's a useful middle ground between the two approaches, other than what existing languages (e.g. ML) already provide.

And is having one generalized way to construct monads better than having language constructs that have specific monads built in (states/worlds, etc...)?

Maybe having a way to generate DSLs (more specific than do-notation) for specific monads could help.

There certainly is a PL angle to this discussion. I don't think "imperative" programmers really want to learn Haskel but they do sense something interesting in monads. Haskell is a FORMAL imperative system. We are familiar with formality in functional languages but not in imperative or stateful ones. Imperative systems can be formalized by using systems theory, but there don't seem to be any languages that do this "formally" with "types" like Haskell.

Interesting. I inadvertently duplicated you, but more verbosely, below. The name "monad" is well chosen -- as in some active entity that has it's own world-line and that is interesting in so far as it "does computing". That's hard to relate to the generally familiar, though.

"Faces or Vases?"
-t

I like this way of looking at it too -- a custom VM and a custom interpreter are similar, differing mostly in the hypothetical implementation details.

'bind' and 'return' are analagous to function application and constants/variables.

'bind' is a way of applying one expression to another, although in reality it passes the result of a computation to another computation, and perhaps does other things like threading state.

'return' simply injects a value into the monad, which is like a constant or variable expression. I'm thinking of lambda expressions as constants. Also, I know in the strict lambda calculus, you don't have a variable reference and an environment -- the variable reference is just replaced by the value it was bound to.

This is what prompted me to think of a monad as a sort of stripped-down lambda calculus interpreter object. It has the two main operations, and by writing 'bind' and 'return', you implement those two operations.

Monads are often related to substitution in computer science uses and this is robust. You do indeed get that return labels a "variable" and bind applies a "substitution" (function) to the "variables" (hence the name "bind".) This comes up again for algebraic uses/free monads.

> A monad is a very abstract kind of "virtual machine".

There are two sides to every metaphor. There are the things that a metaphor is apt for, but there are also the things that it's not. You have to choose your metaphors to get both sides right. Your description fits some kinds of monad very well. But the catch is that it also fits comonads, applicatives, Arrows and probably lots of other type classes too. So what's missing here is any kind of discussion of what aspect is specific to monads. (This complaint is true of many other metaphorical descriptions of monads - it reminds me of the Wason test.)

The combination of both a (potentially trivial) notion of sequencing and higher-order computations. Arrows with application also offer that, but they're equivalent to monads.

"... the catch is that it also fits comonads, applicatives, Arrows and probably lots of other type classes too. So what's missing here is any kind of discussion of what aspect is specific to monads."

For the literal question "What is a monad?", I guess you're right. But my guess is that many of the people who ask that question don't really mean it to be that specific. That is, if there are slight generalizations (Arrows?) or duals (comonads?) of a monad, which can be used for analogous purposes in related situations, they (ok, we) would like to know a bit more about them, too. Which makes the analogy pretty apt, IMHO.

This table does an awesome job of summarising the hierarchy of generalised notions of function application of which monads form just one branch.

Definitely -- monads have very specific, very delibarately chosen semantics. The metaphor I'm using is really a response to people who are new to the concept, or even new to functional programming.

They're getting into pure functional programming, they want to set a variable, they find out that you need monads for this, then they find out that monads are very important, and they get stuck wondering what they are and why there are 'monad laws', and just have no idea what to do with them.

THAT is when the simplifying metaphor is most useful.

When I first started reading about monads, I pretty much understood the concept of state threading and the linearity of the 'world state' and so on; but I didn't know why this bind/return structure was needed. It took me a while to realize that bind/return form a tiny functional language of their one -- one whose implementation you have full control over. I wish that had been mentioned explicitly.

Monadic i/o and UNIX shell programming.

Just remember that this is a picture of one specific monad, not monads in general. (Though, of course, generalisations can be understood by understanding lots of specific examples.)