Monads without pretension (2011)(rcrowley.org)

51 pointsby signa11vor 12 Jahren57 comments

Monads without pretension (2011)

http://rcrowley.org/2011/09/21/monads.html

57 comments

The whole point about monads is that they provide a uniform interface for working with values that carry some extra context. The genericity of the interface is nice, in that it allows you to write generic monad combinators, but they are only useful because of the context (effects, control flow, etc). If you don't describe any of the implementations, you are missing the point!

The best introduction to monads was written in 2006 (more than eight years ago now) and I don't imagine that a better one will be written in the near future -

http://blog.sigfpe.com/2006/08/you-could-have-invented-monad...

chriswarbovor 12 Jahren

It's not even about the effects, really. It's simpler to think of Monad as an interface for manipulating encapsulated data in a way which keeps it encapsulated.

The simplest way to encapsulate data is to wrap it using a constructor which we keep private to our module:

    module M1 (Encap(), val1, val2)
    data Encap a = mkEncap a

    val1 :: Encap Int
    val1 = mkEncap 5

    val2 :: Encap Int
    val2 = mkEncap 10

Other modules importing M1 get access to the Encap type, val1 and val2 but not the mkEncap constructor. They can use val1 and val2 as-is, but they can't construct new Encap values or destruct existing Encap values to get at their contents. The problem is, there's not much we can do with this interface.

One way we can make this more useful is being able to apply some function to an encapsulated value. That's what Functor is for, so we can add this to M1:

    instance Functor Encap where
      fmap f (mkEncap x) = mkEncap (f x)

Now users of M1 can transform encapsulated values without being able to break the encapsulation. For example:

    val1Plus7 :: Encap Int
    val1Plus7 = fmap (+7) val1

    val2Str :: Encap String
    val2Str = fmap show val2

We're still pretty limited though, since there's no way to combine encapsulated values into new encapsulated values, or to encapsulate our own values. That's what Applicative provides, by letting us construct encapsulated values without gaining the ability to destruct them, and by allowing encapsulated functions to be applied to encapsulated values (since functions are closures, this lets us gather up encapsulated values and combine them arbitrarily):

    instance Applicative Encap where
      pure x = mkEncap x
      (mkEncap f) <*> (mkEncap x) = mkEncap (f x)

Now users of M1 can encapsulate and combine values, like this:

    -- val1 + val2
    val1PlusVal2 :: Encap Int
    val1PlusVal2 = fmap (+) val1 <*> val2

    -- New encapsulated string
    val3 :: Encap String
    val3 = pure "Hello world"

    -- val3 repeated val1 times
    val3Repeated :: Encap String
    val3Repeated = fmap rep val1 <*> val3
                   where rep n _ | n <= 0 = ""
                         rep n s          = s ++ rep (n-1) s

This is quite a powerful interface, but one thing we can't do is `collapse` double-encapsulated values into single-encapsulated values. That's what Monad provides:

    join :: Encap (Encap a) -> Encap a
    join (mkEncap (mkEncap x)) = mkEncap x

An alternative, but equivalent, definition is to allow calls to encapsulation-producing functions without encapsulating their result. Haskell's Monad is defined this way:

    instance Monad Encap where
      (>>=) :: Encap a -> (a -> Encap b) -> Encap b
      (mkEncap x) >>= f = f x

These kind of encapsulated values turns out to hold effects without breaking the language, and these interfaces turn out to be powerful enough for general computation.

jberrymanvor 12 Jahren

>These kind of encapsulated values turns out to hold effects without breaking the language

I wonder if you're hand-waving a bit here. To me "encapsulated values" describes Identity or Maybe, but really doesn't work (IMO) for e.g. State or IO where bind is composition.

chriswarbovor 12 Jahren

I would use the term "wrapped-up" where you've used "encapsulated", and in fact I specifically avoided talking about wrappers for this exact reason :)

Maybe my terminology could have been better, but I meant "encapsulated" in analogy to OOP, which advocates "encapsulating" all data via methods. The OOP definition of encapsulation includes using getters/setters, which is like having "wrapped-up" properties, but the idea is that we can go beyond this to calculate the data in arbitrary ways without our clients having to know about the implementation. That's what I was trying to get at here; for example, the implementation of IO involves horrible imperative yukiness, but we (the client) don't need to know that: we just use the interface, and if our functions ever get called, they will be given an appropriate argument.

physPopvor 12 Jahren

This is a wonderful explanation, thank you!

Flowvor 12 Jahren

I agree. I read that comment last night and could almost not sleep due to the insights it gave me. I'm going to spend the whole weekend re-reading about Functors, Applicative and Monads now. Maybe this time I'll grok it all.

Thanks Chris!

agumonkeyvor 12 Jahren

I like to rename encapsulation as invariant these days. List monad will ensure you have a list of a.

Patient0vor 12 Jahren

One thing that this article and lot of other Monad articles gloss over is the scoping in "do" notation and when using the >>= operator.

The example:

    return 7 >>= (\x -> Writer (x+1,"inc."))
             >>= (\x -> Writer (2*x,"double."))
             >>= (\x -> Writer (x-1,"dec."))

works for this example, but a more accurate representation of how "do" notation is expanded is:

    return 7 >>= (\x -> Writer (x+1,"inc.")
             >>= (\x -> Writer (2*x,"double.")
             >>= (\x -> Writer (x-1,"dec."))))

Note that I've moved the parentheses.

Actually, you can, equivalently, omit the parentheses for the same meaning, because the '->' has very low precedence:

    return 7 >>= \x -> Writer (x+1,"inc.")
             >>= \x -> Writer (2*x,"double.")
             >>= \x -> Writer (x-1,"dec.")

The point is, most times each of subsequent functions need to "see" what was in scope in the earlier functions. Most times, the later monadic actions need information that is pulled out of the monad in previous actions.

For example, consider the following:

    main = putStrLn "Enter your first name" >>=
       \_ -> getLine >>=
       \first -> putStrLn "Enter your last name" >>=
       \_ -> getLine >>=
       \last -> putStrLn ("Hello " ++ first ++ " " ++ last ++ ".")

The last monadic action needs both "first" and "last" to both be in scope. This only works because of the way that it is implicitly parenthesized.

Until I "got" this, I was very confused by most of the Monad examples I found.

Here's an article I wrote about the IO monad which also makes this point: https://github.com/Patient0/IOMonad

jerfvor 12 Jahren

I wrote this up, "So You Want To Write A Monad Tutorial in Not-Haskell": http://www.jerf.org/iri/post/2928 It focuses on all the things I've seen people miss about "monads" when they try to write an implementation in another language after the third time I saw someone claim they'd implemented "monads" in Javascript using method chaining, which I do not believe to be possible in part because of the issue you point out, which is that the scope builds up as you go.

It is perfectly reasonable to also read this as the list of elements of monadery that even tutorials written in Haskell tend to miss or fail to explain.

mattfenwickvor 12 Jahren

From your article:

> Monads are not "about effects".

What is your definition of "effects"? I ask because this article[0] and many others[1] seem[2] to use a contradictory definition, in which failure, nondeterminism, state etc. are viewed as effects and monads are a means of implementing those effects.

------

[0]: http://www.sciencedirect.com/science/article/pii/S2352220814...

[1]: http://scholar.google.com/scholar?q=algebraic+effects+monad&...

[2]: as far as I understand them; I may be wrong.

telvor 12 Jahren

"Effect" is a more general idea. It's a lens for viewing any kind of impure computation[0]. Monads are a model for effects. You can view them as pure[1] computation in lambda calculus or as defining a region of code which, internally, has impure effects.

So to summarize: effects are a general concept, monads are a particular technology for implementing that concept.

Further complexity ensues when people start talking about the general concept of a monad which is interesting in its own right but it has a more sophisticated relationship with the concept of effects.

[0] Purity is a property of, say, functions. Its definition is a function `f` is pure if and only if

    const () . f = const ()

which usually means that non-termination is impure as well. The notion of equality you use above can finesse this definition a lot.

[1] As stated in [0], non-termination is an effect, so Haskell monads are impure in that sense. Haskell typically ignores non-termination effects, though. Generally, monads would work more or less just fine even without non-termination though. Externally you can think of them as pure.

jerfvor 12 Jahren

Ironically, I added that just as I was linking it here, despite the date on that post.

In addition to tel's discussion, what I was really trying to get at is that monads aren't "about" IO effects in particular, they're not about "impurity". In this case the whole thing is pure.

Defining effects at a deep programming language research level can bring a different understanding, where all monads are about effects, but "effects" has a different meaning that most people understand.

I'll ponder how to clarify that better.

mattfenwickvor 12 Jahren

My suggestion is to use "side effects" -- it seems to me that most people have an intuitive understanding of that term.

... but I may be wrong about that.

louthyvor 12 Jahren

Your C# IO monad could really benefit from using LINQ (I know you mention it at the end). If you're interested in a full set of C# monads (including a fully implemented IO monad) check my csharp-monad library [0]

[0] https://github.com/louthy/csharp-monad

jfarmervor 12 Jahren

The best introduction to monads that I've read is the original paper that discussed them in the context of functional programming: http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/ba...

ufovor 12 Jahren

On the same vein, SPJ's "Tacking the Awkward Squad" is also a great old paper, and focuses more on impure effects than Wadler's

elwellvor 12 Jahren

If you want video, this is probably worth watching; haven't finished it yet.

https://www.youtube.com/watch?v=ZhuHCtR3xq8

pedrowvor 12 Jahren

For those like me who find it hard to think outside the imperative programming box, Eric Lippert's series of articles is good.

http://ericlippert.com/2013/02/21/monads-part-one/

A lot of Monad articles like to explain 'what' without first establishing 'why' (IMHO)

nightskivor 12 Jahren

Are you sure? There are plenty useful monads which are not effects... In fact the article you linked even says so.

throwaway283719vor 12 Jahren

Yeah, I should have written "computational context" not "effects".

elclanrsvor 12 Jahren

In dynamic languages I don't see the need to create a Monad interface. I'd create classes/objects and simply use instances of those objects. As long as they conform to the desired interface, and you can check their relationships, then it should work; and use monkey-patching if necessary, embracing the dynamic nature of the language. I don't think it is possible to fully translate Haskell examples without the types, but you can adapt the ideas to other languages and get very similar functionality, in JavaScript for example:

    class Maybe {
      constructor(value) {
        if (value != null) {
          return new Just(value)
        }
        return new Nothing()
      }
      bind(f) {
        if (this instanceof Just) {
          return f(this.value)
        }
        return new Nothing()
      }
    }

    class Just extends Maybe {
      constructor(value) {
        this.value = value
      }
      toString() {
        return `<Just ${this.value}>`
      }
    }

    class Nothing extends Maybe {
      constructor() {
        this.value = null
      }
      toString() {
        return '<Nothing>'
      }
    }

    var result = Maybe(2).bind(x => {
      return Maybe(3).bind(y => {
        return Maybe(x + y)
      })
    })

    console.log(result.toString()) // <Just 5>

mjburgessvor 12 Jahren

Monads have so little pretension these days, you'd think they were the salt of the earth. Working classes, for working people.

chriswarbovor 12 Jahren

Monads were pretentious in the '90s. The pretention switched over to Arrows in the '00s and to Algebraic Effects in the '10s ;)

mjburgessvor 12 Jahren

Yeah, Arrows is my "next thing".

jerfvor 12 Jahren

You may not want to bother. Their luster has faded as it has been determined they were a particularly complicated way of representing Applicative + Category: http://just-bottom.blogspot.de/2010/04/programming-with-effe... In theory there's nothing necessarily wrong with them but I think the consensus is that in practice you're better off understanding Applicative (very simple) and Category (also very simple), and then freely combining those however you need to accomplish things, rather than trying to use Arrow (surprisingly complicated).

By contrast, both Applicative and Category as very, very useful.

bkeroackvor 12 Jahren

Total nitpick, but it annoys me when people implement something in Python but use ancient syntax.

  return '<M a: %s>' % self.a

Should be:

  return '<M a: {}>'.format(self.a)

And:

  class M(object):

Should be:

  class M:

etc.

jonhohlevor 12 Jahren

I can see why you might want the second change (discarding superfluous information), but string formatting looks better to me in the first case: it's more terse, and embeds type information in the format string using a well known and understood convention.

Why do you prefer the explicit method call over an operator?

bkeroackvor 12 Jahren

It's arguable, but operator overloading should only be used (if at all) when there is conceptual symmetry between the standard and overloaded usage (eg, adding two datetime objects with '+').

I can't think of any way that taking the modulo of two strings logically results in interpolation. If anything, it should do something like return the original string with all instances of the argument removed. It's just simpler to not support it at all and use the standard .format() method.

There's also the fact that it's deprecated, of course. :)

physPopvor 12 Jahren

% format is deprecated in the python spec.

illiciumvor 12 Jahren

   class M(object):

is a new-style class in Python 2.x, in which it's the correct syntax: https://docs.python.org/2/glossary.html#term-new-style-class

It's different in Python 3 but that doesn't matter because Python 3 is largely irrelevant.

ddellacostavor 12 Jahren

What is the point of implementing monads in Python? I thought the point of monads was that they provide a mechanism for introducing side effects gracefully into a pure language (like, say, Haskell) while still allowing for type safety, per correspondences between category theory and type theory. Python is not strictly typed and makes side effects pretty easy, if I recall from the last time I wrote Python.

Seriously, what is this constant obsession with monads that has infected the programmers?

Why not be obsessed with, say, functors? I can then make statements like, "A functor is a wrapper. Anyone who tells you otherwise is being obtuse" and be just as correct, and sound just as smart.

wanders off grumbling to himself...

freyrs3vor 12 Jahren

> I thought the point of monads was that they provide a mechanism for introducing side effects gracefully into a pure language

That's roughly a description of the IO monad, which is a specific monad. The IO monad is really a degenerate case, and most monads ( List, Cont, Maybe, Writer, State, ... ) have nothing to do with effects.

Half the problem of talking about monads is that in their full generality they're really just a description of a trivial algebraic structure that doesn't really impart much intuition. Monads just get a lot of press because they're one of the simplest examples of a structure that can't be compressed easily in terms of common experience. There's nothing I can point to in our our everyday experience and say "monad" is like this.

zak_mc_krackenvor 12 Jahren

Monads are not just about effects: encoding effects in the type system is just one of the benefits.

Monads are mostly about enabling composition between operations returning different types.

lelfvor 12 Jahren

This article can confuse people even more.

This is what monad is (read: interface with two functions):

  class Monad m where
    (>>=)  :: m a → (a → m b) → m b
    return :: a → m a

Read: function >>= of arguments M[a] and (fun from a to M[b]) that returns M[b]. You can probably write it somehow in MyPy annotations.

(It's actually different in haskell, doesn't matter)

The author however just implemented one instance of Monad: Identity (the most trivial). And called it a Monad. And then semi-checked laws on one value.

ksherlockvor 12 Jahren

Do haskell people realize that using haskell describe monads isn't actually helpful?

orbifoldvor 12 Jahren

Well you could explain them in terms of category theory as an endofunctor T: C -> C, together with two natural transformations eta : 1 -> T and mu : T^2 -> T, that satisfy a number of axioms. The Haskell definition encodes a special case, where the underlying "category" is "Hask", whose objects are Haskell types and morphisms are Haskell terms. Of course this is strictly speaking not a category, but it is close enough.

In mathematics monads usually arise as adjunctions between two functors, for example beginning with a set of elements, you can consider the free monoid generated by it and forget the group structure, this gives you a much larger set. If you did this operation on a set of characters, you would get the set of all strings of those characters, eta would in this case be the operation that given a character in the character set gives you the corresponding string of length one and mu would concatenate two strings.

corysamavor 12 Jahren

Unfortunately, you've taken it two steps in the opposite direction from helpful. The point is that when your audience is neither haskellers nor mathematicians (I.e. the vast majority of programmers on Earth) repeatedly explaining monads in Haskell and/or mathematics is not helpful.

Imagine if you wanted to learn about monads, but every article went "Monads are a simple and powerful idea that, interestingly enough, can be very, very well expressed in Latin. Therefore, I will switch to Latin for the remainder of this article. Oh... You haven't studied Latin? You really should! It's really very useful. Moving on... Cogitus sin extricatus..."

If you want your audience to understand, you need to explain it in C.

orbifoldvor 12 Jahren

Well if the question is 'what is a monad' then the most straight forward explanation is that it is an abstract mathematical concept in category theory and that there are certain laws that have to be satisfied. You can even draw really pretty pictures of those laws http://math.ucr.edu/home/baez/week92.html#tale.

The advantage of mathematics is that it cleanly separates the external view and internal view of a concept. The axioms are easy to state abstractly and they are the most important part, haskell only allows to abstractly define the type of the operations, but can't abstractly enforce the laws. Rather any instance of the typeclass is assumed to satisfy the laws.

Those happen to also hold for certain constructions in functional programming languages, like lists (the list monad) and several others, not by coincidence, but because those languages have a close connection cartesian closed categories.

I firmly believe it is not helpful to explain something by analogy, because an analogy only goes so far. The mathematical notion of a monad is not complicated at all and is only obscured by writing page after page about them in the syntax of some arbitrary programming language.

freyrs3vor 12 Jahren

C is probably the worst language to implement monads in because the type systems really lacks polymorphism, higher order functions and any sort of type-class overloading to clean up the syntax. I mean you could hypothetically pass around a record full of void function pointers to get around all this, but it would be so ugly and unintuitive that it would be silly to try and explain monads this way.

dllthomasvor 12 Jahren

Actually, you can do a bit more than that if you specialize. It'll still be ugly, but it might help people grasp what's going on.

corysamavor 12 Jahren

I think you have the same idea I do. In a statically compiled language, all of the high order polymorphism eventually compiles down to actual, concrete code that should be expressible in hand-specialized C structs and functions performing a single, specific task. Haskell makes that specialization process incredibly convenient and C makes it incredibly inconvenient. But, the point is not to ship a bunch of production code quickly. The point is to provide a low-abstraction example to demonstrate concretely what the compiler is doing for you without prefacing the example with "Assuming of course that you have already studied Haskell..."

freyrs3vor 12 Jahren

You'd end up building a small functional runtime. That's a fun project to understand compilers better. But given that Haskell types are erased at runtime the very thing that makes monads monads wouldn't even be around anymore. All the values would be represented uniformly by some *StgClosure struct and the whole program would just be a mess of casts and projections into these values.

corysamavor 12 Jahren

So, we're talking about Haskell passing around void pointers and later doing cross-your-fingers typecasts on them? That doesn't sound very much like the Haskell I keep hearing about. I was expecting something more like an ungodly stack of C++ templates eventually building up a return type containing a record of all side delayed effects of the function. That C++ template could then be manually flattened to a C struct. It would be a gross amount of manual labor. But, it would also be typesafe in plain C.

dllthomasvor 12 Jahren

There is some broken reasoning here.

There is a translation from any typed language into an untyped language. Writing code in that untyped language is not going to be type safe, while the code generated (correctly) in that untyped language from the typed language is still guaranteed to be correct.

It is entirely possible that the only way to get anything safe out of some Haskell code is to rely on checks the Haskell compiler gives you at compile time, which the C compiler cannot give you.

That said, people often underestimate the kinds of guarantees you can bang out of a C compiler, at the cost of a bit of verbosity.

sampovor 12 Jahren

> So, we're talking about Haskell passing around void pointers and later doing cross-your-fingers typecasts on them?

Following on this thought: Every compiler is essentially an assembler programmer! And we all know how error prone it is to code in assembler. So how can the compiler ever produce error-free binaries?

dllthomasvor 12 Jahren

Types can be erased at runtime. That doesn't mean types have to be erased at runtime. Whatever best suits the pedagogy.

sampovor 12 Jahren

Seriously, man! Anybody who would understand your explanation is the kind of person who already knows what monads are, and thus does not need your explanation in the first place.

ghkbrewvor 12 Jahren

I'll just leave this here: http://stackoverflow.com/questions/3870088/a-monad-is-just-a...

recursivevor 12 Jahren

That's maybe helpful for mathemticians.

telvor 12 Jahren

You need a language which enables generalization. Sadly, most computer languages lack good facilities for this. Human language works, though:

A monad is some parametric type, T, along with two functions called (in Haskell anyway) "return" and "bind". Return "injects" values into the type taking values of type A to values of type T(A). Bind transforms values of type T(A) into values of type T(B) using a function like A -> T(B).

Then these two functions must follow a few rules.

That's a monad. The Haskell fragment above describes the signatures of those functions, notes how they relate to the parametric type, and also produces a facility for overloading `return` and `(>>=)` ("bind") and even working with them when lacking a concrete choice of type `T`.

freyrs3vor 12 Jahren

I try to put myself in the mind of someone who works in a language in which type notions like ( t : * -> * ) and ( a -> t b ) are completely inexpressible I can see how it can be hard to wrap your head around monads. I think a lot of the communication problem about monads is fundamentally a problem that higher types and parametric polymorphism are just not part of the general programmer knowledge and there's no reference point to understand the signatures.

telvor 12 Jahren

Yeah, agreed. I would add to that list general confusion around what "monad" is: is it a noun, an adjective, what kind of noun? Can I touch it, build it, program it? How many are there?

All of those questions change their answer depending, terrifyingly, on how you informally define the word "monad".

dllthomasvor 12 Jahren

Just today I've been playing with an alternate prelude that I think makes all this a bit clearer (at the cost of using basically every GHC extension, ironically).

donsvor 12 Jahren

Psuedocode then.

Given a type `m` and a type `a` a monad provides functions with types:

    bind : m a → (a → m b) → m b
    wrap : a → m a

kazinatorvor 12 Jahren

The following may help some fellow Lisp-heads understand some aspects of monads:

http://www.kylheku.com/cgit/lisp-snippets/tree/monads.lisp

Monads are developed starting with CLOS, then wrapping macros around them for doing monadic comprehensions. Finally, a monad-defining macro is introduced which generates the class and methods from a succinct syntax, and is used to write several monads, including a state transformer monad.

louisdefunesvor 12 Jahren

Is it me or the title is spelled wrongly? Shouldn't it be "pretention"?

bhauervor 12 Jahren

According to Wiktionary, you are using an older form of "pretension."

http://en.wiktionary.org/wiki/pretention