Everything Your Professor Failed to Tell You About Functional Programming

Computer science is the womanizer, and math is the pure-hearted girl he won't call the next day.

I've been trying to learn Haskell lately, and the hardest thing seems to be learning about monads. "Monads in Ruby" and "Monads for Functional Programming" helped me finally to break the ice, but more importantly, they gave me a glimpse behind the veil. I finally began to understand something that is trivial to people such as Philip Wadler, but something that never had been explained to me so succinctly. In computer science, we enjoy using mathematic models, but the science still works if you violate the math. And, much to the dismay of purely functional programming enthusiasts, we almost always do. However, when we embrace the math, sometimes the loss in flexibility is more than compensated for by the increase in functionality.

Monads as a Design Pattern

Somewhere, somebody is going to hate me for saying this, but if I were to try to explain monads to a Java programmer unfamiliar with functional programming, I would say: "Monad is a design pattern that is useful in purely functional languages such as Haskell. Although the concept of a monad has been taken from mathematics, this design pattern can be applied in Haskell to implement a wide range of features."

Philip Wadler says, "Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism."

The Java programmer could argue fairly, "Hey, Java has all those things, and monads aren't even mentioned in Design Patterns. What's the deal?"

I'd respond: "Design patterns fluctuate by language. Just as each language has its own set of native features, it also has its own set of both idioms and design patterns that make sense within that language; naturally, there's a lot of crossover between similar languages. So although I don't expect monads will be the next great thing in Java, they're a necessary part of understanding Haskell." [see Footnote 1]

The Java programmer might continue, "By why would I care about Haskell, especially if I have to learn about this whole monad thing, simply to do the things I already know how to do in Java?"

I'd slyly say:

Have you been paying attention to the The International Conference on Functional Programming Contest over the last several years? It's one of the largest programming contests of the year, and it's often mentioned on Slashdot. Users of any language may enter, and a wide variety of languages are routinely used by the contestants.

During the last several years, the winners of the ICFP Programming Contest were mostly Haskell, OCaml and Dylan programmers, all of which are functional programming languages.

Learning new things occasionally can be painful. Someone once said, "If a programming language doesn't teach you a new way to think about problems, it's not worth learning." I've found that learning about monads and Haskell in general has both been painful and rewarding.

A Trivial Introduction to Monads

Both Wikipedia and "Monads for Functional Programming" offer introductions to monads from a category-theoretic perspective, but they aren't for the faint of heart. Despite having a degree in math, I found that it took a while for me to grasp what was going on. Perhaps I'm rusty, but I think a simpler explanation is possible.

"Monad" is an interface. For any type "<InnerValueType>" (notice the template-ish syntax), a class "MonadExample" that implements the "Monad" interface has the following two methods:

  1. It has a constructor with a parameter named "value" of type "InnerValueType".

  2. It has a method named "pass" that takes a callback. The callback must accept a parameter of type "InnerValueType", also named "value". It must return an instance of "MonadExample". [see Footnote 2] The "pass" method invokes the callback, passes "value" and immediately returns the result.

Whacky interface, eh?

It may help if you start by thinking of monads as a special type of container. Just as "List <Integer>" makes sense, so should "MonadExample <InnerValueType>". Some classes that implement the Monad interface always contain exactly one value. Others might contain zero or more values, as List <Integer> does.

Continuing, let's imagine a simple function "f()" that accepts a value and returns another. Now, instead of simply passing around values, let's wrap the values in monads and pass around the monads. To use the function f() on that value, you must call the monad's "pass" method. Doing so, you suddenly get two benefits. First, you can put a lot of other stuff in the monad besides the value. Second, you can do whatever you want when someone calls the pass method. For example, you can keep track of how many times it was called.

What's even more interesting is you can pass different objects to f(); each implements the Monad interface. Per polymorphism, they can do totally different things, and f() doesn't have to know or care.

In Java, this behavior is not novel--any method may have side effects. But, in a language such as Haskell, side effects are strictly forbidden; functions should take values and return values. Use of the monad, in such a language, enables you to make use of side effects where otherwise impossible.

An Example

Philip Wadler has written several papers detailing how monads can be used to implement a variety of language features in a purely functional programming language, such as Haskell. This article barely scratches at the surface. However, I'd like to offer one example that is somewhat interesting.

The "Maybe" class implements the Monad interface. The Maybe class has two states: it either can contain a real value or it can contain nothing. It's a fairly common cause of bugs in a lot of languages to end up with NULL in a place you weren't expecting it. Sometimes NULL is a valid value in some parts of the code, and sometimes that NULL escapes into code not expecting NULL. The Maybe monad "captures" this behavior in a way that is useful, easy to understand and verifiable at compile time in Haskell. This may be of interest to anyone who's stumbled across such a bug. [see Footnote 3]

At this point, the reader may be begging for some code. One of the hardest things about learning Haskell is you can't understand Haskell without understanding monads, and you can't understand most of the monad examples without understanding Haskell. Hence, here's the Maybe example in Python:


    class Maybe:

        def __init__(self, value=None):
            self.value = value

        def __repr__(self):
            return "Maybe(%s)" % self.value

        def pass_to(self, callback):
            # "pass" is a keyword, so I've used the name "pass_to".
            if self.value is None:
                return Maybe(None)
            return callback(self.value)


    def add(left_monad, right_monad):
        monad_class = left_monad.__class__
        # This strange indentation is perhaps more readable.
        return left_monad.pass_to(lambda left_value: (
               right_monad.pass_to(lambda right_value: (
               monad_class(left_value + right_value)))))


    n1 = Maybe(5)
    n2 = Maybe(6)
    n3 = Maybe(None)

    print n1, "+", n2, "=", add(n1, n2)
    # => Maybe(5) + Maybe(6) = Maybe(11)

    print n2, "+", n3, "=", add(n2, n3)
    # => Maybe(6) + Maybe(None) = Maybe(None)

Here the same example in JavaScript:


    function Maybe(value) {
        this.value = value;
    }

    Maybe.prototype.constructor = Maybe;

    Maybe.prototype.pass = function(maybe, callback) {
        if (maybe.value == null) {
            return new Maybe(null);
        }
        return callback(maybe.value);
    }

    Maybe.prototype.toString = function() { 
        return "Maybe(" + this.value + ")";
    }

    function add(leftMonad, rightMonad) {
        // Pass leftMonad and function taking leftValue.
        return leftMonad.pass(leftMonad,
            function(leftValue) {
                // Pass rightMonad and function taking rightValue.
                return rightMonad.pass(rightMonad, 
                    function(rightValue) {
                        // Return the resulting monad.  leftValue and
                        // rightValue are accessible via a closure.
                        return new leftMonad.constructor(
                            leftValue + rightValue);
                    })
            });
    }

    n1 = new Maybe(5);
    n2 = new Maybe(6);
    n3 = new Maybe(null);

    document.write(n1 + " + " + n2 + " = " + add(n1, n2) + "<br>");
    // => Maybe(5) + Maybe(6) = Maybe(11)

    document.write(n2 + " + " + n3 + " = " + add(n2, n3) + "<br>");
    // => Maybe(6) + Maybe(null) = Maybe(null)

A few things deserve note:

  1. To implement this, your language must support closures.

  2. The "add" function works with any monad. That's part of the beauty of monads. All the knowledge about Maybe was encapsulated in the Maybe class (Python) or prototype (JavaScript).

  3. The successively nested anonymous functions used in the add function are perhaps a bit difficult to understand, but this is a literal translation of how it would work in Haskell. Fortunately, Haskell has syntactic sugar that makes this style programming very easy to read. It's fair to say that the translation into either Python or JavaScript is a bit awkward in comparison.

What's Up with All the Math?

If you read either Wikipedia's or Philip Wadler's introduction to monads for functional programming, you may wonder, "what's up with all the math?" Why is it that computer scientists feel compelled to justify things mathematically before they feel comfortable using them as techniques in computer science? Sure, early computer scientists were mostly mathematicians, but is the connection really so crucial? I can think of three reasons:

  1. Mathematicians are trained to base their work on previous work. Euclid taught us how to create chaos out of definitions, postulates and common notions.

  2. If you base your work on an existing body of work that already has been scrutinized via proof, you reasonably can assume that things probably will turn out better.

  3. If you can prove that your work meets certain criteria, you can let the math do a lot of the work for you. For instance, if you can prove that your code implements a true monad, everything else you know about monads will "just work".

At the risk of stating the obvious, mathematical models aren't perfect. If you add two cups of one substance to two cups of another substance, you might end up with four cups because 2+2=4--or you might end up with an explosion. Obviously, the model must fit the facts, not the other way around. Only then can you use the model to try to ascertain additional facts.

What Happens If You Start Ignoring the Math?

The idea of a function in computer science comes from the Lambda Calculus. What happens if you start ignoring the math? C already fails to comply with Lambda Calculus because of the side effects, but let's take it further. Imagine a version of C called C' that passes all arguments by reference instead of by value and has no return statement. Hence, when you call a function, you can pass a bunch of arguments (note, some of those arguments might contain only junk values). The function itself uses some of those parameters to do something. Then it may, as a side effect, change some of the parameters. Because the arguments are passed by reference, the function is really changing the caller's variables:


    /* Increment x. */
    void inc(int *x)
    {
        (*x)++;
    }

    /* ... */
    int x = 5;
    inc(&x);

We suddenly have a language with no return values and only side effects. Nonetheless, it's easy to see that any program in C easily can be translated into C'. Furthermore, it'd be easy to write a pure Lambda Calculus programming language in C'. C' still would be a useful language if you had nothing else.

Next, let's consider the associative nature of integers:


    (a + b) + c = a + (b + c)

In languages that permit operator overloading, such as C++, Python and Haskell, you can implement the "+" operator for objects. There's nothing in the compiler that forces you to make + associative. Of course, it's usually foolish to implement + in a way that isn't associative, but there's nothing stopping you.

Similarly, in Haskell, you can declare that a type is a member of the type class "monad"--that is, it implements the interface--even if your type doesn't mathematically qualify as a monad. I'm sure that you can expect bad behavior, in some manner or another. But as intelligent as Haskell compilers are, they won't stop you (which is mentioned here).

Why the Universe Won't Come Crashing Down If You Violate the Identity Principle

To belabor the point in the interest of humor, consider the identity principle: a thing must equal itself. My buddy, Leon Atkinson, use to jokingly argue with me that "Nothing makes sense if you violate the identity principle". Well, observe:


    $ python
    >>> class A:
    ...   def __eq__(self, other):
    ...     return False
    ...
    >>> a = A()
    >>> a == a
    False

Notice that the universe didn't cease to exist. I didn't get a core dump or even an exception. I bet if I embedded this naughty class in some dark corner of my Python program, and never made use of it, my program would run.

Now consider that in SQL, "NULL" can best be translated as "nothing"; it's not FALSE, 0 or "". Observe the identity principle in SQL:


    mysql> SELECT FALSE = FALSE;
    +---------------+
    | FALSE = FALSE |
    +---------------+
    |             1 |
    +---------------+
    1 row in set (0.06 sec)

    mysql> SELECT NULL = NULL;
    +-------------+
    | NULL = NULL |
    +-------------+
    |        NULL |
    +-------------+
    1 row in set (0.00 sec)

Notice that NULL does not equal NULL. This leads to my point: In computer science, nothing [still] makes sense [even] if you violate the identity principle.

Why Less Is More

Okay, so what? Should we forsake our math background? Is purely functional programming a lame holdover from a bunch of bitter mathematicians? If it works, it works. Right? No. Sometimes less is more. In math, additional constraints on a set of elements may lead to more theorems that you can prove about that set of elements. Sometimes being more restrictive about what code is allowed to do allows you to make assumptions that lead to optimizations. Sometimes, entire new features can result.

Consider the bad old days of assembly programming. As programs got larger, and as more pieces relied on one another, assembly programmers eventually discovered that you have to be pretty stringent about who gets to modify what. These days, we've learned to be rather controlling about which subroutines are allowed to modify which registers. You can push and pop all you want, but by the time you leave a subroutine, the registers that aren't supposed to be changed better still have their original values intact.

Similarly, as we moved away from structs in C to objects in C++, we started being a lot more strict about who could modify or even know about the internal structure of an object. As soon as you break encapsulation and start poking around the inside of an object in code using that object, your own code becomes tied to the implementation of that object. What seemed like freedom is really slavery.

Now, consider the order of evaluation of C function parameters. Expert C programmers will know where I'm going with this. What does the following program print?


    #include <stdio.h>

    int *inc(int *x)
    {
        printf("%d\n", *x);
        (*x)++;

        return x;
    }

    void printboth(int x, int y)
    {
        printf("x: %d, y: %d\n", x, y);
    }

    int main(int argc, char *argv[])
    {
        int x = 0;

        printboth(*inc(&x) + 10, 
                  *inc(&x) + 100);

        return 0;
    }

The question comes down to which inc(&x) comes first. I believe it's actually part of the ANSI standard, although I could be wrong, that arguments are evaluated right to left:


    $ ./test
    0
    1
    x: 12, y: 101

Notice that y ends in 1, whereas x ends in 2. Indeed, the y argument was evaluated first. Can you guess what would get printed if you translated this code into Java? [see Footnote 4]

It makes me wonder, if a function's side effects can't influence anything beyond the monad in a purely functional programming language such as Haskell, and if the programmer is completely in control of the monad, does that make the program easier to understand? If you don't have to worry about the side effects of some random function that you didn't even write, do you get fewer bugs?

As a further point, consider what "Joel on Software" reminds us of when explaining MapReduce, the algorithm that makes Google so massively scalable [see Footnote 5]: if a list of functions [isn't] allowed to have any side effects, you can safely call them all in parallel. Considering how hard it is to make something thread safe, suddenly parallel programming in a functional programming language such as Haskell, Erlang or Alice seems a lot nicer!

Summary

Purely functional programming languages such as Haskell are very strict in their approach to side effects. Monads can be used to compensate for this strictness in order to implement a lot of the features we have come to take for granted in non-strict languages. They can do this without compromising the strictness of the language as a whole. Although staying true to an underlying mathematical model isn't fundamental to the continued existence of the universe, sometimes doing so can have substantial benefits. Sometimes the ideas that are hard to understand and that seem overly restrictive can open up whole new worlds in the universe of computer science.

Acknowledgments

I'd like to thank Brandon L. Golm and Brennan Evans for their substantial feedback on this article.

Footnotes

Footnote 1: I've occasionally heard Lisp programmers such as Paul Graham bash the concept of design patterns. To such readers I'd like to suggest that the concept of designing a domain-specific language to solve a problem and then solving that problem in that domain-specific language is itself a design pattern that makes a lot of sense in languages such as Lisp. Just because design patterns that make sense in Java don't often make sense in Lisp doesn't detract from the utility of giving certain patterns names and documenting them for the benefit of all the less experienced programmers.

Footnote 2: Strictly speaking, "pass" may return a value of "MonadExample" that wraps a value of "SomeOtherInnerValueType". This added bit of flexibility is difficult to describe without bewildering the reader.

Footnote 3: Cyclone is an interesting variant of C that has special syntax for this concept of "a pointer that might be NULL vs. a pointer that can never be NULL". It too could catch this class of errors at compile time.

Footnote 4: It prints x: 11, y: 102. If you attempt this exercise, remember that instead of using a pointer to an int, you should use an object that wraps an int.

Footnote 5: The same idea is also central to Erlang, a functional programming language used by Ericsson.

Shannon Behrens is a self-professed language lawyer who works for IronPort Systems in San Bruno, California. His eventual goal is to implement a Python-like systems language and then develop a practice kernel in that language.

______________________

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Null

Anonymous's picture

The null comparison has some analogies to the liar paradox, because if we negate null it is still null. If I know the knowledge of flight is unknown to me, but I also negate that the knowledge of flight is unknown to me, then I better leave the windows alone.

Re: footnote 1

Johnny Gout Cure's picture

"... bash the concept of design patterns... domain-specific language to solve a problem ... is itself a design pattern... design patterns that make sense in Java don't often make sense in Lisp doesn't detract from the utility of giving certain patterns names..."

I absolutely *agree* with the characterization above. However the BIG PROBLEM is that these so-called patterns are being touted as _universal_ ones, e.g. they apply no matter which language you use, which as you also say above is most definitely untrue.

I do find myself using pattern names nowadays much as I feel the idea was rather bogus from the beginning. The problem is that "patterns" are being presented as a silver bullet/panacea when they are actually nothing more than an occasional mere _convenience_ to facilitate communication.

The urge to hype is partly due to the fact that it wouldn't have taken off without overselling it, but even if I do find pattern vocabulary *occasionally* useful, I find that hype most disingenuous.

Identity

Robert F's picture

I don't get your notion that using an equals sign to represent an irreflexive relation is 'breaking the identity principle'. Redefining the meaning of the equals sign does not change the meaning of equality, of being the same thing. Null is still equal to null, even if the relation you're using for = doesn't say so.

You seem to have circumscribed mathematics rather narrowly. Do you consider mathematics done with paraconsistent logic not to be mathematics, for instance?

More Monads - Am I getting it?

Joshua Volz's picture

Okay, so a monad is a design pattern that can be used to encapsulate some functionality that will generally work on any type (otherwise generalizing the functionality wouldn't be helpful, since you would have to still deal with all the different types).

Am I the only one who thinks of blocks and yield in Ruby when they hear that? The block is the part of the functionality that you are encapsulating in the monad (potentially w/ side effects) and the function that takes the monad calls "pass" (or yield) to get that functionality executed on the values passed to it. Assuming you could encapsulate the block (say in a proc object) and its state (think closure) then you could reuse that block just like how you could reuse a monad.

I have only been reading about Haskell and monads for about two hours though, so I might be completely missing the point here. Can somebody straighten me out if I am off base please?

Awesome article

Charles Stevenson's picture

I really enjoyed reading this. I've been struggling through Haskell 98 Report, A Gentle Introduction to Haskell (Yeah right ;) and Yet Another Haskell Tutorial for a few months now. It was nice to see the examples in Python and JavaScript. Keep up the good work.

peace,
core

other Haskell tutorials

Shannon -jj Behrens's picture

about C and ANSI

leo's picture

It seems a matter of CPU arch...
on i386, you get:
$ ./a.out
0
1
x: 12, y: 101
---
on powerpc:
0
1
x: 11, y: 102
---
both are gcc 4.0.3

sequence points.. arg evaluation order unspecified in C99

Jose's picture

I am not completely sure now, but look at Appendix C of the Ansi std. Read through the list, and read item #10 of section 6.5.2.2, which states "The order of evaluation of the function designator, the actual arguments, and subexpressions within the actual arguments is unspecified, but there is a sequence point before the actual call." A function call like f(x,y) must have x and y evaluated fully before f is called but x and y can be evaluated in any order. [Note that the comma between x and y is not the comma operator as defined by the standard but is just syntax inside the paren of function call. Also, note that f can be evaluated before or after x and y but it isn't *called* until all of f (obviously), x, and y have been evaluated fully. Ex, (p+x)(x++,x--) is basically illegal becuase even without looking at how the params are used inside the function, the actual function that is to be called can be any of 3 possible values depending on when p+x is evaluated in relation to x++ and x-- (first or last; after x++ but before x--; or after x-- but before x++).]

Thus it is unspecified which *inc(&x) is computed first. For the program to follow the standard strictly, basically you are supposed to get the same results either way (not the case in the current example) or else condition the statement with #if #else (perhaps to execute one way or the other depending on the compiler used).

The natural disclamers apply (IANAExpert, etc)

Evaluation order

Wim L's picture

Yep. The function arguments will usually be evaluated right-to-left on a register-starved architecture like x86 which pushes the parameters on the stack in that order ... but the compiler is free to evaluate them in another order (or simultaneously, in interleaved instruction streams) if it feels like it. On a ppc (and several other architectures), the first few parameters are passed in registers, so there's no evaluation order that's more natural than another.

Your increments example is, AFAIK, perfectly legal C, but the standard says that any of the three behaviors is valid and you can't count on any particular one happening. So, it's legal, but not all that useful.

(Disclaimer: I am not a language lawyer.)

Re: Why the Universe Won't Come Crashing Down If You Violate the

Leon Atkinson's picture

It is not the universe that will come crashing down, but your own ability to perceive the universe. The universe, of course, will continue to exist and behave according to its rules.

On a different topic, I might ask you, "why have you slighted PHP by not including an example?" I might quickly follow that question with, "How would I implement a monad in PHP 5?"

To that, you would probably say, "I have left this as an excercise for the (perverse) reader."

I would then be forced to exclaim, "Touche! The student becomes the teacher!" and then regret using a silly French word, possibly mispelling it and definitely mispronouncing it.

Teasing aside, I do hope you continue to write articles like this for LinuxJournal. As with all your work, they are top quality.

Monads in PHP

Shannon -jj Behrens's picture

> On a different topic, I might ask you, "why have you slighted PHP by not including an example?"

I could claim that it's because PHP doesn't have closures that I know of, but the real reason is because a pack of wild Haskell programmers would probably hunt me down and chain me in a room with nothing more than a Cobol compiler ;)

> Teasing aside, I do hope you continue to write articles like this for LinuxJournal. As with all your work, they are top quality.

Thanks for the encouragement!

Hey! What's with the slams on COBOL?

Ren's picture

The earliest databases were interfaces for COBOL - IDMS and CICS for instance.

And *those* were certainly more capable than that toy MySQL.

Vive l' Postgres!!

so a monad is a design pattern

Anonymous's picture

got it

Monads

Marpag's picture

It may be time to drop the word "monad" from Computer Science. Since it first started to appear a few years back, it has appeared in numerous places and usually without a definition, so that many are now running hither and whither trying to come up with a definition for these beasties. One hears, for example, that Microsoft's new Longhorn OS with be based on monads. A simple web search will quickly produce references to things like HTML monads, XML monads, C# monads, with little explanation of what they might be in each case.

Trying to guess what circuits exist in a black box from input and output patterns can produce many different results. It is usually better to be provided with a schematic to understand what is happening. So, it is desireable that the guy who first coined this "monad" thing would come out and tell us what he meant. Then, once we have a definition, it would be quite easy to see why a particular piece of code is a monad or not. But, giving examples claiming that "this is a monad" and "this is one too" only leads to conjectures about what was meant and to uncomfortable moments where one may at first think that one understands which is quickly followed by a next moment when one thinks that perhaps one does not.

Does anyone out there have a definitive definition of monad? If not, I would suggest that the term be dropped. It is notable that "design pattern" is now another beastie that has been effectively dropped because it is used in so many different ways that no one can be sure anymore about what it might be.

Monad reply

Robert F's picture

A monad is simply a monoid object in the category of endofunctors. See Saunders Mac Lane's Category Theory for the Working Mathematician.

The reason it seems to you that monad might not have a precise definition is that:

1. It doesn't map very clearly to languages that don't have type systems based on System F or other typed lambda calculi (e.g. ML or Haskell), as it then becomes difficult to define the concept of functor and natural transformation in these languages.

2. To define monad properly, you should use the following concepts:
Monoid
Category (and object and morphism)
Functor
Functor composition
Natural transformation
both ways of composing natural transformations

Perhaps initial objects and products too.

It might also be useful to define the Kleisli category, as that's where monads find their use in Haskell (they tend to be used to define 'functions with extra stuff signified by the type of their return type') and is where Haskell's >>= operator comes from.

Fortunately, it is not necessary to understand all that to actually use monads, any more than it is necessary to understand relational calculus to use SQL or to understand boolean rings to use OR and AND.

Incidentally, the Longhorn thing was not to do with the category theoretic monads. I think the original version of PowerShell was named monad after the use of the term in Leibniz's philosophy.

Monads are originally from

mgsloan's picture

Monads are originally from category theory (the same term is used in predicative logic to indicate the unary operators, which is only ~).

More recently (say, 10-15 years) it has been adopted in functional languages as a method of expressing containment and processing on the contained items. This has definite links to the category theory meaning. The monads of the functional language haskell allow elegant IO within a perfectly pure language.

C#'s 'monads' are basically a limited adoption of haskell's - apparently this connection is not ephemeral - the implementors know haskell.

I'm unsure about HTML/XML Monads. I have a feeling you are confused on that matter.

Monads

Shannon -jj Behrens's picture

The definition is actually quite concrete both in math and CS. For *precise* details, please see:

http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/marktoberdorf.pdf

I'm not sure how monads would work in, say HTML, since HTML is a markup language and doesn't have functions. :-/

Definitive definition of monad

Andrej Bauer's picture

The word monad came to computer science from mathematics, more precisely from category theory (this was done by Eugenio Moggi). In category theory, monad is a structure with a standard and well known definition.

I do not know how people misuse the word in computer science, but given its historical origin, it should only be used in connection with those aspects of computer science which are mathematically modeled by (mathematical) monads. You do not really have the freedom to "redefine" monads here.

Neither is it true that monads in computer science have no definition. In good computer science they have a precise definition, such as e.g. in Haskell, and this definition is based on the mathematical one. Just because a bunch of ignorant people use the word as a buzzword is not a reason to drop the word from all of computer science. It is the ignorant people who should be dropped.

Avoiding lambdas in python code

Matteo Dell&#039;Amico's picture

Nice article. However, I had quite a hard time decoding lambdas in the Python example, and I rewrote them as named functions. Usually, it is a bad idea to use lambdas in python, since named function can always do just the same thing.


class Maybe:
def __init__(self, value=None):
self.value = value
def __repr__(self):
return "Maybe(%s)" % self.value
def pass_to(self, callback):
# "pass" is a keyword, so I've used the name "pass_to".
if self.value is None:
return Maybe(None)
return callback(self.value)
def add(left_monad, right_monad):
monad_class = left_monad.__class__
def left_pass(left_value):
def right_pass(right_value):
return monad_class(left_value + right_value)
return right_monad.pass_to(right_pass)
return left_monad.pass_to(left_pass)
n1 = Maybe(5)
n2 = Maybe(6)
n3 = Maybe(None)
print n1, "+", n2, "=", add(n1, n2)
# => Maybe(5) + Maybe(6) = Maybe(11)
print n2, "+", n3, "=", add(n2, n3)
# => Maybe(6) + Maybe(None) = Maybe(None)

PS: looks like it is impossible to get formatting correct... you can download this at my homepage.

Avoid lambdas?

Arnar's picture

I feel a bit silly replying to a year and a half old thread, but:

"Usually, it is a bad idea to use lambdas in python, since named function can always do just the same thing."

That's like saying we shouldn't use multiplication because it can just as well be done with a loop and addition.

I don't get why people are so afraid of such simple concepts. And Shannon, I quite frankly don't get the point either of your section "What's with all the math then?".

I'm not trolling, but imo the notion of wanting to drop or avoid things because they are hard is not they correct mindset to make progress for future generations to enjoy.

lambdas versus named functions

Shannon -jj Behrens's picture

I know where you're coming from. In fact, I wrote the same code as you, but I really disliked the way the code flowed:

def1
def2
def3
call3
call2
call1

I was worried readers would find this more unreadable than:

lambda1
lambda2
lambda3

I think it's fair to say that both ways are awkward. I think in the longterm, readers could learn to visually parse the lambda version more accurately since the code isn't "split". Like I said, I'm glad Haskell has special syntax for this.

Design patterns only for those with little experience?

Quintesse's picture

Nice article but I agree with Joshua that I miss a good explanation of the "why" of all this.

I do take exception with your comment in footnote 1 where you suggest that Design Patterns are only for those programmers with little experience. I also think that the Gang of Four wouldn't agree with you. It is a bit like saying that medics who learn latin do so only to be able to explain things betters to beginning doctors. I think a large part of the value of Design Patterns is the fact that we now have a common idiom for talking about things that experienced programmers knew and used all along. (But surely many of us "experienced" programmers still learned a lot from those Design Patterns ;-)

Design patterns only for those with little experience?

Shannon -jj Behrens's picture

> Nice article but I agree with Joshua that I miss a good explanation of the "why" of all this.

Hmm, I thought I went to great lengths to explain that in my "Monads as a Design Pattern" section. Specifically:

You need monads to understand Haskell.
You need Haskell because it's a functional programming language.
You need functional programming languages because they're kicking butt right now in the programming contests.

> I do take exception with your comment in footnote 1 where you suggest that Design Patterns are only for those programmers with little experience.

I apologize, but you have misread my statement. (More below.)

> I also think that the Gang of Four wouldn't agree with you. It is a bit like saying that medics who learn latin do so only to be able to explain things betters to beginning doctors. I think a large part of the value of Design Patterns is the fact that we now have a common idiom for talking about things that experienced programmers knew and used all along. (But surely many of us "experienced" programmers still learned a lot from those Design Patterns ;-)

Absolutely. We're in 100% agreement.

argument evaluation

Anonymous's picture

The article says:

"The question comes down to which inc(&x) comes first. I believe it's actually part of the ANSI standard, although I could be wrong, that arguments are evaluated right to left ...
Notice that y ends in 1, whereas x ends in 2. Indeed, the y argument was evaluated first. Can you guess what would get printed if you translated this code into Java?"

That is not correct at all. The order of evaluation for arguments is undefined so a conforming program can not rely on it. In addition, multiple side effects on the same variable wihout a sequence point in between are not only unordered, but undefined. I believe that applies here, even though the change is inside of another function. So a conforming compiler could do something completely unexpected like deleting all your files. :)

Err... maybe that was your point. I didn't quite understand the point about experienced C programmers. If so, nevermind.

argument evaluation

Shannon -jj Behrens's picture

> Err... maybe that was your point.

giggle. Yep ;)

> I didn't quite understand the point about experienced C programmers. If so, nevermind.

I stole this joke from "Expert C Programming: Deep C Secrets".

I have stared at your Maybe

Joshua Rodman's picture

I have stared at your Maybe python class for some time, squinting and peering.

I do not understand why the implementation is so verbose, for starters. left_monad? how about x. Secondly, the formatting is really terrible. Even in native haskell there's no reason to dodge a few bind expressions to break out the concepts.

Also, you don't ever explain the why of any of this. The behavior could be easily achieved by simply testing for none in the add function. Why create a new Maybe(None) istead of just returning self.value?

What does any of this achieve?

It's also interesting that you note that erlang is a very workable language for thread-safe programming. Erlang eschews the whole mental masturbation exercise of Monads and has all kinds of side effects up the wazoo with the very core idiom of message passing, but gains all the practical benefits of FP.

I have stared at your Maybe

Shannon -jj Behrens's picture

> I have stared at your Maybe python class for some time, squinting and peering.

Thanks for reading ;)

> I do not understand why the implementation is so verbose, for starters. left_monad? how about x.

I was going overboard in the hope of making it more readable.

> Secondly, the formatting is really terrible.

The indentation was my own. The lack of blank lines was done by "Linux Journal". For that, I apologize.

> Even in native haskell there's no reason to dodge a few bind expressions to break out the concepts.

> Also, you don't ever explain the why of any of this.

Hmm, I thought I went to great lengths to explain that in my "Monads as a Design Pattern" section. Specifically:

You need monads to understand Haskell.
You need Haskell because it's been kicking butt lately in the programming contests.

> The behavior could be easily achieved by simply testing for none in the add function. Why create a new Maybe(None) istead of just returning self.value?

> What does any of this achieve?

The idea is that the add function can be used with *any* monad. Other monads might work completely differently. The Maybe monad is very simple.

> It's also interesting that you note that erlang is a very workable language for thread-safe programming. Erlang eschews the whole mental masturbation exercise of Monads and has all kinds of side effects up the wazoo with the very core idiom of message passing, but gains all the practical benefits of FP.

Fair enough. I admit that I have not learned every functional programming language. Thanks for the paragraph above, I find it interesting. Haskell has my fancy right now, because I'm debating internally the question of function vs. purely functional. Obviously, I don't have all the answers.

Do you really need Haskell?

Andreas Bogk's picture

> You need Haskell because it's been kicking butt lately in the programming contests.

Hm. We, the Dylan Hackers team, came in second, but mainly because we made mistakes in choosing the meta-game strategy for the second round. We kicked Haskells butt in round one. And we won the prize for the most readable and refactorizable code, which is not a light aspect in maintaining real-life systems.

For my life, I cannot wrap my head around monads, or read the type errors you get out of Haskell or ML compilers. Monads may be nice as a mathematical tool, but they're unwieldy as a programming abstraction.

Oh, and speaking of a Python-like system langage: we already have that, and it's called Dylan. We share your dream of using that to write a new system from scratch.

Dylan, eh?

Shannon -jj Behrens's picture

Andreas, yes, I have been keeping my eye on Dylan ;) You said, "Oh, and speaking of a Python-like system langage: we already have that." Does that mean there's a compiler for Dylan? I thought there was only an interpreter. I shouldn't be surprised, since there are compilers for other derivatives of Lisp. I wonder if it has Scheme-style macros :-/

Ok, I will consider myself "encouraged" to learn Dylan ;)

Yep, Dylan

Andreas Bogk's picture

There's not only one, but two Dylan compilers in existence. One is Gwydion Dylan, which was written by the people at CMU who were also responsible for CMU CL. Project lead was Scott Fahlman, known as the inventor of the smiley.

The other compiler, now known as Open Dylan, was written at the now-defunct company Harlequin. A lot of the people who worked on the Lisp machine in better times long gone ended up at Harlequin, and worked on the LispWorks compiler there. These were also the people who worked on the Dylan compiler. Harlequin eventually went bankrupt, and was split apart. The Dylan compiler ended up in the hands of the authors, because commercial interest had faded, and they eventually decided to release everything under an open source license. This code is impressive, the garbage collector alone represens 30 person years of work by experts in the field.

Dylan was designed to bridge the gap between the power of dynamic languages and the speed of static languages. It uses a type annotation system, much like CL does, and the compiler does what is called "optimistic type inferencing" to optimize away type checks and generic function dispatch. It is possible to get within the same order of magnitude in speed as if the program had been written in C, in a lot of cases even matching the speed.

Regarding macros: Dylan does have proper hygienic macros. It's missing procedural macros, but there's a proposal for an extension available, and Open Dylan (ex Functional Developer, ex ex Harlequin Dylan) even used procedural macros internally.

Thanks for you interest in Dylan. If you have any questions, feel free to drop by on #dylan on irc.freenode.net.

Dylan Hackers

Charles Stevenson's picture

Hey... I watched your talk at CCC and read some of the IFPC site a few months ago but I haven't looked at Dylan yet since I was still trying to grok Haskell. Perhaps I should just stop wasting time and move straight to Dylan. Might stop by IRC sometime soon...

peace,
core

Nice article.

shapr's picture

For people wishing to see an implementation of the monad abstraction in their own language, A collection of links to monad implementations in various languages is handy. It includes links to versions in C++, Clean, Haskell, Java, Joy, Miranda, OCaml, Perl, Prolog, Python, Ruby, Scala, Scheme, Tcl, XSLT, and maybe more at this point.

Nice article, a few issues

Cale Gibbard's picture

Nice article, good to see people trying to get these ideas out to the masses.

There are some issues with it that I'd like to mention.

The term "monad" is misused a couple of times, especially in the
examples in your article. The only thing which is a monad is the type
constructor -- the function on types, never the elements of any given
type. So Maybe is a monad, but (Just 5) isn't.

Another slightly odd thing which you might try to fix with your Python
implementation of Maybe is that Nothing is properly part of the Maybe
type, that is, it's a value of type (Maybe a) which isn't just return
applied to some value. Here, you're using the constructor for the
class as return, but you also get the equivalent of Nothing by
applying the constructor to the value None, which is a little odd.

I'd also have some reservations with the comment that you need to
understand monads to understand Haskell and vice versa. That's sort of
true, but it really shouldn't be a difficulty, because you pass back
and forth between them in learning. You don't need very much Haskell
to understand some simple examples of monads in Haskell (Lists are
probably the best example), and you don't need to know all that much
about monads to understand most Haskell code.

By the way, did you read my article?
http://www.haskell.org/hawiki/MonadsAsContainers

It takes a rather different perspective on monads than a lot of the
tutorials do, and it's one that I've found people new to monads have
an easier time with.

The point about monads being a design pattern I actually wouldn't take
too much exception to, except for the fact that I don't really like
the term "design pattern" in the first place. :) Too often, the things
people call design patterns are just ordinary functions or general
interfaces in a more expressive programming language.

In Haskell, you have the Monad class which unifies the use of monads
throughout the language, so that you don't end up with the same
structures of bind and return and liftM and join over and over on
different types. (Which is the point at which I'd think it more
reasonable to call it a design pattern.) It started out in programming
use as a design pattern, and now it's just a typeclass whose members
satisfy some laws.

I suppose one could say that the general use of the Monad class is a
design pattern, but I'd argue that it's no more a design pattern than
the use of the Num class (which is what Haskell uses to unify operations on numeric types). :)

- Cale

Nice article, a few issues

Shannon -jj Behrens's picture

Thank you very much for your corrections as well as your helpful comment in general.

Part of the reason that

Anonymous's picture

Part of the reason that nothing really bad happens if you have side effects in your program is that you can actually represent side effects in the lambda calculus without too much difficulty: each function takes and returns an extra argument, which is the state of the system. Things passed by reference are actually instructions for interacting with the state, not values. Of course, this is essentially the monad concept. You can look at a language like C (or C') as having everything in one huge monad, which the compiler handles for you, and the math works out just like using small explicit monads in Haskell. Of course, your language features aren't operating directly on the lambda calculus elements that they look like (i.e., "x" isn't a variable with an integer value in the lambda-calculus sense, it's a variable with an address value, and the state at the address holds the integer). The "everything is constant" functional aspects come through in that you can't write "&x = &y;" or "5++" in C.

The difference between C and Haskell

LyleK's picture

The difference between C and Haskell, regarding monad behavior, is that in C, every function is in the IO monad, whereas in Haskell, only some functions are, and there are other monads besides IO.

Part of the reason that

Shannon -jj Behrens's picture

Brilliant point.

Many thanks

Anonymous's picture

It warms the cockles of my heart to see somebody in industry talking about such subjects!

Monads in Ruby

Shannon -jj Behrens's picture

MenTaLguY said:

Having thought about it a little bit, the definition of "pass" in
the article is a bit weird -- some monads can hold more than one
value at a time, for instance, so skipping the fact that "pass" is
sort of a "fanout-then-recombine" operation is kind of an
unfortunate omission.

On the plus side, one really important thing you picked up on is
that the data type the monad is built on needs to be a type
constructor -- i.e. a generic data type. That's something I've
been angsting about in my Monads-in-Ruby article, as I've had to
rather deliberately gloss over some of the important type issues
involved because of Ruby's laissez faire approach to typing.

I reply:

I agree. Sorry for the omission. The List Monad in Ruby tries the function with every item in the list. Its approach to computation is "try everything", and that approach is encapsulated in the Monad, right?

Maybe Monad

Anonymous's picture

I've never bothered to try understanding monads, but this is not the first time I read about them. Not the first time I see a Maybe monad too. Could you give another example why a Maybe class might be useful (or say how the one you have is useful)? Maybe(6) + Maybe(None) = Maybe(None) has no obvious explanations. f(any,None) = None would seem pretty easy to define in any language.

This reply might be a bit

Anonymous's picture

This reply might be a bit less erudite than the sibling, but I thought it might be useful to write something a bit more to-the-point. A lot of imperative programs I've seen use a pattern where a routine returns a sentinel value (usually False) for failure. So you get code like this:

def do_something():
(success, val) = do_somethingelse()
if not success:
return False

(success, val2) = do_another()
if not success:
return False

(success, val3) = do_more(val, val2)
if not success:
return False
...

return final

Exceptions are a way out of this, but that is not ideal when it's not actually an error for the various routines to fail. In Haskell, you can have all the routines return a Maybe type and do:

do_something = do val1 <- do_somethingelse
val2 <- do_another
val3 <- do_more val1 val2
...
return final

The Maybe monad will automatically collapse the whole computation to Nothing if one of the sub-processes returns Nothing; otherwise, the return value will be (Just final).

I apologize for the indentation; I can't seem to get proper pre-formatted text from this comment entry box.

Avoidance of redundancy, separation of concerns, and factoring

Anonymous's picture

Maybe(6) + Maybe(None) = Maybe(None) has no obvious explanations. f(any,None) = None would seem pretty easy to define in any language.

Yes. And g(any, None), and h(any, None), and foo(any, None), and bar(any, None), and frobnicate(any, None), and redundantize(any, None), and all the rest, are just as easy, of course. And if you ever need versions that don't have the None-handling logic, you can write even more versions of these functions!

The trick that the Maybe monad is doing is to encapsulate the logic that you'd have to implement over and over in those functions in just one place. You write them without having to worry about whether somebody might call them with None as an argument (and in Haskell, in fact, that means that unless the functions explicitly accept aguments of type Maybe, you can never call them with None, guaranteed at compile time). Then, if you need to use them in the context of a computation that only optionally returns a value, you build that computation using the the Maybe monad. Or if you actually change your mind, and want the computation to fail with an error as early as possible, you just replace the Maybe monad with the Error monad. Or if you want it to be nondeterministic, you can use the List monad. And so on...

Avoidance of redundancy, separation of concerns, and factoring

Shannon -jj Behrens's picture

Brilliant comment. Wow, I wish I could have said it that nicely ;) I tried, but I fear it didn't come through.

Webinar
One Click, Universal Protection: Implementing Centralized Security Policies on Linux Systems

As Linux continues to play an ever increasing role in corporate data centers and institutions, ensuring the integrity and protection of these systems must be a priority. With 60% of the world's websites and an increasing share of organization's mission-critical workloads running on Linux, failing to stop malware and other advanced threats on Linux can increasingly impact an organization's reputation and bottom line.

Learn More

Sponsored by Bit9

Webinar
Linux Backup and Recovery Webinar

Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.

In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.

Learn More

Sponsored by Storix