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 theCat 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.

## No comments:

Post a Comment