Composing functions with Arrows

The Arrow class in Haskell is a generalization of the Monad class. Whereas a Monad type contains a value, and therefore is often used to represent state (in that the value captures the output of a function), an Arrow type represents the entire function, capturing both its inputs and outputs.

This is very Prolog-y. In Prolog, there are no functions, per se: the procedure's parameters (both input and output, if the procedure has any) are explicit in the declaration.¹ It's this total control of the procedure's environment that makes writing, e.g., aspects for Prolog a trivial exercise.

With Arrows, Haskell, which has always been friendly to function composition, receives another way of controlling data flow and composing functions. This topic is broad, diverse and general, and I am just starting down the path of exploring the Arrow class, so this entry will concentrate on only one aspect of the Arrow class, that is data flow through a composed arrow.

The problem comes up often enough: one wishes to dispatch some input through different functions and then marry the results for disposition by another function (if this sounds like neural nets or circuits, that's because those systems do just that). The usual way of going about this work is for the programmer to shepherd the data as it flows from function to function. However, the Arrow protocol provides tools to automate this shepherding. To provide a specific example of the above described problem, we will use problem 54 from Project Euler to illustrate: which hand of poker wins (with the problem statement listing the rules of what makes a hand of poker and the ranking of hands)?

To see which hand wins, first the hands must be classified to their type: high card, pair, two pairs, three of a kind, straight, flush, full house, four of a kind, straight flush and royal flush. We will concentrate on hands that are straights, flushes, straight flushes and royal flushes.²

Given a hand is a list of cards of the following type ...

data Face =  Jack | Queen | King | Ace deriving (Eq, Ord, Enum)
data N = Two | Three | Four | Five | Six | Seven | Eight
         | Nine | Ten deriving (Eq, Ord, Enum)
data Rank = N N | Face Face deriving (Eq, Ord)

data Suit = Diamonds | Clubs | Spades | Hearts deriving Eq

data Card = Card Rank Suit deriving Eq3

... and cards are typed as follows ...

data HighCard = High Rank deriving (Eq, Ord)

data Type = [...]
             | Straight HighCard
             | Flush HighCard Rank Rank Rank Rank
             [...]
             | StraightFlush HighCard
             | RoyalFlush deriving (Eq, Ord)

... and the cards are ranked in descending order, seeing if a hand is a straight is simply a check to see if all cards are a run:

run :: MonadPlus m ⇒ [Card] → m HighCard
run (Card rank _:cards) 
     = High rank |- descending (value rank) 
                               (map value cards)
     where descending _ [] = True
           descending x (card:t) = x - 1 ≡ card
                                   ∧ descending card t

... where the value returns the value (of the rank) of the card (Two ≡ 2, Three ≡ 3, ..., King ≡ 12, Ace ≡ 13), and the |- function [pron: "implied by"] converts a value to its MonadPlus equivalent based on the result of a predicate:

(|-) :: MonadPlus m ⇒ a → Bool → m a
x |- p | p         = return x
       | otherwise = mzero

A flush is a hand that has all cards of the same suit ...

sameSuit :: MonadPlus m ⇒ [Card] → m Suit
sameSuit (Card _ suit:cards) = suit |- all inSuit cards
    where inSuit (Card _ s) = s ≡ suit

... or in the mode of sameSuit a flush is a hand where every other card has the same suit as the first card.

So now we have functions that determine if a hand is a flush or if its a straight. Now, during the discussion, you may have been wondering at the return type of these functions. Why not simply return a truth value, as these are predicates on straights and flushes? If these functions simply tested only for straights and flushes (mutually-) exclusively, the return type of Bool is most appropriate, but we intent to use these tests for more than just that: we will be using these simple functions to build our tests for straight flushes and royal flushes, and their return types help in that eventuality.

The strength of the Arrow class comes into its own in the following development, as well.

First off, what are straight flushes and royal flushes, conceptually? A straight flush is a straight in the same suit with a discriminating high card (for, after all, 109876 beats 76543). A royal flush is a straight flush with an ace as the high card. Now it is clear that the return type of the test functions above need more information than what Bool conveys.

So, we need to process the hand through both run and sameSuit, obtaining positive results from both functions, and we need to retrieve the result from run either to ensure the hand is a royal flush (because the high card must be an ace) or to fix the value of the straight flush. The Arrow protocol has function, &&& [pron. "fan-out"] that splits an input and sends it off to two Arrow types for separate processing, so to determine a straight flush we start the test with ...

run &&& straight

... which gives the following results (with the Maybe type selected to represent the particular MonadPlus):

AKQJ10	(Just (Face Ace), Just (Suit Spades))
AKQJ10	(Just (Face Ace), Nothing)
AK762	(Nothing, Just (Suit Spades))
QQQ44	(Nothing, Nothing)

Now that we have those results (in the form of a tuple pair), we need simply to perform a logical-and over the different values to obtain a conjoined truth result and to retrieve the high card's value to determine the "blue-blooded"ness of the straight flush.

That solution gives us two problems to deal with:

1. I'm not aware of a logical-and operation for the MonadPlus types; but that doesn't matter because:


2. We're working with two different types of MonadPlus type values anyway.

So, I rolled my own conjunctive function, favoring the result of the run, given both tests resolve positively:

mand :: Monad m ⇒ m a → m b → m a
x `mand` y = y >> x >>= return

Given the above definition of mand and introducing the composition function of the Arrow protocol, >>>, we can now write the computation that determines a straight flush and returns its high card:

run &&& sameSuit >>> uncurry mand

In fact, this pattern: f &&& g >>> uncurry mand⁴ neatly captures the logic programming paradigm of goal-seeking via conjunction, so it deserves it's own apt abstraction:

conjoin :: Monad m ⇒ (a → m b) → (a → m c) → a → m b
conjoin f g = f &&& g >>> uncurry mand

So, now we have the tools available to discriminate a hand's type along the straight or royal flush -- the straight flush simply returns the type with the high card value ...

straightFlush :: [Card] → Maybe Type
straightFlush hand = (run `conjoin` sameSuit) hand >>=
                     return . StraightFlush

... and a royal flush is a straight flush with a guaranteed high ace:

royalFlush :: [Card] → Maybe Type
royalFlush hand = straightFlush hand >>= highAce
   where highAce kind
           = RoyalFlush |- kind ≡ StraightFlush (High (Face Ace))

Note the complementary rôles of conjoin and >>= [pron. bind]: conjoin marries two truth values (emphasizing the first), and >>= forwards a truth value for disposition. Due to the monadic nature of these functions, a false result (or failure) at any point in the computation aborts it, so these nondeterministic functions are very well-behaved: what is returned is either Just a straight flush or a royal flush if and only if every test is true along the way, or Nothing if even a single test fails.

In summary, this particular aspect of the Arrow protocol that captures the totality of functions and simplifies the control of data flow gives a particularly powerful and flexible set of tools to the user, combining this flexibility with (Arrow) composition and the existing Monad and MonadPlus facilities allows a programming style as simple, declarative and powerful as the logic-programming paradigm.

---

1	Further distancing Prolog procedures from Haskell functions, the outcome of a procedure is not an "output" but its validity, or truth value -- how very un-Haskell-y!
2	But seriously! A royal flush? How many of you have every drawn that hand? There should be some special rule for drawing a royal flush, like: you get a life-time supply of marzipan loaded into the trunk of your brand new Bentley parked at your vacation home in St. Croix.
3	Note that in poker there is no precedence of suits (unlike in other card games, like Contract Bridge), so Suit is not an Ord type. This means, that since the Card type contains a Suit value, it, too, is not ordered ... if it were, then the situation would arise where a high card hand of 109... would lose to a high card hand of 106... which is patently not within the rules of poker.
4	In fact, the pattern foo &&& bar >>> uncurry quux deserves and has its own article which very prettily describes and illustrates graphically what this pattern does.