Parsing Permutations

My favorite game is bridge. It’s an excellent test of cooperation and strategy. I’m in a discord chat devoted mostly to the game and folks often share interesting bridge hands with one another. I decided it would be fun to build a program that parsed a simply-formatted bridge hand and produced a plain text bridge diagram.

Here’s a defensive problem that Sir Hugo Drax faced at Blades, defending a contract of 7♣xx.

$ bridge-cli-exe <<< 't987 6543 - 76532 > akqj akqj ak kj9, r/r, imps, s6'
Vul: R/R   ♠T987
IMPs       ♥6543
           ♦
           ♣76532
Lead: ♠6    -----     ♠AKQJ
           |  N  |    ♥AKQJ
           |    E|    ♦AK
           |     |    ♣KJ9
            -----

I’d like to focus on an interesting problem I faced when parsing this input. I wanted the user to be able to enter several elements: the layout (the cards), the vulnerability, the type of scoring, and the opening lead, each separated by a comma. However, I wanted these elements to be provided in any order. Furthermore, some of these elements were required while others were optional.

To simply things and avoid a game most people know nothing about, let’s change the example. Suppose we’d like to parse the following input.

name: Drew, age: 39, note: likes bridge

We’ll assume that name and age are required, while the note is optional. We’ll parse our input into the following type.

data Person = Person
  { name :: String,
    age :: Int,
    note :: Maybe String
  }
  deriving (Show)

The twist, as stated above, is that we’d like to be able to parse the elements in any order. First, let’s build simple parsers for each of the elements. We’ll use megaparsec.

type Parser = Parsec Void Text

parseName :: Parser String
parseName =
  string "name:" *> space *> some letterChar

parseAge :: Parser Int
parseAge = do
  ageString <- string "age:" *> space *> some digitChar

  case readMaybe ageString of
    Just age -> pure age
    Nothing -> fail "invalid age"

parseNote :: Parser String
parseNote =
  string "note:" *> space *> some (alphaNumChar <|> char ' ')

We can use each of these parsers individually.

> runParser parseName "" "name: Drew"
Right "Drew"

> runParser parseAge "" "age: 39"
Right 39

> runParser parseNote "" "note: likes bridge"
Right "likes bridge"

> let errorResult = runParser parseName "" "foo"
> putStrLn $ fromLeft "" $ first errorBundlePretty errorResult
1:1:
  |
1 | foo
  | ^^^
unexpected "foo"
expecting "name:"

Before we worry about allowing arbitrary ordering, let’s build a parser for Person that assumes name first, then age, and finally an optional note.

sep :: Parser ()
sep = space *> "," *> space

parsePerson :: Parser Person
parsePerson = do
  name <- parseName
  age <- sep *> parseAge
  note <- optional (sep *> parseNote)

  pure $ Person {name, age, note}

Let’s try using it.

> runParser parsePerson "" "name: Drew, age: 39, note: likes bridge"
Right (Person {name = "Drew", age = 39, note = Just "likes bridge"})

> runParser parsePerson "" "name: Drew, age: 39"
Right (Person {name = "Drew", age = 39, note = Nothing})

But how can we combine these same parsers regardless of order? The answer lies in the much-too-generically-named parser-combinators library. This library provides a module called Control.Applicative.Permutations that provides exactly the API we want. Let’s look at the solution.

parsePersonPerm :: Parser Person
parsePersonPerm =
  intercalateEffect sep $
    Person
      <$> toPermutation parseName
      <*> toPermutation parseAge
      <*> toPermutationWithDefault Nothing (Just <$> parseNote)

> runParser parsePersonPerm "" "note: likes bridge, name: Drew, age: 39"
Right (Person {name = "Drew", age = 39, note = Just "likes bridge"})

> runParser parsePersonPerm "" "name: Drew, age: 39, note: likes bridge"
Right (Person {name = "Drew", age = 39, note = Just "likes bridge"})

> runParser parsePersonPerm "" "age: 39, name: Drew"
Right (Person {name = "Drew", age = 39, note = Nothing})

The toPermutation and toPermutationWithDefault functions let us turn required and optional Parsers into “permutation-flavored parsers”. We then use an applicative-style API to compose our permutation parsers and build a permutation parser for Person. Finally, we run our permutation parser via intercalateEffect. This allows us to pass a parser that should appear in-between each permutation parser, regardless of their order.

I hope you’ll be able to use this technique the next time you need to parse a group of arbitrarily-ordered elements.