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

^{1}It's this total control of the procedure's environment that makes writing, e.g., aspects for Prolog a trivial exercise.

With

`Arrow`s, 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.

^{2}

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

dataFace=Jack|Queen|King|Acederiving (Eq,Ord,Enum)dataN=Two|Three|Four|Five|Six|Seven|Eight

|Nine|Tenderiving (Eq,Ord,Enum)dataRank=N N|Face Facederiving (Eq,Ord)dataSuit=Diamonds|Clubs|Spades|HeartsderivingEqdataCard=Card Rank SuitderivingEq^{3}

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

dataHighCard=High Rankderiving (Eq,Ord)dataType=[...]

|Straight HighCard

|Flush HighCard Rank Rank Rank Rank

[...]

|StraightFlush HighCard

|RoyalFlushderiving (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 ::MonadPlusm ⇒ [Card] → mHighCard

run (Cardrank _:cards)

=Highrank |- descending (value rank)

(mapvalue cards)

wheredescending _ [] =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:

(|-) ::MonadPlusm ⇒ a →Bool→ m a

x |- p | p =returnx

|otherwise= mzero

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

sameSuit ::MonadPlusm ⇒ [Card] → mSuit

sameSuit (Card_ suit:cards) = suit |-allinSuit cards

whereinSuit (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 | `(` |

AKQJ10 | `(` |

AK762 | `(` |

QQQ44 | `(` |

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:

- I'm not aware of a logical-and operation for the
`MonadPlus`types; but that doesn't matter because: - 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 ::Monadm ⇒ 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

^{4}neatly captures the logic programming paradigm of goal-seeking via conjunction, so it deserves it's own apt abstraction:

conjoin ::Monadm ⇒ (a → m b) → (a → m c) → a → m b

conjoin f g = f &&& g >>>uncurrymand

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

wherehighAce 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 >>> ` deserves and has its own article which very prettily describes and illustrates graphically what this pattern does. |

## 3 comments:

Does Haskell understand the → arrow in a source file? Or is that just for code display purposes?

@max, about your → question.

Hm, not sure. I do know that Haskell

doesunderstand (a -> b) perfectly well, but I'm not sure if my Haskell system, or any Haskell system, understands that (a → b) as the equivalent construct.ifyour system doesn't understand (a → b)thenuse (a -> b) insteadelsedo whichever you'd like{-# LANGUAGE UnicodeSyntax #-}

Post a Comment