Falling Asleep at Mass

Originally posted Sep 19, 2005

So, anyway, we went to Mass, Our Lady of Mt. Carmel. This parish church looked amazing: it was a cathedral, almost a Basilica in its guilded reliefs and grandeur. Of course, since we are a bit away from the hubbub of Metro Manila, the Mass was entirely in Tagalog. Entirely. (Usually, at Marikina, the readings are in English and the order of the Mass: the Sanctus, the Lord's Prayer, the Homily are in Tagalog, so I can follow along well enough.) Our choir director came to the Philippines when his daughter's family came here on, um, business. He later complained to us that all the choirs here sing to the heartbeat: bump-bump, bump-bump goes the bass drum in every synthesizer of every choir he heard. Not so with this choir! They alternately chanted the Tagalog verses and then sang beautifully layered harmonies. It looked like there were eight members; the soloists sang wonderfully on their own, but also blended in with the other singers nicely.

The highlights of the mass where two full-on meltdowns by Isabel (she dropped her sunglasses on both occasions and could not be pried away from the floor) requiring that I take her outside into the sudden torrential downpour (that suddenly ceased as I walked outside carrying her) and my ability to jerk myself awake, three times, from a standing position. Those 5 pm Masses, after being awake since 2:30 am, are killers, I tell ya!

It's funny, as soon as I stepped outside, carrying the li'l tyke, she instantly stopped wailing to check out the neat surroundings. She became a sweet little baby again, looking out curiously from my arm to see the surrounding shops and houses, but she was especially attracted to the pair of Patriarchs guarding the entrance to the Church. On the right stood St. Peter in a green robe and gold cloth holding a pair of keys and on the left stood St. Paul in a grey robe and red cloth. I would point out features of each saint, and we would stand and admire the saint for a moment. Isabel would then shyly point toward the other saint, so then we would walk over to admire and observe. This cycle repeated quite a few times: Isabel also became interested in removing the rain water from the palms planted in front of the saints. As soon as she saw her mama pass by the entrance (returning from assisting Elena Marie, who needed to excuse herself for a moment), the game was up.

Good thing, too: she weighs in at 30 lbs now!

After Mass, the priest remained in the center aisle to dispense blessings. Diane's parents, who are not Catholic, shook his hand, instead of "mano"ing [bowing one's forehead to the back of the hand]. This surprised him. Then he saw me and Omar, who was wearing a "NYPD" dark blue shirt ... I think today was an unusual day for this priest.

We all then rushed out, back into the rain, to pile into our van. Isabel, being tired, began crying, so we formed a hasty plan: Elena Marie would go with Anda and Pap"U" to the pancake house for breakfast ("HOORAY!" Elena Marie is not one to turn down a pancake house invitation), and I would "guard" Isabel when Diane put her to bed. Not quite sure how well I "guarded" Isabel, because I was out before she was.

And then I woke up "this morning" to practice Kenjutsu, but, this time, the staff were used to my early morning ways (actually, I showed up at dawn, around 5:30 am, trying first to return to sleep), so, instead of panicking or keeping a very safe mental distance from me, they sat back and enjoyed the show. I always knew that 20 years of practicing swinging around a stick would turn out useful somehow.

'til next time (oh, by the way, our server's name at Pizza Hut (I was vetoed for McDo) was "Maui").

Time with Nana and Kiddies

Originally posted Nov 22, 2005

Okay, so, like, I just got this, ya know, email from Bill and Ocean saying that they were 'thinking' about me, so, like, overusing valley-girl-speak, I've overused my allotted vacation from writing emails to my family.

Sorry, this one is going to be short (ya know: work, 'n' stuff).

We all went to visit Nana and had a fun-taskic time; but not before receiving death threats from at least two relations: 'You tire out Nana, we come to kill you.' ... and these weren't iron-skillet warnings, no-no, these were, 'you like your eyes inside your head instead of outside, right?' kind of warnings. I knew I was Italian; I didn't know I was connected to the Mafia, though. Now I do.

We took Nana to 'Make your own teddy bear shop', and we all had fun. They had six stations install to stuff, to brush and to clothe the new playmates. Please allow me to welcome, officially, 'Emily' and 'Bamboo' [pron: 'ba-bu' by Isabel, or 'Kah(t)' when she forgets the name], two ballerina cats into the family. They are constant companions of the children, even unto now.

Here's the kicker: Nana served Gnocchi. ... and, no, you can't have any. (She asked me: 'How is it?' I asked her back: 'How can I phrase my answer in such a way in that you will serve this when I visit next time?' She laughed. BTW, the 'Italian' restaurants here don't know what gnocchi is. When I ask for vermicelli, they say, "We don't have that." "Do you have angel hair pasta?" "Oh, yes." "I'll have that, then." *sigh*)

Dad took us to the US Coast Guard Academy to watch a 'Pass in Review'. I got really 'homesick' watching those kids march past us. Hm; maybe they have a faculty position open ... ? The pass in review was in honor of a businessman, ex-army, who had donated a sum to the USCGA. That's nice of him; as the Coast Guard is always stretching: overworked and under-budgeted.

-----

Diane recently had a 'Mom's nite out' where she and other neighborhood mommies go on a supper outing and get a break from the kids and swap stories. Poor Elena Marie discovered that she is now very strongly attached to her mother, and started crying as Diane left for her supper (Courageous me: "It's okay, go on ahead; I CAN HANDLE THIS!" (yeah, right)). She didn't stop crying for two continuous hours. This woke the sleeping Isabel, who joined in the chorus for the second hour. Hm, turns out I couldn't handle this situation all that well, so, when I promised the kids that we would go out to find their mother, they sobered right up and off we went (As we were preparing to exit, Isabel's chin began to quiver: "No-no, Isabel, no crying if we are to find Mama"; she found some fortitude so as to press on). We hopped into the van, and we set out for the restaurant.

What do children do in a late night van ride? They fall asleep: quickly and deeply. Hey, dummy Dad, next time think of this option sooner than two hours into the saga! So, I turned toward home and parked in the driveway. ... and waited in the driveway for two more hours for Diane to return. The four-hour outing was a very good one for Diane. She was shocked to see us waiting in the van, but I didn't see an alternative: waking them up by removing them from their car seat would only restart the saga with a new intensity.

Of course, now that Elena Marie has become acquainted with the idea that being apart from her mother is too much to think on, she is now inseparable from her, even for dental appointments, etc. So, I told you the above story to tell you the below one.

-----

Diane had a teeth cleaning appointment during a lunch break. Elena Marie made it generally known that she would prefer to be with her mother. So we settled on a plan of attack that would have me chaperone Isabel while Elena Marie went with Diane to the Dentist's. This worked perfectly: Isabel and I dined at the Macaroni Grill (yes, the 'what's vermicelli?' place), and I have never seen a little girl have so much fun! It helps that she's attached to me, now, and found the prospect of an outing with Papa to be a reason for running in place and giggling ecstatically. The restaurant setting helped, too: they provided us with a rolled paper table setting and, count'm, FOUR CRAYONS! While we waited for our food ("The usual?" Our waiter, J.C., was pleased to know my order and pleased I remembered his name), Isabel alternately drew pictures (these she showed off with a good deal of satisfaction) or demanded I trace one, the other, or both of her hands or draw a new caricature of 'ba-ba!' [her personal pronoun; she calls herself 'baby']. She would have nothing to do with her chicken strips and french fries, instead, she would only take food offered from my plate. She also explored every detail of our booth, prancing, sans care, on the seat.

That is, until she tumbled from her precarious position to land with a solid *THUMP* on the floor under the table. After some crying, a kiss on the hurt, and some hug-time, she was good as new, and good thing this incident occurred at the end of our lunch after Diane had phoned to inform us of her return.

I was concerned that Elena Marie received the short end of this stick, but these concerns evaporated when I saw her, the next morning, line up her dolls, wiping their mouths with wet-naps: she instructed me that she was the doctor and they were getting their teeth cleaned.

-----

The next appointment followed a similar track: Elena Marie informed us of her preference (you do know how children inform parents of a view, right? If you don't know, I'll give you a hint: tears for hours), but this time I accompanied everyone on the visit. The waiting area was perfect: it had a kiddie korner, stockpiled with books and some other toys. So, after Elena Marie's initial reserve, both children came to me in turn demanding I read this or that book (or one of the five or so other books that they grabbed from the pile) to them, and when I paused to take a breath, Elena Marie would very sweetly sing out: "Papa, will you please read?" and punctuate the 'request' with a dazzling smile.

*sigh*

-----

Okay, back to work for me. Ocean, Bill: you can stop 'thinking' about me (I think 'thinking' about someone means 'calling the police to dredge the river for remains', so I'm sorry to cause any concerns). You all have a day that as good as a little girl singing to you and smiling dazzlingly while another one giggles ecstatically while running in place.

Hide 'n' Seek

So, I've been working on a new entry on monadic nondeterministic computation for three days now. Then what happens? My browser freezes, locking away three days work. So, what does one do, at 0530 (that's A.M.), when this happens? Start from scratch? Obviously, but then was not the time for doing that, being I was a bit unstable after my eighth operating system reinstall (don't ask, unless you want an earful), so off to bed I went. Instead, I'll treat you with some historical post not yet posted on this blog. Here's the first one:

Originally posted Nov 28, 2005

Hello, our family has been having it's usual plain-ole quiet domesticity, so I thought I'd share a little story. And so here it is.

Elena Marie enjoys organizing our playtime activities (statements like: "Papa, do a puppet show; here are the dolls you will use" and "Papa, I will be the teacher and you will be the daddy and Isabel will be the baby" (which induces Isabel and I to sit in front of Elena Marie raptly as she educates us on the essences of things: "This is this, and this is this, ... and this is ... a stick!")), so this weekend Elena Marie declared that we will play hide-n-seek: "You and Isabel hide under the bed [pointing to the specific bed], and don't hide anywhere else or I'll get lost!" She said, "Okay, go hide now!" looking to make sure we hid ourselves properly (I stood my ground: "You must count first!" 'cause I'm firm, and stuff ... (firm as in '"silky tofu" firm', not as in 'law firm')) and we promptly hid in the bathtub. After counting, she looked around the house (starting by looking under the indicated bed, I assume) and finally found us (I suppose it helped a bit that Isabel and I were giggling in anticipation and "peeking" out from behind the shower curtain).

Well, now it was the turn of Isabel and me to count and to seek. Elena Marie started the round off with panache: "I will hide under the bed here, okay, Papa?" indicating the same bed -- it wasn't really a question. So, dutifully, Isabel and I counted (Isabel sounds so sincere -- "awwwwwhn, duuuu, eeeee ..." -- as she counts), and then we embarked on a seeking adventure: we walked into the bedroom -- "Is she hiding in the closet, Isabel?" Isabel looked in the closet: "naaoowwh" meanwhile Elena Marie scratched the floor from under the bed, hintingly. We next went to the laundry bin -- "Is she here, Isabel?" Isabel looked at the clothes, searchingly: "naaowwwh!" Elena Marie: *scratch-scratch* We went into the hallway: "Isabel, is Elena Marie hiding in the banyo?" Isabel ran to the toilet, opened the lid, peered in and declared: "naaooww" as she slammed it closed.

That last little maneouver paralyzed Diane and me into fits of hysterics. I coundn't see because my vision was obscured by tears of laughter, and Diane was doubled over. At this point Elena Marie abandonned her subtle play and called out from under the bed, when drew Isabel "to find" her sister, so we all laughed and applauded each other's excellence.

Good times!

Choice with Monads: List, Maybe, Either

We've seen up to now what monads are and how they can be useful in simple ways, such as for heavy lifting on recursive addition. So, monads are useful for housekeeping when you have more work than a computer could handle in a straightforward manner. This work is called deterministic, meaning that the computation occurs in only one way. As we have seen, monads can be helpful with this kind of computation. But monads can be helpful with nondeterministic computations, or computations that proceed along multiple possible paths, as we shall see.

Haskell comes with three kinds of monads that have been used specifically for nondeterministic computation: the Maybe monad, the list data type and, a new one, the Either monad.

We saw the first one in the previous post: the Maybe monad. This monad type has two instances: Nothing and Just x (where x is the specific value of the computation). The Maybe monad is illustrated by the two dialogues below:

Scenario 1
Waiter:	How is the pork chop, can I get you anything to go with that?
Custamah:	Oh, Nothing for me, thanks.
Waiter:	Wonderful, enjoy your meal.
Scenario 2
Waiter:	How is the pork chop, can I get you anything to go with it?
Custamah:	Oh, Just a small bowl of applesauce, please?
Waiter:	Sure, I'll bring that right out

The waiter in the above two scenarios doesn't know exactly what the customer will want, but that waiter is pretty sure the customer will ask for Nothing or for Just something, and these options describe the Maybe monad type.

Another example of this kind of monad is the list data type. But whereas the Maybe monad allows two options (the answer or failure), the list data type (a monad) allows multiple answers (including no answers, which is represented by the empty list). These kinds of monads form a protocol called the MonadPlus class, just as the more general monad data types form the more general protocol of the Monad class, and just like regular monads, conform to a set of laws.

First, let us specify and explain what the MonadPlus protocol is. All MonadPlus types must have the following two properties defined:

mzero :: m a -- the base, or usually interpreted as fail, value; and,
mplus :: m a → m a → m a -- a function that chooses a success value when offered two values

For the Maybe MonadPlus type the above properties are defined as follows:

mzero = Nothing
Nothing `mplus` b = b
a       `mplus` b = a

In other words, Nothing is the failure case, and mplus tries to choose a non-Nothing value (roughly: "If a is Nothing, pick b; otherwise pick a." Here's a question for you: what happens when both a and b are Nothing, and for what reason?) Note the interesting semantics of mplus -- it is not at all addition, as we expect, for:

Just 3 `mplus` Just 4 = Just 3

Recall that if we wish to do monadic addition, we need to define such an operator.

madd :: (Monad m, Num a) => m a → m a → m a
madd = liftM2 (+)
Just 3 `madd` Just 4 = Just 7

So, now madd has the triple meaning here: it is not mplus (which is not addition), it is addition for monads containing numbers, and it either heightens awareness or annoys the cause of "MADD". Got all that?

The Maybe type has a special handler, called maybe. Its type signature is:

maybe :: b → (a → b) → Maybe a → b

What does this function do? Well, we've already seen it in action with the monadic Ackermann and Fibonacci solutions. One can read the arguments from right to left, to get the feel of an if-then-else: if the last argument is Just a, then pass a to the second argument (which is a function that converts an a to the proper return type); else execute the first argument. A very compact and useful function when working with Maybe types.

The second most commonly used data type used for non-deterministic computation is the list MonadPlus data type. It has an interesting variation from the Maybe definition:

mzero = []
mplus = (++)

In other words, the empty list ([]) is the base (failure) case, and mplus here actually is addition ('concatenation', to be technically correct); addition, that is, in the list-sense. But it all works out, particularly when it comes to the base cases, for:

[3] `mplus` [] = [3]
Just 3 `mplus` Nothing = Just 3

But, on the other hand, mplus is differnet when handling non-base cases for the Maybe and list monad types, for:

 [3] `mplus` [4] = [3, 4]
Just 3 `mplus` Just 4 = Just 3

But this difference is consistent with the different types: the list monad allows for multiple solutions, whereas the Maybe monad allows only one.

The list data type has too many special functions associated with it to review in this post. I recommend a review of the Haskell online report to get a taste of list's rich functionality, and then read Eric Kidd's post on backtracking with monads for some insights into using list monads in nondeterministic programming.

The third data type that is used, albeit less frequently, for non-deterministic computation is the Either data type. It's structure is as follows:

data Either a b = Left a | Right b

The way Either operates is that it offers a mutually-exclusive choice. For example, little Isabel sits to my Left and her até Elena Marie sits to my Right, so at 4 p.m. I must choose Either one to serve tea first: Left Isabel or Right ElenaMarie.

The interesting distinction of the Either monad to MonadPlus types such as the list data type and the Maybe monad is that both options are weighed equally, or, more to the point, neither is considered to be the base case. This means that Either, qua Either, is not in the MonadPlus class. With this caveat, can the Either type be used for non-deterministic computation? Yes, absolutely!

Not only can the Either type be used in its basic monadic form, but it also can be coerced into the MonadPlus class. How? It's simple, really. By simply choosing one of the branches to be the base (the Haskell library designers chose Left), the Either type now conforms to that protocol. The convention assigns the error message (a String) to the Left and the value sought is assigned to the Right one. This rather reduces Either to a glorified, error-handling, Maybe, and that is how it is used in every-day Haskell code for the most part.

The Either monad also has a special handler, either, with the type signature of:

either :: (a → c) → (b → c) → Either a b → c

This function is in the same vein as the Maybe handler, but complicated by the fact that maybe has only one (success) type to handle, whereas this function has two possible types it deals with -- either's type translates as: if the answer from the third argument (Either a b) is Left a, then feed a to the first argument (a function that converts the input value of type a to the output of type c), but if the answer from the third argument is of type Right b, then feed b to the second argument (a function that converts the input value of type b to the output of type c).

What we've seen in this entry is an introduction to the MonadPlus class and three examples of monads that allow for choice, Maybe, the list data type and Either, and saw an example for each which demonstrated their ability to code with choice.

The next entry will further explore the MonadPlus class and some of its powerful functions, such as msum and guard, and how the MonadPlus class allows us to code in a declarative nondeterministic style.

No "fib"bing; getting into the monad groove

The title is groan-inducing, as all my "jokes" are. I guarantee it: once you've finished reading this entry, reread the title, and you won't be able to stop from groaning.

The Fibonacci series goes as follows: 0,1,1,2,3,5,8,13..., or put another way, the current number is obtained by adding the previous two numbers. It is useful for many things, as its limit is the golden ratio, found in nature (the spiral of some crustaceans and the population growth of rabbits [they must be stopped!]) and in artifice (windows, painting, doors, buildings follow the width and height of this ratio)).

Any fibonacci number can be easily computed from the following formula ...

fib :: Integer → Integer
fib n | n ≡ 0     = 0
      | n ≡ 1     = 1
      | otherwise = fib (n-1) + fib (n-2)

... that is, easily computed if this world were purely mathematical, including the caveat that any computable function could be instantly computed. Run on a computer, fib 25 slows noticeably and fib 50 may as well describe the halting problem, because I wasn't going to wait around for it to terminate.

Note the similarity between the computation of the Fibonacci series to the computation of the Ackermann table. They are not the same kind of problem, mind you, as the Ackermann is not primitively recursive; the Fibonacci is "only" doubly (branching) recursive. But they are similar enough in that they can be solved in similar ways. Given that the current Fibonacci number is the sum of the previous two Fibonacci numbers, we need only a (reversed) list to memoize the previous results, so the above sequence becomes:

[..., 13, 8, 5, 3, 2, 1, 1, 0]

and the "next" Fibonacci number would be simply the first two elements of this list (21, in this case). But how do we know where we are in the sequence? Easy: the length of this list tells us where we are, and in this case, the list has 8 elements, meaning the "next" Fib is 9th in the sequence.

So, turning to monads with this list structure for memoization, the code falls out as follows:

fib :: Int → FibS
fib n = get >>= λmem . maybe (fib' n >>= update)
                             return
                             (gimme mem n)

So, fib is now simply a decision: "Do I have the fib requested in the list?" "Yes: gimme it and return it" or "No: compute it and then update the list"

The list is a very slight variation on a regular list type, as we choose to carry around its length (as opposed to recomputing it at each iteration), and we lift this new datatype into the State monad (as we did with the Map datatype for our Ackermann monad optimization):

data Mem = Mem [Integer] Int
type FibS = State Mem Integer

The actual computation function is lifted into the monadic form with very little variation ...

fib' :: Int → FibS
fib' n | n ≡ 0     = return 0
       | n ≡ 1     = return 1
       | otherwise = liftM2 (+) (fib (n - 1)) (fib (n - 2))

... where monadic addition, liftM2 (+), replaces addition in the usual sense (recall the spot of bother we had "adding" Thing One to Thing Two), and where the plain numbers are lifted into the monad with return. In brief, the substance is now monadic but the structure is the same as our original, plain, fib.

The other housekeeping functions are new for the monadic solution, but what one would expect. The update follows in the same vein as the one for the ackermann monad:

update :: Integer -> FibS
update n = do (Mem lst len) ← get
              put (Mem (n:lst) (len + 1))
              return n

An interpretation of the update function is that it is the identity function with the side-effect that it remembers the result that it returns.

The only other function is the self-describing gimme which retrieves a previously-computed fibonacci number from memory:

gimme :: Mem → Int → Maybe Integer
gimme (Mem (h:t) len) n | len ≡ n   = Just h
                        | len > n   = let x = (len - 1) - n
                                      in Just (t !! x)
                        | otherwise = Nothing

This gimme function uses the Maybe monad and its functionality, saying "If I have the value already computed [If the list length is equal to or greater than the requested index], then return Just that value; otherwise I've got Nothing, so you need to compute that value."

In summary, we've decorated the naïve fibonacci algorithm with some memory and three new functions (one manager and two support functions). What is the payoff?

Ready> fib 1500
[no delay]
135511256685631019516369368671484083777860107124184972421335
431532214873108735287506122593540357172653003737788143473202
576992570823565500453499141029242495959974839822286992875272
419318113250950996424476212422002092544399201969604653214384
983053458933789325853933815390935494792961948008381459961871
22583354898000

Ready> fib 50000
[4 second delay]
[10615 digits]

Ready> fib 60000
[2.5 second delay]
*** Exception: stack overflow

These results are a great step forward over the naïve fib implementation (which essentially froze at fib 50) and even memoized implementation reported elsewhere (which ran out of memory after fib 1450).

Huzzah! then for efficient program representation in Haskell and monadic code.

"On an ordinary day ..."

"...the extraordinary way you take what I can give and you treasure it."

Yesterday was my 41st birthday, so I'm now in my 42nd year. My sister, Beki, asked me, "So how does it feel to be 41?" and I answered that it feels like any other age -- an ordinary day. "Good," she replied. She's so grounded.

So, my cara spoza treated me for two outings: Li'l Iz and I had Queen Elizabeth tea at the Pinkadilly and then Elena Marie and I spent the evening watching the Nationals get shut out by the Chicago Cubs (no hard feelings: the Cubs have a birthday boy, too -- actually, I blanched when reading the birthyears of the players. Fukudome is a grizzled ancient, being born in 1977. I saw player cards of kids born in 1985. How can they hit a fast ball (and hit it well!) when they aren't even out of diapers yet is a mystery to me.)

I also received a nice birthday present from the UNSC, and finished up the day completing my first hard masyu puzzle.

A good day. Now, back to taxes.

Oh! my acking monad!

So, we just saw, after reams of paper on proving in inscrutable detail the three monadic laws, that after all that, we see that using them is pretty easy. Fancy that, Hedda!

Haskell does provide several different kinds of monads for various uses, but sometimes one must roll one's own to fit the current need. I was exploring the ackermann function, curious to know what A_4,2 looked like [oh, yes, 19730 digits in all its (gory) glory -- I went there!] (other than the cop-out of 2⁶⁵⁵³⁶-3 that is listed in Wikipedia), and whether my computer could calculate and display that value [obviously it could, but it took some work (see below) to arrive at that point]. The ackermann function written in Haskell looks very much like its representation in standard mathematical notation:

a :: Integer → Integer → Integer
a m n | m ≡ 0           = n + 1
      | m > 0 ∧ n ≡ 0   = a (m - 1) 1
      | m > 0 ∧ n > 0   = a (m - 1) (a m (n - 1))

The "problem" with the Ackermann function is that even though it is easy to write, the recursion required to arrive at a solution from even small (single digit) inputs is staggering. My computer staggered and then killed the computation in mid-process (too bad Redjak didn't have that option). The Ackermann function, being not primitively recursive, is also highly redundantly recursive, so it would be nice to provide "hints" to the program, something like: "Oh, you've already computed A_3,1 to be 13, so you don't need to recompute that entire branch any more."

This "hinting" has a name in computer science; it's called "memoization", and Haskell provides the State monad that can be used to cover that functionality quite nicely. As we're computing the values that build up the solution, we put the smaller-indexed solutions into a dictionary, something like:

A3,1	=	13
A2,2	=	7
A2,1	=	5
... and so forth ...

Such a dictionary in Haskell is called a Map, because we are mapping from the "word" (the indices of the Ackermann function) to the "definition" (the solution)...

type Index = (Integer, Integer)
type AckMap = Map Index Integer

... and we wrap that Map with the State monad ...

type AckMapS = State AckMap Integer

... where AckMapS uses the AckMap dictionary to provide the preexisting (partial) solution, or, given there's none yet, populates the solution calculated (the Integer) into the dictionary at the current Index. Simple, yes? So, all we need is an utility function that does the lookup or updates the state ...

ackify :: Integer → Integer → AckMapS
ackify m n = get >>= λma . maybe (a' m n >>= update m n) 
                                 return
                                 (Map.lookup (m, n) ma)

... the update function that actually does the housekeeping ...

update :: Integer → Integer → Integer → AckMapS
update m n ans = do mappo ← get
                    put (Map.insert (m, n) ans mappo)
                    return ans

... so that our monadic version of the ackermann function is as follows:

a' :: Integer → Integer → AckMapS
a' m n | m ≡ 0           = return (n + 1)
       | m > 0 ∧ n ≡ 0   = ackify (m - 1) 1
       | m > 0 ∧ n > 0   = ackify m (n - 1) >>= ackify (m - 1)

which looks very much the same as the original function, with calls to a being replaced by calls to the lookup-or-update ackify function and function composition (e.g. a (m - 1) (a m (n - 1))) being replaced by the monadic composer, >>=. So, from the above demonstration we see that monads are not only easy to use, but also easy to "roll your own" and integrate into preexisting non-monadic code without much fuss.

---

Critique

Although the incorporation of the State monad dramatically speeds processing solutions and makes some solutions computable that were unreachable under the naïve approach, there are at least two better generalizations:

1. Use the fixpoint (or the Y-combinator) of the ackermann function so that one can now decorate the engine of computation without altering its structure at all! Incredible! So instead of using a monad to abstract stateful decoration of computations, the fixpont can be used to abstract any decoration of computation!


2. Use the compiler to change the code, instead of having it programmed in. Many functional language compilers have the option to memoize computations automagically. So, instead of writing code that memorizes partial results, the compiler intercepts the computation, replacing computation with previously calculated values (or running the computation if no such value exists and then storing that result into the runtime). No extra coding; no "troublesome" monads.

---

Critique on the critique

On the other hand ("there are five fingers", as my favorite Mother-in-law enjoys rejoining),

1. The fixpoint solution is more general and more elegant, but being more general suffers in a slight decrease in efficiency: it more than likely will run more slowly than the specialized monadic state solution


2. With an explicit encoding of state, the programmer has direct say into what is memoized and what is not, but with a compiler directive, everything is memoized. Since the Ackermann function can be represented by simple functions for m < 4, the map can be replaced by a faux-map for those values, reducing the memory footprint of memoization to only a couple of cells for m == 4 (as opposed to over 150,000 cells for m == 4 and n == 1 using the naïve memoization scheme).

... so the above described solution may be "good enough" for the task at hand, after all. Put another way, when I said I was wrong, I might have been wrong. Caveat programmer.