How do I get better?

I just fielded a question from a programmer who wishes to improve his (Haskell) programming skill, and I responded with a reading list (below) and a referral to the Project Euler problems site. But I also see this as an excellent question for myself. How do you, genteel reader, recommend I improve my skill as a coder? Or, put another way, what book, or books, and which article, or articles, so totally transformed you from J. Random Hacker to J. Über Hacker (hacker being coder, or mathematician, or logician, or rule developer, or ...)?

My list is as follows. Would you kindly tell me what I need to read right now so I can see the light as you have?

Books for learning:

The Art of the Metaobject Protocol, Moon, et al
To Mock a Mockingbird, Smullyan
Reasoned Schemer, Bird, et al
Algorithms, a Functional Approach, Rabhi, LaPalme
Genetic Algorithms, Goldberg
How to Solve it, Modern Heuristics, Michalewicz/Fogel
Godel, Escher, Bach, an Eternal Golden Braid, Hofstadter
Prolog Programming for AI, Bratko
(and, after a year of programming in Prolog), Craft of Prolog, O'Keefe
A Grammatical View of Logic Programming, Deransart/Maluszynski
An Introduction to Mathematical Philosophy, Russell

Books for Joy:

Testaments Betrayed, Kundera
Last Samurai, DeWitt
Lord of Light, Zelzany
American Gods, Gaiman
Complete Enchanter, de Camp
Moor's Last Sigh, Rushdie

Noosphere:

"To Dissect a Mockingbird" article, Keenan
The lambda papers, Steele/Sussman
Growing a language article, Guy Steele
AI Junkie site
sigfpe.blogspot.com blog
randomhacks.net blog
the Monad.Reader (on haskell.org)
Comonad.Reader blog
"What the Hell are Monads?" article, Winstanley
"Monad Transformers, Step by Step" article, Grabmueller
"Generalising Monads to Arrows", Hughes
"Theseus and the Zipper", on the Haskell Wiki
"Escape from Zurg: Exercise in Logic Programming", Erwig
And for language construction/deconstruction: Lazy K, Jot, Iota and Whirl (well, at least they aren't INTERCAL ...), ... I suppose brainf**k should be mentioned here too ...
"The tale of N-categories" serial, starting with week 73, Baez

Combinators in Haskell

In this article, instead of continuing along my path of shoving Prolog (predicate logic) into Haskell, I'll take a break from that and shove Haskell into Haskell. This turn comes by way of my recent professional experience working with Prolog — I found myself oftentimes needing to write some purely functional code, but I found the Prolog semantics getting in my way, so, borrowing some of the ideas from my previous professional programming experiences with Mercury and Dylan (when Harlequin was still a going concern, and had picked up the Dylan ball that Apple, then CMU, dropped, making a really sweet Dylan programming environment), I implemented a set of libraries for Prolog, including basic ZF-set operations, propositional logic syntax, list/set/bag utilities, and the combinator logic of Schönfinkel.

"geophf!" You exclaim, horrified, "you don't really use combinators to write working production code, do you?"

Well, yes, and I also proposed a new one in addition to the ones covered by Smullyan in To Mock a Mockingbird, and have studied the make-up of the "void" combinator of Unlambda, so I'm one of those kinds of programmers.

In short, when I was working with Prolog, I shoe-horned a Haskell interpreter into to be able to write map and fold when I wished to write map and fold. Since Prolog has DCGs (Definite Clause Grammars), I lived a monad-free and worry-free life. Ah, yes, those were the days.

That was quite a trip down memory lane. Looking back, I marvel at my fortune, not only have I professionally programmed in those languages (and VisualWorks Smalltalk; that was fun when I presented the boss a solution in two weeks that he was expecting in two months — he was so impressed that he bought the VisualWorks system for the contract, made me mentor a junior programmer on Smalltalk (Chris Choe, a good guy to work with), and had me teach a brown bag course at work on Smalltalk, but I digress, again), but it looks like Haskell is now part of our solution at my current place of work.

Life is good.

Of course, it would be so much better if I had access to the primitive combinators in Haskell (did Miranda allow that kind of low-level access, I wonder). I mean, why should one write out 'const', a whole FIVE characters, when one simply wishes to use the K combinator. I felt that very pain all too recently. I had that freedom using my combinator library when I was working on Prolog ... goodness, even MITRE fabricated the Curry Chip.

So, I could not put it off any longer, I pulled out my dog-eared copy of Mockingbird and wrote the CL module, as I didn't see one in the Haskell standard library. It went surprisingly quickly and easily. There were a few snags, Prolog, being dynamically-typed, allowed me to define the reoccuring combinators of L, M, and U (definitions of the combinators are available in my combinator library or tabled form or as graphical notation (which includes a very nice write up of propositional logic in CL)), but Haskell's type system complains of an occur-check error. I have the hack to define the Y combinator ...

fix f = let x = f x in x

... but I'm having difficulty hacking the other self-applying combinators; any suggestions on how to implement those? I'm particularly interested in implementing Turings' universal combinator ...

Uxy = y(xxy)

... because of its interesting properties I'd like to explore.

Anyway, here's the ones I do have.

> module Smullyan where

It was pointed out to me in the comments that if you make the ((->) a) type a Monad, then some of the combinators simplify to monadic operators.

> import Monad
> import Control.Monad.Instances

These are some of the combinators presented in Smullyan's To Mock a Mockingbird. Some have direct Haskell equivalents, e.g.: I ≡ id, K ≡ const, C ≡ flip, B ≡ (.), but then that just makes my job easier here. I also admit a preference to the Schönfinkel combinators over the renamed Haskell equivalents, so here is the library.

We will not be defining combinators here that cause an occurs-check of the type system, e.g. L, M, U, but we can define some interesting ones, such as O and Y by using work-arounds.

If we wish to start with λ_I, then its basis is formed from the J and I combinators.

> -- identity (I have no idea to which species belongs the 'identity' bird)
> i :: a -> a
> i = id

> -- jay: jabcd = ab(adc)
> j :: (a -> b -> b) -> a -> b -> a -> b
> j a b c d = a b (a d c)

I actually spent quite a stretch of time building the other combinators from the JI-basis, e.g., the T combinator is JII, the Q1 combinator is JI, etc. When I attempted to define the K combinator, I ran into a brick wall for some time, until I reread the section in Mockingbird about how the noble basis has no way to define that abhorred combinator. Since that time I've fallen from grace and have used λ_K, but I've always wondered since if a complete logic could be reasonably expressed in λ_I, and if so, how would that logic be implemented? I haven't come across any papers that address these questions.

Musing again, let's define the basis of λ_K which is founded on the S and K combinators.

> -- starling: sfgx = fx(gx)
> s :: Monad m ⇒ m (a → b) → m a → m b
> s = ap

> -- kestrel: kab = a
> k :: a -> b -> a
> k = const

... okay, that wasn't too hard, so, SKK should be I, right?

--- :t (s k k) :: a -> a ... oh, yeah!

let's continue with some of the other combinators:

> -- bluebird: bfgx = f(gx)
> b :: (b -> c) -> (a -> b) -> a -> c
> b = (.)

> -- cardinal: cfgx = gfx
> c :: (a -> b -> c) -> b -> a -> c
> c = flip

Now we start defining combinators in terms of simpler combinators. Although, we could have started doing that once we've defined S and K, as all other combinators can be derived from those two.

> -- dove: dfghx = fg(hx)
> d :: (d -> b -> c) -> d -> (a -> b) -> a -> c
> d = b b

> -- thrush: txf = fx
> t :: a -> (a -> b) -> b
> t = c i

> -- vireo (pairing/list): vabf = fab
> -- e.g. v 1 [2] (:) -> [1,2]
> v :: a -> b -> (a -> b -> b) -> b
> v = b c t

> -- robin: rxfy = fyx
> r :: a -> (b -> a -> c) -> b -> c
> r = b b t

> -- owl: ofg = g(fg)
> o :: ((a -> b) -> a) -> (a -> b) -> b
> o = s i

> -- queer: qfgx = g(fx)
> q :: (a -> b) -> (b -> c) -> a -> c
> q = c b

-- mockingbird: mf = ff
m = s i i

... ah, well, it was worth a try ...

> -- warbler: wfx = fxx
> w :: Monad m ⇒ m (m a) → m a
> w = join

> -- eagle: eabcde = ab(cde)
> e :: (a -> b -> c) -> a -> (d -> e -> b) -> d -> e -> c
> e = b (b b b)

With the above definitions, we can now type-check that my JI-basis is correct: the type of I already checks, and the type of J should be equivalent to B(BC)(W(BCE))), ...

:t (b (b c) (w (b c e)))
(b (b c) (w (b c e))) :: (d -> e -> e) -> d -> e -> d -> e

and it is ... yay!

-- lark (ascending): lfg = f(gg)
l = ((s ((s (k s)) k)) (k (s i i)))

l :: (a -> b) -> (c -> a) -> b
a b = a (b b)

... ah, well, another one bites the dust ...

but we can define Y, albeit with a let-trick, thanks to Dirk Thierbach, responding to the thread "State Monad Style" on comp.lang.haskell:

> fix :: (a -> a) -> a
> fix f = let x = f x in x

> -- sage/why: yf = f(yf)
> y :: (a -> a) -> a
> y = fix

So, there you go, 15 combinators to get you started; now you can program a functionally pure and mathematically sound version of Unlambda (which exists and is called Lazy-K, by the way) using your very own Haskell system.

After all, why should someone ever be forced to write \x -> x^2 when they have the option, and privilege, to write w (*) instead?

Apologies for late Spring cleaning

It was pointed out to me that the colour cyan is difficult to read against a white background; my syntax highlighter outputs Haskell keywords as cyan, so I understand that reading the code here can be bothersome. So, I'm in the process of converting the cyan to a darker colour (which first involved me converting every <font color='cyan'> to <font color='#00c8c8'>, but then, part way through that process, I moved all font metadata to the stylesheet and now simply mark code, keywords and data types with appropriate metadata tags).

A bit of a long-winded apology for what you may see as several (and repeated) repostings from this blog.

Legal Disclaimer

Parties:

"I", "me", "my", "mine", the author, geophf, aka Douglas M. Auclair
"You", "your", the reader, user, coder, redistributor, referencer. Some non-exhaustive examples of "You" include, J. Random Coder, J. Random Corporation, J. Random Defense Agency, J. Random Financial Institute, J. Random Blog, J. Random for-profit corporation/LLC, J. Random Sovereignty, or http://planet.haskell.org ... just as examples.
"This blog", http://logicaltypes.blogspot.com, its content and entries originating from me.

License:

The words of this blog, http://logicaltypes.blogspot.com, are freely available to be read, to be commented on, to be referenced, or to be copied. I, the author, would like attribution, either to this site (an URL as reference is appropriate) or to the author, geophf, aka Douglas M. Auclair, but do not require it. I would also like to know if you find the topics discussed here useful, by either leaving a comment on this blog in the standard fashion, or by sending me an email at the scrambled email address of doug.at.cotilliongroup.dot.com. Descramble in the standard way.

The code in this blog is also free and freely available for commercial, noncommercial, academic or non-academic (if you happen to be a maraudering visigoth coder) use. Attribute is requested as above, but not required. Notification, as above, is also requested, but not required.

Limitation of Liability:

Note that, although the code and words are free and freely available for use and redistribute, no guarantee is made for any word or code sample published here. Some non-comprehensive examples include the following: if you use this code in a missile guidance system, and that missile falls in a populated area of friendly forces and civilians, I, my words, and my code are not to be held responsible for the resulting damage to life and to property. Or, if you implement systems published in this blog in a clustered system, and that system becomes self-aware, like Cyberdyne or the Matrix, and decides either to wipe humanity off the face of the Earth by triggering an all-out global thermonuclear war or by constructing power plants composed of the now-enslaved human population, I, my words and my code are not to be held responsible for the loss of life, freedom or property. Or, if you use this code or the ideas explored here in a Mars rover, and it offends the space alien natives, and the descend in force, 'War of the Worlds'-style, I, my words, and my code are not to be held responsible for the resulting loss of life and damage to property. Or, if you implement this system in a new Qbit supercomputer, and it results in either a singularly, sucking up the world Donnie Darko-style, or it results in a readjustment of space-type causing a complete quantum collapse of the universe, then I, my words, and my code are not to be held responsible for the early onset of the rapture. The examples enumerated above serve only to illustrate that I, my words and my code may be used but any and all damage resulting from such use, no matter how small or how catastrophic, may not be held responsible for that damage, legally, financially, or otherwise.

Exemption from obligation:

Conversely, should you use this code, or the words of this blog, and the use results in making, earning or saving money, property or life, such as, non-exhaustively, making profit in the stock market, or gaining a strategic or tactical advantage on the battlefield, or locating 3 missing teenagers, or saving 150 sailor's lives at sea, or seizing 26 million USD-worth of illegal narcotics per month, you are under no obligation to recompense me for profits or property gained or seized, lives saved, or other benefits merited. If possible and desired, I would like attribution in the code or words used and notification of the positive result of said use, but I also understand whims of corporate and personal desires as well as restrictions of non-disclosure agreements and concerns of national/world security, so attribution and notification are desired, as above, but not required. The examples above illustrating exemption from your obligation are neither exhaustive, meaning any gain is covered in this exemption clause, nor are they meant to illustrate implied or real events that have occurred in the past, present or future: I make no claim as the efficacy of me, my words, or my code in any of the above illustrations, nor do I make a claim that the above illustrations are based on any past, present or future events that may or may not have occurred.

Of course, I will not be uncivil, either. And gratuities are gratefully accepted (but, as per above, neither required nor expected). If, in gratitude, you do wish to recompense me for beneficial use of my words or code, please contact me at (scrambled) doug.at.cotilliongroup.dot.com to discuss methods of renumeration.

Coverage:

This license is put into effect for all entries posted by me. All comments by me are also covered by this license. Comments published by others are at the risk of the originators: I bear no risk nor liability of words published by others on this blog. This license is put into effect immediately, August 2, 2008, and covers all entries from the first entry ("Trivial Monad solutions" dated May 14, 2008) to all entries and content following it until such time that it may be superseded by a new license from me.

Difference Lists in Haskell!

Oooh! Scrumptious!

I've discovered while exploring one of my Tangents, the Comonad.Reader, that a member of the Galois team, Don Stewart, has developed a Difference List library ... in Haskell. My initial scan of the library is that it is simple, elegant and practical. Three feathers in his cap!

Excuse me while, initially, I replace in my code the 'cons then reverse' list-building pattern with Don's DList. I also can't wait to find other applications for this type.

While I'm away doing that, you can read sigfpe's blog, particularly his clever implementation of the Fibonacci series as a comonad.

Don't know; don't care: Whatever

The Maybe Monad type (covered in this blog in May) is a practical data type in Haskell and is used extensively. Since it is also a MonadPlus type, it is also immediately useful for logic programming, particularly of the semideterministic variety. Personal, I view Maybe as a second-order Boolean type, which, in itself, is a very powerful mode of expression, as George Boole demonstrated. Do yourself a favor, reread his works on algebra, or perhaps some musings from others, such as Dijkstra. Just as Donald Knuth showed that any n-tree could be transformed into an equivalent binary tree, and Paul Tarau put that to good, ahem, clause and effect, the Boolean algebra can model many other forms of algebras ... and does, for, after all, last I checked all my calculations are reduced to boolean representations (some call them binary digits).

Yes, Maybe's all well and good (and for the most part, it is — it's very well-suited to describe a large class of problems). But, as a dyed-in-the-wool logic programmer, Haskell has a bit of a nagging problem capturing the concept of logic variables ... that is, a thing that either may be grounded to a particular value (which Maybe already has when the instance is Just x) or may be free (which Maybe does not have). In short, the problem is with Nothing. And what is the problem? Values resolving to Nothing in a monadic computation, because they represent mzero, or failure, propagate throughout the entire (possibly chained) computation, forcing it to abort. Now, under the Maybe protocol, this is the desired result, but, when doing logic programming, it is often desirable to proceed with the computation until the value is grounded.

Now, deferred computation in Haskell is not a novel concept. In fact, there are several approaches to deferred, or nondeterministic, assignment, including my own unification recipe as well as the credit card transformation (which the author immediately disavows). The problem with these approaches is that they require resolution within that expression. What we need is a data type that captures succinctly this decided or undecided state. This we do with the Whatever data type:

data Whatever x = Only x | Anything

Just like Mabye, Whatever can be monadic:

instance Functor Whatever where
    fmap f (Only x) = Only (f x)
    fmap f Anything = Anything

instance Monad Whatever where
    return x = Only x
    Only x >>= f = f x
    Anything >>= f = Anything

You'll note that the monadic definition of Whatever is the same as Maybe, with the exception that Maybe defines fail on Nothing, whereas Whatever has no such semantics.

Even though Whatever is monadic, the interesting properties of this data type come to the fore in its more ordinary usage ...

instance Eq x ⇒ Eq (Whatever x) where
    Only x ≡ Only y = x ≡ y
    Anything ≡ _    = True
    _ ≡ Anything    = True

... and with that definition, simple logic puzzles, such as the following, can be constructed:

In a certain bank the positions of cashier, manager, and teller are held by Brown, Jones and Smith, though not necessarily respectively.

The teller, who was an only child, earns the least.
Smith, who married Brown's sister, earns more than the manager.

What position does each man fill?¹

An easy enough puzzle solution to construct in Prolog, I suppose, and now given the Whatever data type, easy enough in Haskell, too! Starting from the universe of pairs that contain the solution ...

data Man = Smith | Jones | Brown deriving (Eq, Show)
data Position = Cashier | Manager | Teller deriving (Eq, Show)
type Sibling = Bool
type Ans = (Position, Man)

universe :: [Ans]
universe = [(pos, man) | pos ← [Cashier, Manager, Teller],
                         man ← [Smith, Jones, Brown]]

... we restrict that universe under the constraint of the first rule ("The teller, who was an only child...") by applying "only child"ness to both the Teller and to the Man holding that Position (as obtained from the fact: "... Brown's sister ..."), but, importantly, abstaining from defining a sibling restriction on the other Positions ...

-- first rule definition: The teller must be an only child
sibling :: Position → Whatever Sibling
sibling Teller = Only False
sibling _      = Anything

-- fact: Brown has a sibling
hasSibling :: Man → Whatever Sibling
hasSibling Brown  = Only True
hasSibling _      = Anything

-- seed: the universe constrained by the sibling relation
seed :: [Ans]
seed = filter (λ(pos, man).sibling pos ≡ hasSibling man) universe

And, given that, we need define the rest of the rules. The first implied rule, that each Position is occupied by a different Man is straightforward when implemented by the choose monadic operator defined elsewhere, the other rule concerns the pecking order when it comes to earnings: "The teller ... earns the least" (earnings rule 1) and "Smith, ..., earns more than the manager." (earnings rule 2). This "earnings" predicate we implement monadically, to fit in the domain of choose ...

-- the earnings predicate, a suped-up guard
makesLessThan :: Ans → Ans → StateT [Ans] [] ()

-- earning rule 1: the teller makes less than the others
(Teller, _) `makesLessThan` _ = StateT $ λans. [((), ans)]
_ `makesLessThan` (Teller, _) = StateT $ λ_. []

-- and the general ordering of earnings, allowed as long as it's
-- different people and positions
(pos1, man1) `makesLessThan` (pos2, man2) = StateT $ λans.
        if pos1 ≡ pos2 ∨ man1 ≡ man2 then  []
        else [((), ans)]

... we then complete the earnings predicate in the solution definition:

rules :: StateT [Ans] [] [Ans]
rules = do teller@(Teller, man1) ← choose
           mgr@(Manager, man2) ← choose
           guard $ man1 ≠ man2
           cashier@(Cashier, man3) ← choose
           guard (man1 ≠ man3 ∧ man2 ≠ man3)

           -- we've extracted an unique person for each position,
           -- now we define earnings rule 2: 
           --      "Smith makes more than the manager"
           -- using my good-enough unification2 to find Smith

           let k = const3
           let smith = (second $ k Smith)∈[teller,mgr,cashier]
           mgr `makesLessThan` smith
           return [teller, mgr, cashier]

... and then to obtain the solution, we simply evaluate the rules over the seed:

evalStateT rules seed

The pivotal rôle that the Whatever data type is in the sibling relation (defined by the involuted darts sibling and hasSibling). We can abduce the derived fact that Brown is not an only child, which, with this fact reduces the universe, removing the possibility that Brown may be a Teller ...

universe \\ seed ≡ [(Teller,Brown)]

... but what about the other participants? For Jones, when we are doing the sibling/hasSibling involution, we don't know his familial status (we eventually follow a chain of reasoning that leads us to the knowledge that he is an only child) and, at that point in the reasoning we don't care. For Smith, we never have enough information derived from the problem to determine if he has siblings, and here again, we don't care. That is the power that the Whatever data type gives us,⁴ we may not have enough information reachable from the expression to compute the exact value in question, but we may proceed with the computation anyway. Unlike Maybe's resolution to one of the members of a type (Just x) or to no solution (Nothing), the Whatever data type allows the resolution (Only x), but it also allows the value to remain unresolved within the type constraint (Anything).⁵ So, I present to you, for your logic problem-solving pleasure, the Whatever data type.

---

Endnotes

1	Problem 1 from 101 Puzzles in Thought and Logic, by C. R. Wylie, Jr. Dover Publications, Inc. New York, NY, 1957.
2	f ∈ list = head [x|x ← list, f x ≡ x] When x is atomic, of course f ≡ id, but when x is a compound term, then there are many definitions for f for each data type of x that satisfy the equality f x ≡ x and that do not equate to id. We see one such example in the code above.
3	I really must define a library of combinators for Haskell, à la Smullyan's To Mock a Mockingbird, as I've done for Prolog.
4	This semantic is syntactically implement in Prolog as anonymous logic variables.
5	I find it ironic that Maybe says everything about the resolution of a value, but Whatever allows you to say Nothing about that value's resolution.

My Top-"10" Movie List

The following article is presented as a literate (literal) Haskell program. You can read it, and you can just as easily feed it to a Haskell interpreter, such as ghci or hugs.

I often get into conversations with acquaintances about movies, and when a (really) good movie is mentioned, I exclaim, "That's on my Top '10' list!", because, well, it is. After about 17 of these exclamations in a (series of) conversations, I'm often called on my assertions: "Well, what are your top 10 favorite movies then?" So, I've been forced to show my hand. Which language, though, to display this (ever-changing) list? HTML, no? XML? No, dreck, and no-no-no (been there, done that; barely survived to tell the tale). Haskell, of course. What follows is my top "10" movies as a program as activated data. If you need to see the movies in something other than code, I've posted the run result: voilà.

> module Movies where

The philosophy of this system, other than the fact that I count to 10 accurately, but I appear to have difficulty stopping there (just as the protagonist (?) in the movie "High Fidelity" has in counting to 5), is that I use the State monad to control how the output of the database is formatted. The resulting movie database is a tabled-HTML output.

Quite simply, the State monad contains a (modular) counter, and when my logic determines, then things happen at each cycle.

The Reader transformer monad carries the constant of when I wish to do these things, so the net result is a State monad counter wrapped in a Reader (constant) transformer. This article is not about the (very useful) topic of monad transformers, so I recommend the excellent article that covers that material.

> import Control.Monad.State
> import Control.Monad.Reader

> data Cat a = Cat String [a]

... unfortunately, the type-class system balks at using bare or aliased types, such as string, so here I wrap String in the "S" data type and provide my HTML representation against that.

> type Caddy = Cat (S Int)   -- quite the cad, indeed!

> data S s = S s String 

> instance Show (S s) where 
>     show (S s str) = cdata str []

Not particularly happy with the cdata transformation, either, but it's a quick and dirty implementation to handle a problem of character data in the database that would muck up an HTML representation.

> cdata [] ans = reverse ans 
> cdata (a:b) ans = cdata b ((if a == '&' then 'n' else a) : ans)

The typeclass Html is a pretty printer that generates HTML from the data set.

> class Html a where
>    asHtml :: a → ReaderT Int (State Int) String

Here, when the typeclass is given an instance of "String" (wrapped in the S data type), it pretty prints columns, wrapping every n columns were n is the constant held by the ReaderT transformer monad.

> instance Html (S s) where
>    asHtml x = do pre ← prefix
>                  post ← postfix
>                  return (pre ++ "<td>" ++ show x
>                          ++ "</td>" ++ post)
>         where prefix = do idx ← get
>                           return (if idx == 0 then "<tr>" else "")
>               postfix = do sz ← ask
>                            idx ← get
>                            put ((idx + 1) `mod` sz)
>                            return (if idx + 1 == sz 
>                                    then "</tr>\n" else "")

This is the engine control of the pretty printer. When given a category, it prints the title, resets the counter to zero, and then hands off the printing of columns to either itself (if the category (e.g. "Top 10 movies") contains categories (such as the genres)) or to the "String" printer (if the category just contains the movie list).

> instance Html a => Html (Cat a) where
>    asHtml (Cat title list) 
>          = do rows ← ask
>               put 0
>               cells ← mapM asHtml list
>               rest ← get
>               return ("\n<tr><th colspan='"
>                       ++ show rows ++ "'>" ++ title
>                       ++ "</th></tr>\n" ++ foldl (++) "" cells
>                       ++ closeCells ((rows - rest) `mod` rows))
>           where closeCells 0 = ""
>                 closeCells x = foldl 
>                                (λx y → x ++ "<td>&nbsp;</td>")
>                                "" [1..x]
>                                ++ "</tr>\n"

The database of movies follows:

> scifi, documentary, ferrn, romcom :: Caddy
> western, musicals, comedy :: Caddy
> horror, brit, oldies, sitcom, indie, drama :: Caddy

> movies :: Cat Caddy
> movies = Cat "My Top 10 Movies" 
>               [scifi, ferrn, romcom, musicals, 
>                comedy, indie, documentary,
>                horror, brit, sitcom, drama, oldies,
>                western, anime]

> anime = Cat "Animation" 
>             (map (S 1) ["Emporer's New Groove", "Wallace & Gromit", 
>                         "Shrek"])
> scifi = Cat "Science Fiction" 
>             (map (S 2) ["Solaris", "Blade Runner", "Galaxy Quest",
>                         "Donnie Darko", "Fight Club"])
> ferrn = Cat "Foreign"
>             (map (S 3) ["Le Placard", "Yojimbo", "Bleu, Blanc, Rouge", 
>                         "Siti no Samurai", "Sanjuro", "Eiron Shimbum", 
>                         "Schultze gets the Blues", "Eat Drink Man Woman", 
>                         "Legend of Drunken Master", "Shaolin Soccer", 
>                         "Kung Fu (Hustle)", "Cronos"])
> romcom = Cat "Romantic Comedy" 
>              (map (S 4) ["George of the Jungle", "Charade", "Bull Durham",
>                          "Bride and Prejudice", "L.A. Story",
>                          "Moonstruck", "My Big, Fat Greek Wedding", 
>                          "Bullets Over Broadway", "Clueless", "Ocean's 11",
>                          "Whole Nine Yards", "Princess Bride"])
> musicals = Cat "Musical"
>                (map (S 5) ["Guys and Dolls", "Singin' in the Rain", 
>                            "Mary Poppins"])
> brit = Cat "Brit"
>            (map (S 6) ["Cold Comfort Farm", "Importance of Being Earnest",
>                        "Hot Fuzz"])
> oldies = Cat "Ole Timey"
>              (map (S 7) ["O Brother, Where art Thou?",
>                          "To Have and Have Not", "Hopscotch"])
> western = Cat "Western" 
>               (map (S 8) ["Shanghai Noon", "Pale Rider",
>                           "Dances with Wolves"])
> comedy = Cat "Comedy" 
>              (map (S 9) ["Blazing Saddles", "Arsenic and Old Lace",
>                          "Dodgeball", "Young Frankenstein",
>                          "Harold & Kumar go to White Castle",
>                          "Revenge of the Pink Panther"])
> sitcom = Cat "Sitcom"
>              (map (S 10) ["Addams Family", "Addams Family Values", 
>                           "State and Main", "Rushmore"])
> horror = Cat "Horror/Suspense" 
>              (map (S 11) ["Jacob's Ladder", "Silence of the Lambs",
>                           "Shawn of the Dead"])
> drama = Cat "Drama" 
>             (map (S 12) ["Grave of the Fireflies", "Village", "Payback",
>                          "Shadowlands", "Station Agent", "Pleasantville",
>                          "Shoot 'em up", "Searching for Bobby Fischer"])
> indie = Cat "Indies" 
>             (map (S 13) ["Bagdad Cafe", "Ghost World", 
>                          "Living in Oblivion", "My New Gun"])
> documentary = Cat "Documentaries" 
>                   (map (S 14) ["Good Night and Good Luck",
>                                "thirty two short films about Glenn Gould",
>                                "Koyaanisqatsi", "Unzipped", "Ed Wood"])

This function calls the monadic system to print the movie database.

> showMovies :: Int → String
> showMovies cols = "<table>\n"
>                   ++ evalState (runReaderT (asHtml movies) cols) 0
>                   ++ "\n</table>\n"

> test = putStrLn (showMovies 3)

You can download it and see the embedded HTML in a code browser, such as eclipse. At any rate, executing test will get the above movie database in a tabled-HTML form.

What's the payoff?

Ah, yes. Well, if I had encoded my movie list in one of the currently popular metadata formats, such as HTML or XML/XSTL, then changing the number of columns per row would be prohibitively difficult with the former (HTML), and getting the metadata output as a properly formatted set of table rows would have been prohibitively difficult with the latter (XSTL). The Haskell program demonstrates both: you've seen how (relatively) easy it is to output the structured data as table rows of three columns per row, to change the number of columns (e.g.: to two columns per row), it's as simple as rewriting the test function to ...

test = putStrLn (showMovies 2)

... paid off; or, if you prefer, Q.E.D.

Alternative Implementations

Using the Reader monad is one of the ways to pass around "global" values, defining a ("global") constant function is another, sigfpe discusses those, as well as using the Reader Comonad, in an article on comonadic plumbing. I chose the Reader transformer monad instead of the Reader comonad for this article, because combining a comonad with a monad introduces arrows as the glue. Another article will explore comonads first before we dive into the thick of monad/comonad/arrow plumbing.