Pattern guards for a protocol by Mark Seemann

A Haskell example.

Recently, I was doing a Haskell project implementing a cellular automaton according to predefined rules. Specifically, the story was one of Galápagos finches meeting and deciding whether or not to groom each other for parasites, effectively playing out a round of prisoner's dilemma.

Each finch is equipped with a particular strategy for repeated play. This strategy is implemented in a custom domain-specific language that enables each finch to remember past actions of other finches, and make decisions based on this memory.

Meeting protocol #

An evaluator runs over the code that implements each strategy, returning a free monad that embeds the possible actions a finch may take when meeting another finch.

The possible actions are defined by this sum type:

data EvalOp a
  = ErrorOp Error
  | MeetOp (FinchID -> a)
  | GroomOp (Bool -> a)
  | IgnoreOp (Bool -> a)

When two finches a and b meet, they must interact according to a protocol.

• Evaluate the strategy of the finch a up to the next effect, which must be a MeetOp.
• Invoke the continuation of the MeetOp with the finchID of finch b.
• Evaluate the strategy up to next effect, which must be GroomOp or IgnoreOp. This decides the behaviour of finch a during this meeting.
• Similarly, determine the behaviour of finch b, using the finchID of finch a.
• For each finch, invoke the continuation of the GroomOp or IgnoreOp with the behaviour of the other finch (True for grooming, False for ignoring), yielding two new Strategys (sic).
• The resulting Strategys (sic) are then stored in the Finch objects for the next meeting of the finches.

If at any step a strategy does not produce one of the expected effects (or no effect at all), then the finch has behaved illegally. For example, if in step 1 the first effect is a GroomOp, then this is illegal.

This sounds rather complicated, and I was concerned that even though I could pattern-match against the EvalOp cases, I'd end up with duplicated and deeply indented code.

Normal pattern matching #

Worrying about duplication, I tried to see if I could isolate each finch's 'handshake' as a separate function. I was still concerned that using normal pattern matching would cause too much indentation, but subsequent experimentation shows that in this case, it's not really that bad.

Ultimately, I went with pattern guards, but I think that it may be more helpful to lead with an example of what the code would look like using plain vanilla pattern matching.

tryRun :: EvalM a -> FinchID -> Maybe (Bool -> EvalM a, Bool)
tryRun (Free (MeetOp nextAfterMeet)) other =
  case nextAfterMeet other of
    (Free (GroomOp nextAfterGroom)) -> Just (nextAfterGroom, True)
    (Free (IgnoreOp nextAfterIgnore)) -> Just (nextAfterIgnore, False)
    _ -> Nothing
tryRun _ _ = Nothing

Now that I write this article, I realize that I should have named the function handshake, but hindsight is twenty-twenty. In the moment, I went with tryRun, using the try prefix to indicate that this operation may fail, as also indicated by the Maybe return type. That naming convention is probably more idiomatic in F#, but I digress.

As announced, that's not half as bad as I had originally feared. There's the beginning of arrow code, but I suppose you could also say that of any use of if/then/else. Imagine, however, that the protocol involved a few more steps, and you'd have something quite ugly at hand.

Another slight imperfection is the repetition of returning Nothing. Again, this code would not keep me up at night, but it just so happened that I originally thought that it would be worse, so I immediately cast about for alternatives.

Using pattern guards #

Originally, I thought that perhaps view patterns would be suitable, but while looking around, I came across pattern guards and thought: What's that?

This language feature has been around since 2010, but it's new to me. It's a good fit for the problem at hand, and that's how I actually wrote the tryRun function:

tryRun :: EvalM a -> FinchID -> Maybe (Bool -> EvalM a, Bool)
tryRun strategy other
  | (Free (MeetOp nextAfterMeet)) <- strategy
  , (Free (GroomOp nextAfterGroom)) <- nextAfterMeet other
  = Just (nextAfterGroom, True)
tryRun strategy other
  | (Free (MeetOp nextAfterMeet)) <- strategy
  , (Free (IgnoreOp nextAfterIgnore)) <- nextAfterMeet other
  = Just (nextAfterIgnore, False)
tryRun _ _ = Nothing

Now that I have the opportunity to compare the two alternatives, it's not clear that one is better than the other. You may even prefer the first, normal version.

The version using pattern guards has more lines of code, and code duplication in the repetition of the | (Free (MeetOp nextAfterMeet)) <- strategy pattern. On the other hand, we get rid of the duplicated Nothing return value. What is perhaps more interesting is that had the handshake protocol involved more steps, the pattern-guards version would remain flat, whereas the other version would require indentation.

To be honest, now that I write this article, the example has lost some of its initial lustre. Still, I learned about a Haskell language feature that I didn't know about, and thought I'd share the example.

Conclusion #

Most mature programming languages have so many features that a programmer may use a language for years, and still be unaware of useful alternatives. Haskell is the oldest language I use, and although I've programmed in it for a decade, I still learn new things.

In this article, you saw a simple example of using pattern guards. Perhaps you will find this language feature useful in your own code. Perhaps you already use it.

• ← Previous
• Archive
• Next →