Trivial Monad solutions (cont.)

This is a continuation of the previous entry on the subject, with the solutions for exercises 3 and 4. But, we are now finally and formally introduced to the Haskell-style bind operator: >>=. What >>= (which is pronounced: "bind") does is to give the value the monad contains to the function that then uses it. More formally defined (specific to sigfpe's trivial monad example):

W a >>= f == f a

An example of the syntax (again, following sigfpe's post) is as follows:

W 5 >>= f

(where f was defined in sigfpe's post as an increment function for his trivial monad: f x = W (x + 1)). The above example would result in the (monadic) value W 6. So, now you see >>= (trivially) in action, and sigfpe asks us to put it into use for the following exercises.

The first exercise that we'll continue on in this entry is exercise 3, which is to prove the three monad laws:

Left Identity: return a >>= f == f a

or, a monadized value bound to a function is the same as applying a function to the plain value.

Right Identity: m >>= return == m

or, a monad bound to return is just that monad, again (or, the identity function for monads is bind return), and finally:

Associativity: (m >>= f) >>= g == m >>= ((λ x . f x) >>= g)

which is similar in spirit to associativity for addition, i.e.: (a + b) + c == a + (b + c).

Just a side note here, some people become discouraged when they are told "to prove" something, whereas if they are asked "to solve" a problem, they turn right to it. Fogel and Michalewicz rightly point out that proving and solving are basically the same process!

My cara spoza asked me, as I was attempting to (re-)prove liftM2 (+) for exercise 2, "Is proving difficult?" The question gave me pause: "Well, sometimes the simplest proof can elude me for days, and sometimes something that appears much more difficult comes in a flash."

So, let's prove each of these laws in turn, using the definitions of >>= and return as axioms.

First up, Left Identity:

Prove:	return a >>= f	==	f a
1.	return a >>= f	==	W a >>= f	return definition
2.		==	f a	>>= definition
Q.E.D.

Next, Right Identity:

Prove:	m >>= return	==	m
1.	m >>= return	==	W a >>= return	monad identity
2.		==	return a	>>= definition
3.		==	W a	return definition
4.		==	m	monad identity
Q.E.D.

And, finally, let's prove associativity. We'll start out by reducing the left hand side ("lhs") to something simpler:

Simplify:	(m >>= f) >>= g
1.	(m >>= f) >>= g	==	(W a >>= f) >>= g	monad identity
2.		==	f a >>= g	>>= definition

... but it was here that I became stymied, for I didn't see how to transform f a >>= g into something resembling the right hand side (rhs), which is m >>= (λ x . f x >>= g). Do you? Give it a try!

...

The thing to do, when one becomes stuck solving or proving something, is to acknowledge that fact, and then to try something entirely different. One way to try something different is to rework the simplification of the lhs so it assumes a form much closer to what the rhs is. I didn't see this approach to be fruitful, however: I reduced the lhs to be something pretty simple, so a rework would make the lhs more complicated -- clutter often obscures correlation. Another approach is to leave the lhs be and work on simplifying the rhs -- maybe a simplification there would yield an useful correspondence. Let's do that:

Simplify:	m >>= (λ x . f x >>= g)
1.	m >>= (λ x . f x >>= g)	==	(W a >>= (λ x . f x >>= g)	monad identity
2.		==	(λ x . f x >>= g) a	>>= definition
3.		==	f a >>= g	β-reduction

Ha! Now we see that the simplification of the lhs is identical to the simplification of the rhs. That was easier than expected.

Q.E.D.

To summarize this exercise, proving something or solving something is really a rather simple task: using the tools you have to match the solution to the problem. The fun part comes in when you discover new ways to use the given tools, or, finding out the given tools aren't sufficient, which means finding new tools to solve the problem. Once you have your tools, along with the problem statement and desired outcome, it is often the case that there is a simple walk from the problem to the solution, the solution to the problem, or both meet somewhere in the middle. Odds are, you are not the first one solving a problem, if you need help, there's a whole big world out there -- someone probably has already left the solution out there for you to find.

Exercise 4: Monads cannot be unwrapped completed back to the plain value they carry, but if a monad is layered, that is a monad contains a monad, it is possible to remove one or more layers. join is such a function that does this "unlayering". Given a layered monad mm = W (W x), join mm will return the value W x. The declaration for join is:

join :: W (W a) ⇒ W a

Define it.

Solution 4: Well, the declaration for join looks suspiciously like an application of >>= (you are pronouncing that operator "bind", right?), as it hands the value carried by the monad for function application.

join mm = mm >>= ?f?

The question then becomes "what function to apply the carried value to?" The problem is that >>= has already given us the answer, W x, so we just wish to have join return that value unaltered. Fortunately for us, there is such a function from combinatory logic called the identity combinator, I, which has the form λ x . x, and Haskell already has that definition (it is named id), so we simply use that for the hole in the above definition:

join mm = mm >>= id

Q.E.D.

In conclusion, I hope these entries have helped you to see that monads are actually a rather simply concept that are easy to use. This is just the tip of the iceberg, however: monads are used pervasively in Haskell, tackling a great many tasks. May I suggest the excellent and practical tutorial on Monad Transformers? Please do not be put off by the imposing front page to the paper, as this tutorial shows how monads and their transformers shine, giving a step-by-step introduction of new functionality of monads into a plain-vanilla system.

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.

God Be With Ye, Joel

My friend, Joel, just died this week, suddenly, leaving my friend, Sandy, a widow. The Apostle Paul writes: "God is no respecter of persons." [Rom. 2:11], but I certainly am, and there are very few people in this world that have earned my respect -- Joel was one of them. He and I could not have been any more different: his introspection foiled my exuberance, his patience, my wrath, his acceptance, my judgements. I think it boiled down to, essentially, his Irishness to my Italianness. Yet, as Sandy knows best, these two seemingly opposite characters did not clash, but deepened our friendship, and my respect for him over the 18 years that I've known him.

We all know the story that the Irish never say a bad word about the dead: a lady asked to speak on behalf of a man, universally reviled, who just died, struggled for a moment, then burst into a smile as she pronounced: "But he had a brother who could sing." For Joel, I have the opposite problem: I cannot recall one moment where he ever lost his cool or exposed himself to censure. For Joel, everything was alright or would work itself out, and he was there, doing his part to make that so. He was always warm in his greeting, in his inquiry, and took your causes, making them his own.

For example, it was Joel who got me on my feet after I left the military with my first job working at his company. He tried me in one role, working for him in marketing, but seeing I was more fit for computers and software, quickly shifted gears and championed me to the IT managers. He did this over and over again for so many people he came across -- he truly liked to help people, he didn't particularly care that this or that person did or didn't fit Joel's assigned position, he just helped to find the best fit for the person he was helping, regardless of his own benefit. I have rarely seen this egolessness in service: when I saw Joel doing this I saw it come from a rock-solid foundation of faith. He knew he was doing his part to help things along, so he had not one concern about the benefits to himself.

He was introspective and studious by nature -- his most natural pose was one of repose, with a book in his hand. But, at the same time, he enjoyed company. At a business function several years ago, Joel opened his house to me and three other young men for a lunch, prepared by Sandy, that I will never forget. The food, of course, was a very welcome respite from the starched business setting, but what I took away with me was Joel's absolute peace and comfort. It seemed to say: "This is my house, this is my home: I'm comfortable in it, and I'm comfortable sharing it with you." Our dessert was an Irish coffee Joey lovingly hand-measured that I have not tasted the like before or since. Joel was a stately craftsman: proud of his work, and pleased to share it.

I shall end with this: his service and conduct were a credit to himself and his family, and we sorely miss him. God bless you, Joel, may you rest in the company of the saints.

Let the Pictures Do the Talking

My Cara Spoza, Sweet and Dainty

I attended a family gathering of mi cara spoza's; it was a small party this time, there were only 40 or so people with family, friends, friends of friends and moiself (that is French; and yes, you must figure out why I listed moiself (that is French) separately). As Li'l Iz was sick (flu, 103.4^o temperature), I was not greeted, instead they looked at me, and asked politely, "Where's Diane?" (they were not impolite, so they didn't ask: "Who are you?") After I explained that she was looking after the sick girl, they coo awhile over EM ("She's soooooooooooooo sweet! She brought presents for her cousins!" because EM likes giving letters, drawings, and presents to her friends) and direct me to the food: "Eat! Eat! Eat!" No, they're not Italian, they're Philippinas.

Well, since Diane wasn't there, the subject of conversation naturally turned to her.

Them: Oh, you must miss her!
Me: Yes, terribly
Them: Ahhhhh! ... what do you like most about her?
Me: Oh, that she's sweet and dainty!
Them, puzzled: Yes, quite.

They must not get my sense of humor, because Diane is very sweet, pixie-like, one might say, but dainty? ... no. So, after a polite pause (yes, Diane's cousins are very polite, I already said they're Philippinas, right?), the conversation resumed.

Them: Well, she may be dainty, but she has her own mind ... you wouldn't want to mess with her.
I agreed: Oh, you could mess with her, but only if you wanted to lose.

This assent brought on much laughter and kibitzing (they call it tsizmis), and soon after eating some delicious cake, I excused myself to trade places with Diane to watch over the sickly child.

Me: Elenas, I'll be going home now, and Mama will be coming here; you may stay and play with your cousin Trisha.
EM, playing with her cousin, Trisha, not giving me a backward glance: Okay

I then thanked all 40 hosts and hostesses, and on my way out, I was confronted by little Trish: Why aren't you gone yet?

Well, I guess I don't need to worry about separation anxiety ...

Let's Go Fly a Kite!

Following my Nana's funeral, my parents, Lola and Pepé, decided to give us a visit. And so they did. My poor dad was knocked out the whole time with some nasty bug, so it was odd: his jovian presence was not accompanied by his usually jovial self.

Me, asking all present at breakfast: Do you know why the Roman numeral for 4 on clocks is "IIII", not "IV"?
all present: gives me a blank look
Me: Because the Romans feared inverting the first two letters of their Pater Deity would offend him.
all present: continuing the blank look
Me: You know -- "Jupiter" from the Greek "Zeus". [because, of course, everybody knows there's no "J" in the Latin alphabet.]
all present: regard each other and resume breakfast.
Me: I always love to keep my audience riveted!

Git it? Jovian, Jove, Jovial, Jupiter (or, and the Romans would say: IVpiter, or, as not to offend him: IIIIptier) ... *SIGH* it's hard to be pater familias.

So, as my dear father was recuperating, we decided on a cherry blossom outing, being that the weather was fine, but then Lola decided to watch over Pepé, and not even the enticement of quantity time with granddaughters nor the promise of ditching the far, far distant cherry blossoms (they were 5 miles away in Washington DC) for the much, much closer promenade at Greensprings Gardens park (which was 3 miles away) would persuade her.

Ah, well! so we packed the kite that EM had made and the kite that Pepé had bought at a dollar store several years ago (so, with inflation, that kite was now an eBay goldmine -- I fancied a 50¢ profit from its sale if I could ever wring it from the hands of my li'l tykes). As we stepped outside, my cara spoza exclaimed: What a fine day, no need for coats at all, as we're going to Greensprings! I agreed and left behind my nice, warm, comfy leather jacket ... good thing I wore a sweater! because as soon as we entered the car, my dear, sweet-tempered dainty cara spoza declared: We shall go to Hain's Point, instead. You know, Hain's Point, that peninsula jutting into the cold, cold Potomac River as it thrusts itself into the black waters of the Atlantic Ocean? That one?

Mater Familias: Yes, that one.

Well, then we needed to convince the tykes, because they, too, like their pater familias, had their hearts set on nice, quiet, warm Greensprings Gardens. But, no worries, the mere mention of a playground turned pouts of sorrow into squeals of joy, so off we went. As we arrived, ...

EM: Papa, why are you driving so slow?
Me: It's "slowly," Elena, and I'm driving so slowly because I don't wish to get a ticket for exceeding the park's speed limit.

... we could see the waves white-capped by a strong breeze as they crashed over the breakers (I kid you not -- if you don't believe me, believe the three gentlemen of a certain age who pulled up beside us in their red caddie only to have their loafers and dress slacks soaked -- soaked! I tell you -- by a wave catching them as they walked along the sidewalk). A strong, cold, breeze greeted us as we opened the doors. Well, I had almost determined to remain, hermit-like, in the van, when my cara spoza brought out mac-n-cheeze for the kiddies (Ooo! they squealed, mac and cheezie, pleazie!) and sandwiches for the adults. What, food? Well, I was a bit peckish (famished, actually), so I decided to forego my embargo and go with them to the picnic tables to eat.

Then it was time for kite-flying, but first we had an interlude, as EM needed to take care of some business. Her Lola requested I abstain from discussing the particulars of the matter, but it's a 4-letter palindrome where the first two letters are the given name of one of the most famous Chinese poets (pronounced, as I learnt from my friend Grace, "Lee Buy").

No, I cannot resist the impulse.

So, EM and I drove off to the baño, ...

EM: Papa, why are you driving so slow?
Me: I'm driving slowly, Elena. Will you drive the van back to Mama, when the park police arrest me for endangering the lives of these joggers, bicyclists and roller-bladers?
EM: No, Papa! I'm not allowed to drive yet!
Me: Well, then, there it is!

... as it was some distance from the park proper, and as we approached this circular building of an imposing granite edifice, EM became less sure of her need to, you know, use the facilities. Well, I promised that I would wait for her, but that wasn't good enough, because after I did my business (hm, sun roofs for public facilities make them very warm, yes, and also remove the need for electric lighting, but this can make the restrooms very pungent!), I found her outside the ladies' room door.

Me: Are you finished already?
EM: No, I didn't go; let's go, Papa.
Me: Elena, I'll wait right outside your entrance.
EM: Promise?
Me: Yes.
EM: Really?
Me: Yes.

With these assurances secured, EM bravely entered the scary, scary restroom. A minute later, she called out to me.

EM: Papa, I need to poop!

So, if you haven't solved the palindrome yet, then you have the answer now.

The next crisis came when I commanded her to flush the toilet, something she normally does at home without issue, but here it was another story.

EM: Papa, I'm scared!
Me: Well, okay, no kite-flying for you!
EM: NoooooOOOooOoOOO!
Me: Well, then, flush the toilet.
EM: But, Papa, I'm scared!
Me: Okay, look, you can flush the toilet and then run right out to me; I'll be right here by the entrance.
EM: Promise?
Me, sighing: Elena, flush the toilet now.
EM, flushing the toilet and running out to me as quick as a bunny: Eeeeeeek!

Before we drove back, we spied two mallards, and EM hid behind me, as she feared being nibbled by their ferocious bills. Well, after I reassured her and showed her that they retreated when I approached them ...

EM: Why, Papa? Why do they run away from you?
Me: They're afraid of being caught and thrown in a pot of boiling water.
EM: Why?
Me: That's what some people do to ducks. Besides, would you wish to be thrown in a pot of boiling water?
EM: No.

... so that emboldened her to give chase to them herself. I think they lost some weight from the exercise.

So, off we returned to Go Fly a Kite (No, sir; I didn't mean you personally!). Here's how people fly kites at Hain's Point:

Me: Okay, tell me when you're ready!
EM: Okay, Papa, let it go!
Me, letting the kite go.
Kite, whoosing straight up into the air.
EM: Wheeeee! Look, Papa, I'm flying a kite!

That's what you get with a steady, strong, sea breeze: perfect kite-flying, or sail-boarding, weather.

Both EM and Isabel had turns launching and flying the kite. When Isabel flew the kite, I was relieved to note that the kite did not lift her up into the air and carry her away -- those wind elementals like to play with little girls younger than five. I also noticed that the kite needed to go higher ...

Me: Let out the string so the kite may fly higher.
EM: No!
Isabel: No!

... so there was nothing for to but for me to lift each girl in turn onto my shoulders. Eventually they did let out quite a bit of string, so as Diane brought the shivering Isabel, still sickly with flu, back to the van, I reeled in the kite, hand over hand. EM was interested in the process, but not interested enough to help more than one dangerous handful. After we (I guess I'm using the royal "we" in this case) reeled in the kite completely, EM and I returned to the van.

Li'l Iz: Papa, when you were flying the kite, I missed yoooooouoouuuououuu!

I explained, with emphasis, that I was not flying the kite, and with that point made and settled, we headed off toward home.

EM: Papa, why are you driving so slow?
Me: I'm driving slowly.

The End.

Li'l Iz: No! You can't say "The End" because you didn't say "Once upon a time"!

God is bigger than the Woggie Man

My littlest, so far, has been parading around the yard singing loudly:

God is bigger than the Woogie Man
[hummed:]a-humma-hmm-hmm-hmhmh-hm ... and the TV
For God is bigger than the Woogie Man;
He's bigger than you and me!

... this obviously came from the Veggie Tales, but I only learnt the correct lyrics when her até joined the singing:

God is bigger than the boogie man,
He's bigger than Godzilla and the monsters on TV
Oh, God is bigger than the boogie man;
He's bigger than you and me.

... so I learnt two things today: God is bigger than the Woogie Man, and He's also bigger than the Boogie man, too.

That there is some big ol' God we got here!