The Water Jug Problem in Hedgehog

A couple of weeks ago this blog post over at the Hypothesis blog caught my eye. I had heard of TLA+ before, but the simplicity of the linked solution surprised me.

And the Python solution was very nice too, I totally have to bring Hypothesis to the office someday.

Anyway, some days later that same week, @jystic announced the release of Hedgehog, a property based testing library, much like QuickCheck but with a more modern approach.

Look, I’d never used QuickCheck or property testing for a real project before, so I was kind of surprised when I recognized some of the advantages @jystic said his library had. Specifically:

  • No Arbitrary instances.
    • The amount of boilerplate needed to avoid orphan instances is tedious in general.
  • Showing the values and code where a property fails.
    • The first frictious moment I had when using QuickCheck was exactly because of this.

So it was set. Let’s try Hedgehog with the Water Jug problem.

The problem

This is better explained in the Hypothesis post, but let’s recapitulate: you have 2 water jugs that you can either fill or empty. One has 5 litter capacity and the other 3. You win by leaving 4 litters in the big one.

The code

I didn’t want many dependencies, so no state monads or funny folds. Just a good old finite state machine. The fsm function will take a state and a step, and return a new state.

We start by importing,

and then defining our type for the problem:

Those are all the different kinds of steps we’ll have.

We will also need state to keep track of how much water our jugs have,

which by the way start out empty:

Now, let’s define what each step does:

That was easy. Let’s also define a function that executes a list of steps from the initial state:

Finally, the Hedgehog bits. We want to say: give me a random list of steps that has length between 0 and 20. We do it like so:

Also we define our property, which we want to see proven false,

also setting the TestLimit to 5000, so it doesn’t give up too early.

The solution

We can load this file using stack ghci --package=hedgehog-0.1, after adding hedgehog and any other missing deps to the global stack project (that is ~/.stack/global-project/stack.yaml). Finally, we get:

Isn’t that pretty? It even has colors on my terminal.

Also, the solution is exactly the same the Hypothesis post had! (I saw other solutions, some even not optimal, but this one was the most common).

I think I’m gonna like Hedgehog.

In the meantime, I’ll see about implementing the generic solution some day.