Shapely Monads

“A new way to think about monads.”

0. Index

  1. Greg Meredith on Monads
  2. Definition
  3. Syntax
  4. The List Shape
       3.0. Shape
       3.1. Wrap
       3.3. Roll
  5. Equations
  6. Shapes & Monads
       5.1. The Identity Monad
       5.2. The  Maybe Monad
       5.3. The List Monad
       5.4. The Set Monad
  7. Lessons

1. Greg Meredith on Monads

I’ve found a wonderful metaphor for the elusive concept of monads. This metaphor was created by Greg Meredith, mathematician, computer scientist and monad expert.

See his presentation:

I’ll try to sumarize my own understanding of the main points of Greg’s presentation below; for myself and for anyone else interested. Please correct me if you think I’ve misunderstood something.

Note. This blog post will evolve. I periodically update it.

2. Definition

The metaphor consists of three parts:

  • Shape
  • wrap
  • roll

Monads with structure also have this part:

  • compose

3. Syntax

The syntax chosen is important to how easy to understand something is. Greg has found that using markup syntax (angle bracket syntax, e.g. <list>1,2,3</list>) is a useful way to think about the shape of monad instances; therefore Shapely Monads.

I’m going to augment this by translating it into domain-specific syntax for lists as well, to make structure even more easy to see.

In the following examples I’ll use 4 syntaxes:

  • function call syntax, e.g. wrap(3); how one would write in a program; qualified (e.g. List.wrap, or Set.wrap) and unqualified (e.g. wrap; this assuming some shape in the context of its use.)
  • abbreviated function call syntax, e.g. w(3) is the same as wrap(3)
  • shape-specific syntax, e.g. [a,b,c,…] for lists, simply because it’s easy to understand; other examples: {a,b,c,…} for sets.
  • markup syntax, e.g. <list>a,b,c,…</list> for lists (same as [a,b,c,…]) whereas <set>a,b,c,…</set> is for sets (same as {a,b,c,…}), etc.

I’ll be careful to make the syntax obvious.

4. The List Shape

To start with some concrete examples, let’s use the monad of lists, the list monad.

4.0. Shape

The list shape is something which we can symbolize as:

  • [] is the empty list; <list></list>
  • [a] is the singleton list; <list>a</list>
  • [a,b,c] is a list of three elements; <list>a,b,c</list>
  • and so on

The sequare bracket syntax is just domain-specific syntax for lists. We use it here to make it easy to see the structure of values.

4.1. Wrap

First let’s create a list of one element, the number zero:

  • List.wrap(0) = <list>0</list> = [0]

So we’ve now put the value 0 into the list monad.

List elements can be other lists, so for example:

  • [[a],[b,c]] is a list of a list of a, followed by a list of b and c

The operator expression to construct this sequence is

List.wrap(List.wrap(a),List.wrap(List.wrap(b)+List.wrap(c)))
=
List.wrap(<list>a</list>,<list>b,c</list>)
=
<list>
   <list>a</list>
    <list>b,c</list>
</list>
=
[[a],[b,c]]

4.2. Compose

To compose lists (append lists to eachother), we can write

  • List.compose(List.wrap(0),List.wrap(1)) = <list>0,1</list> = [0,1]

this will create the singleton list of the number zero composed with the singleton list of the number one, creating a new list of two elements, zero and one.

So far we’ve leared that:

  • List is a Shape; we use color here to help recognize lists
  • List.wrap(x) constructs a new list of one element, i.e. [x]
  • List.compose is the append operation; it takes two lists and creates a new list which is the two lists in sucession

Note also that the neutral instance of the list monad is [], i.e. <list></list> or what we might express as List.wrap(); composing an empty list with any other list yields the same list; it has no effect; we can see this as

  • <list>x</list> + <list></list> = <list>x</list>

    XML has special support for empty elements, which we can take advantage of

    <list>x</list> + <list/> = <list>x</list>

    or, equivalently, using the short-hand syntax for lists

    [x] + [] = [x]

Now, in the following, for syntactic brevity we’ll assume the List monad and not qualify the operations with the specific shape type (List, Set, Graph, etc.)

4.3. Roll

Suppose we create one more level of nesting:

  • wrap(compose(wrap(0),wrap(1))
    =
    wrap(<list>0,1</list>)
    =
    <list>
    <list>0,1</list>
    </list>
    =
    [[0,1]]

Then we can use roll on that to remove the superfluous nesting again:

  • roll(wrap(compose(wrap(0),wrap(1)))
    =
    roll(wrap(<list>0,1</list>))
    =
    roll(<list><list>0,1</list></list>)
    =
    <list>0,1</list>
    =
    [0,1]

More clearly, if we have

  • [[0,1],[2,3]]

Then rolling that gives

  • roll([[0,1],[2,3]]) = [1,2,3,4]

So rolling is an act of flattening or leveling a container; in this case a list of lists of numbers is rolled out to just to a list of numbers.

Let’s sweeten the syntax up a little further by saying that + is an operator symbol for compose, that w is the same as wrap and that r is the same as roll; that gives us expressions such as

  • r(w(w(a)+w(b)) = r(w([a,b])) = r([[a,b]]) = [a,b]

5. Equations

There are equations associated with shapes or more precisely with shape composition operators. For List.append there are no such equations.

Set union, on the other hand, does have equations:

  • a + a = a // idempotency
  • a + b = b + a // commutativity

The first equation says that composing (uniting) a set with itself yields an identical set. It’s a no-op. The second equation says that the order of a and b is irrelevant to the outcome..

Greg also talks about three laws that relate to the parts of the monad metaphor (and indeed the formal definition of a monad). I’m still learning about these.

6. Shapes & Monads

There are many kinds of structures that qualify as monads.

6.1. The Identity Monad

This is the no-operation monad; the simplest of all monads.

  • w(x) = <id>x</id>
  • w(w(x)) = <id><id>x</id></id>
  • r(w(w(x))) = <id>x</id>

There’s not really a definition for + for this monad, but we could perhaps define + as w so that composition is wrapping.

6.2 The Maybe Monad

This is the monad of optional values. They are useful for certain functions that may not have useful results in some cases.

  • w() = <maybe></maybe> = <maybe/>
  • w(x) = <maybe>x</maybe>
  • r(w(w())) = <maybe/>
  • r(w(w(x))) = <maybe>x</maybe>

There’s not really a definition for + for this monad, but we could perhaps define + as w so that composition is the same as wrapping.

Trivia: In Haskell Just(x) is the constructor for <maybe>x</maybe> whereas Nothing is the constructor for <maybe/>. In SML these are called Some and None, respectively.

6.3 The List Monad

This is the monad of lists of values that we’ve already seen. For this monad we have a meaningful composition operation, which is append; append will join two lists together into a new list where the elements of the two are in sequence in the new list.

  • w() = []
  • w(x) = [x]
  • w(w()) = [[]]
  • w(w(x)) = [[x]]
  • r(w(w(x))) = r([[x]]) = [x]
  • w(a)+w(b) = [a,b]
  • w(w(a)+w(b))+w(w(c)+w(d)) = [[a,b],[c,d]]
  • r(w(w(a)+w(b))+w(w(c)+w(d))) = r([[a,b],[c,d]]) = [a,b,c,d]

In these examples I’ve not used markup syntax but I hope that by now you can intuit the simple translation between [] and <list></list>.

6.4 The Set Monad

This is the monad of sets of values. In this case I’ll use {} as the syntactic delimiter of set literal expressions, just to make it clear that these are sets and what the left-hand-side monadic expressions actually mean.

Under set union the semantics are as follows:

  • w() = {}
  • w(x) = {x}
  • w(w()) = {{}}
  • w(w(x)) = {{x}}
  • r(w(w(x))) = r({{x}}) = {x}
  • w(a)+w(b) = {a,b}
  • w(w(a)+w(b))+w(w(c)+w(d)) = {{a,b},{c,d}}
  • r(w(w(a)+w(b))+w(w(c)+w(d))) = r({{a,b},{c,d}}) = {a,b,c,d}

however, if we throw in a couple of duplicate values, the semantic distinctions between sets and lists becomes clear:

  • w(a)+w(a) = {a}+{a} = {a}
  • w(w(a)+w(b))+w(w(b)+w(a)) = {{a,b}+{b,a}} = {{a,b}}
  • r(w(w(a)+w(b))+w(w(c)+w(b))) = r({{a,b},{c,b}}) = {a,b,c}

These three expressions would have a different meaning under list composition.

7. Lessons

These lecture notes do not capture all the knowledge of the first lecture by Greg Meredith but they do show some simple examples of what the monadic operators do. I find this a more syntactic way of thinking that is actually quite appealing. It’s not the whole story though; only a fraction. The theory of monads goes deep, as does its practice.

In the following lectures, Greg will supposedly go into concrete applications of monads in the software design of Web applications. In other words, Greg will show-case monadic Web programming. I can’t wait to see what he’s cooked up.

The monad examples shown here are just of a fraction of the monads that I’ve seen examples of. This really goes to show the fundamental strength of the monadic abstraction.

Enhanced by Zemanta
About these ads

About xosfaere

Software Developer
This entry was posted in Computer Science, Datamodel, Declarative, Imperative, Paradigm, Software, Technical, Uncategorized and tagged , , , , , , , , , , , . Bookmark the permalink.

One Response to Shapely Monads

  1. Anonymous says:

    Dude someone like you needs to follow Greg Meredith around and translate everything he says from Gregspeak into a human language.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s