Recognizing lists

Published on

You are given the following Haskell data type:

Your task is to write a function

that would accept a list iff it contains exactly three elements, of which:

  1. one is an A with a value between 3 and 7
  2. one is an A with an even value
  3. one is a B with a value ending in .hs

The A elements mentioned in conditions (1) and (2) have to be distinct, so [A 4, A 17, B "Prelude.hs"] should not be accepted, even though A 4 satisfies both (1) and (2).

This problem often arises in blackbox testing. You do something to a system; you wait for some time while gathering all events that the system generates. Then you want to check that the system generated all the events it had to generate, and no extra ones. However, the order of events may be non-deterministic. If the system concurrently makes a web request, updates a database and sends a message to a message bus, the order in which these events will be observed by your test suite is arbitrary.

A similar problem arises in input validation.


We want to solve this problem in a general and scalable way. What would an interface to such solution look like? There are two principal options.

One is a simple function

that takes individual predicates and combines them into a recognizer.

Another is to split the process into the build and use phases by the means of an intermediate data type:

In this approach, you convert individual recognizers to monoidal values, combine those values and extract the result.

Semantically, the two are equivalent: if you have one of these interfaces available, you can implement the other one. In a way, this is a consequence of lists being the free monoid, but writing this down explicitly is a good exercise nevertheless.

The advantages of a build-use interface are:

  1. When the cost of the build phase is non-trivial, it can be amortized over multiple uses and/or incremental builds. (This won’t be the case here.)
  2. The use of a specialized type is generally good for the type system hygiene.

We’ll start with the build-use interface because I find it more instructive.

The Parser

To build the monoidal parser, we’ll use the action-permutations library. You may remember it from the article on JSON parsing.

StateT [t] Maybe a is the familiar type of parser combinators, [t] -> Maybe (a, [t]), that return the left-over input. We wrap it in Perms to achieve the order independence, and then newtype it to convert its Applicative instance to a Monoid one:

The build and use functions are straightforward:


First, let’s express our conditions in Haskell code.

Combine them together:

(we could replace mconcat . map toParser with foldMap toParser from Data.Foldable)

Now try it out: