Trivial Monad solutions

Okay, a monad is a mathematical form, which sigfpe describes in his blog. He then proposes a series of exercises [reminiscent of my own exercises in combinatory logic], and even provides solutions. I came up with quite a different solution set, as I used his entry, and his entry only, as the source material.

A recap of monad: a monad is an opaque decorator. It takes a thing (including taking nothing) and hides that thing behind the monadic form. In sigfpe's example, the monad, W, takes a number (or anything else, for that matter), consuming it.

A monad, then, is like a katamari or a black hole, ... or Kuzko: no touchy!

So, then, the question naturally arises: how does one interact with the captured data? Well, the monad interface provides two basic operations in its protocol: return and bind (sometimes written >>=).

• return "lifts" an object into the monadic form. In propositional logic, return is a ⇒ M a -- 'return 5' would yield 'W 5' in sigfpe's example.


• bind takes a function that transforms an object to a monad and converts that function that transforms the object within that monad. In propositional logic, bind is (a ⇒ M b) ⇒ (M a ⇒ M b)

So, bind is used frequently when working with data and their monadic forms, and from it other functions may be derived, such as fmap, which maps (converts) a function that works on "ordinary" data to one that works on monads ... fmap is (a ⇒ b) ⇒ (M a ⇒ M b). Note the closeness to bind: the derivation of fmap is λ x . bind (return • x) (where • is composition (the B combinator, or Bluebird, from combinatory logic), and λ introduces a variable in the expression).

The above is enough introductory material to solve sigfpe's first two exercises, which I reproduce here:

Exercise 1: Write a function, g, that adds a number to a monad containing a number, returning a new monad with the sum, or g :: a ⇒ M a ⇒ M a.

Solution 1: well, given that addition is of the form (+) :: a ⇒ a ⇒ a, and that fmap lifts an ordinary function to a monadic one, the solution nearly writes itself:

g x my = fmap (+ x) my

What is simply done here is to construct a "plus x" function by applying x to the addition operator -- note that (+x) :: a ⇒ a. We then lift that function to its monadic equivalent with fmap and apply the result to the number (y) contained in the monad (my). Q.E.D.

Exercise 2: Write a function, h, that adds monadic numbers, returning a new monad containing the sum, or h :: M a ⇒ M a ⇒ M a

Solution 2: This provided a spot of bother for me. Whereas in the last solution, one could take the first number and apply it to addition to come up with a function that fit the form of fmap, in this case, we don't have any numbers with which to simplify addition to a form we can use, as they are all rolled up into monadic forms.

I described the problem thusly to my daughter, EM.

Me: You know addition, right?
EM: What's that, Papa?
Me: What's one plus two?
EM, immediately:Three! ... and ten plus ten is twenty! ... and twenty plus twenty is thirty! ... and thirty plus thirty is forty!
Me, clearing my throat, letting the errors pass in light of the delighted exuberance with which she delivered her answers: Um, yes, well. Here's my problem, let's say Thing One has a number hiding behind its back, that it won't show you, and Thing Two has a number hiding behind its back, too, that it won't show you, and you're asked to add those two numbers and give the answer to Thing Three. How do I do that?
EM, rolling her eyes: Papa, there isn't a Thing Three in the Cat in the Hat!
Me: Yes, well, suppose there was; how would I do this?
EM: Can you peek behind their backs to see what the numbers are?
Me: No, you're not allowed; besides, those Things are much too fast to run behind them, remember how they ran through the house with kites? ... So, we must use something like the fmap-box-maker, because addition is a box that takes numbers and yields numbers, but we need a box that takes Things and yields Things.

Using fmap does work its way into the solution I eventually derived, but another important player for this solution is also bind used in conjunction with a technique of deferred computation.

You see, just like the solution for exercise 1, we'd like to apply a number to addition to obtain a function for use by fmap. The problem is that we have no such number (just monadic values), but this is where bind is of use. Recall that bind :: (a ⇒ M b) ⇒ (M a ⇒ M b). The standard given explanation of bind is that it transforms a function that lifts ordinary data into monads to a function that works entirely in the monadic domain. But an entirely different way of looking at bind is that it treats a given monad like ordinary data as input to the lifting function. εὕρηκα! [No, I'm not about to hop out of the tub and run around town with my towel flapping in the wind]

The latter usage is the only one for those using >>= (which has the English language pronunciation of "bind", as well, confusingly), but if we take sigfpe's entry as the sole and base source, this "discovery" is quite the epiphany. And with that understanding, along with some deferred computational hand-waving, the solution then, again, presents itself:

h w1 w2 = bind (λ x . fmap (+ x) w2) w1

Working from the parenthetical expression outward, we again see the fmap (+ x) form, unaltered from the solution to exercise 1, giving us a number-to-monad function. The catch here is that we have no such number, so we give a promise that there will be such a number eventually with the λ-introduction. We then immediately fulfill that promise with bind: we apply the number-to-monad function to w1, treating that monadic value as if it were a plain number (that's what bind gives us permission to do), rendering the solution. Q.E.D.

Critique

I obtained solution 1 almost immediately by matching the logic of fmap to that of the problem description. It seemed to me to be rather trivial, so I was taken aback at the lengths and "arcane-ness" that sigfpe put into his solution.

On the other hand, sigfpe merely needed to augment his first solution with variable introduction to obtain his second solution. His second solution was trivially-obtained and obvious, given his approach to the first solution, whereas I had to struggle quite some time -- introducing both λ-abstraction (as sigfpe does) and bind (which sigfpe already had in the alternate syntactic form of >>=) -- to obtain mine.

In my defense, my solutions use only the monadic tools introduced in sigfpe's blog entry. On the other hand, Haskell programmers accustomed with monads rarely use fmap, regarding it as esoteric or superfluous, and instead rely on >>=, or inline binding entirely with the more "natural" do-notation (although there has been some grumblings against it), so in the light of that experience, sigfpe's solutions are natural and the first way most Haskell programmers would solve these exercises. This entry here, then, is from the perspective of someone not familiar with Haskell's approach to monads deriving the solutions from the principles of the provided function bind and its derived sibling fmap as discussed in sigfpe's blog entry.

Please see my next post for the solutions to sigfpe's exercises 3 and 4.