QuickCheck property: Uncategorised bill by Mark Seemann
Initial API definition and a simple property.
This article is one of a series on finding properties for a budgeting kata. I expect you to have read the previous articles in the series.
In this article we get started by adding a first sketch of data structures and an initial, simple property.
The code is available on GitHub, in the commit 1f7aceb.
Budget type #
My intent with the entire exercise is to follow a variation of test-driven development (TDD) that uses QuickCheck properties rather than static examples. Even so, Haskell is such a strongly typed language that I often start with a bit of type-driven development, sketching out how data types and functions may look. I did that here as well, starting with the budget.
data Budget a = Budget { totalLimit :: Int , categoryLimits :: Map a Int } deriving (Show, Eq)
As I noted in the introduction article, this was my third attempt. Two previous attempts had taught me that it might be useful to be able to define the set of values from which category identifiers are picked by QuickCheck. Hillel Wayne's examples use strings, which seems quite natural. When, however, QuickCheck generates String values, it picks from an infinite set of values: "a", "fê, 3_\g§ü:, and unprintable things. The probability of generating two identical values in the same property is small, but sometimes, it turns out, that's exactly what we would like.
There are many ways you can tell QuickCheck to generate values by picking from a small set, such as the elements combinator. The problem with ad-hoc use of such a combinator, however, is that it doesn't support shrinking, and it turns out that for this particular kata, shrinking is indispensable.
As I also mentioned in the introduction, while being mature, QuickCheck also comes with some baggage. Perhaps the most prominent drawback is its lack of automatic shrinking. In order to support shrinking, you must define an Arbitrary instance, and this again means introducing a type.
As so many other Haskell libraries, QuickCheck relies quite heavily on types. If you need to define a type in order to control how values are generated, it might be easier to make a data structure polymorphic and then pick a useful type on a property-by-property basis. So with that in mind (and two botched attempts already behind me), I made Budget parametric in its category identifier type: The categoryLimits element is a map from some identifier of the type a to an Int. Since a could be String, this design still supports the specification.
This is a concession to better support testing, and ultimately, I'm not entirely sure that it helped that much. Ironically, there's some evidence that it might have been at least as useful to parametrize the limit itself, since Int also allows (at least) millions of distinct values.
Item and bill types #
In order to compare budgets to bills, we must also make each item in a bill polymorphic:
{-While the original problem specification has count and categories optional, we may deal with this in a hypothetical parsing step, setting count to 1 if missing, and likewise setting categories to the empty set if missing.-} data Item a = Item { itemCost :: Int , itemCount :: Int , itemCategories :: Set a } deriving (Show, Eq)
As is suggested by the comment, I didn't really feel like dealing with defining count and categories as optional. Both have natural default values, as the specification also defines. I did, in fact, for a time toy with making Item a Monoid instance, but while a lawful definition exists, it doesn't fit the business rules. You can't meaningfully combine two items with different category sets. Doing so would change the outcome of the decision algorithm.
A bill, then, is just a type alias for a list of items:
type Bill a = [Item a]
Those are all the data structures required for the kata.
Functions #
In addition to Budget and Item we also need at least a canAfford function. It turns out that a few auxiliary functions are also useful when writing the QuickCheck properties. For the first property, only this billCost function is in use, but later commits add a few more:
billCost :: (Foldable t, Functor t) => t (Item a) -> Int billCost bill = sum $ fmap (liftA2 (*) itemCost itemCount) bill
As I've previously given out, I often don't add a type declaration to functions, and if you consult the Git repository, you will also see that billCost is unannotated. I only added the type annotation in post-production, in order to make reading this article a iota easier.
I did, however, add a type declaration to canAfford, because at first, in true TDD style, I left it unimplemented, and I needed to have enough of a type to prevent QuickCheck from complaining that it couldn't decide on which instance to pick. Or something.
canAfford :: Budget a -> Bill a -> Bool
The most important part of this declaration is that the type parameters for Budget and Bill must match.
An Arbitrary instance for Item #
To define properties, we need test data generators. As I mentioned in the introduction article, property-based testing involves a degree of boilerplate code. In order to avoid orphan instances, you can define a test-specific AnyItem newtype.
newtype AnyItem a = AnyItem { getItem :: Item a } deriving (Show, Eq)
You can now give AnyItem an Arbitrary instance.
instance (Arbitrary a, Ord a) => Arbitrary (AnyItem a) where arbitrary = do Positive cost <- arbitrary Positive count <- arbitrary AnyItem . Item cost count <$> arbitrary shrink (AnyItem (Item cost count categories)) = [ AnyItem $ Item cost' count' categories' | (Positive cost', Positive count', categories') <- shrink (Positive cost, Positive count, categories) ]
I often dispense with defining the shrink method, but for the properties we'll see before we are done, shrinking turns out to be quite useful. Just like the arbitrary method composes Arbitrary instances for the three constituent values of Item, the shrink method uses the shrinkers associated with Positive Int and Set a, respectively. The only marginally complicated part is the wrapping and unwrapping of Positive, making sure that both itemCost and itemCount stay greater than nought.
Property #
The first property that came immediately to mind was to consider the total limit. Regardless of all other rules, if the total cost of the bill exceeds the total budget, then the bill is not affordable. There are many ways you could express such a property, but I chose to do it like this:
testProperty "Uncategorized bill is only determined by its cost" $ \ (fmap getItem -> bill :: Bill String) (NonNegative lim) -> let budget = Budget lim (mempty :: Map String Int) bill' = (\i -> i { itemCategories = mempty }) <$> bill actual = canAfford budget bill' expected = billCost bill' <= lim in counterexample ("Budget: " ++ show budget) $ counterexample ("Bill: " ++ show bill') $ expected === actual
As I usually do, I wrote this property (and the ones that follow) as inlined values in a test list, similarly to how I do it with example-based tests. I also used view patterns to pull the bill out of the list of AnyItem values I've asked it to generate. The entire type for the lambda expression (everything after $ \ ) is
[AnyItem String] -> NonNegative Int -> Property
That is, the property takes as input a list of AnyItem String and a NonNegative Int, and then defines the property as the let-in expression. Thanks to the magic of pattern matching and view patterns, bill is a Bill String and lim an Int.
The reason I had to annotate bill is because otherwise the entire property is parametrically polymorphic, and then QuickCheck doesn't know what to do.
Now that I'm writing this article, I think that I could have defined an even stronger property by just leaving bill be, instead of setting all itemCategories to the empty set. That would also have made the code simpler.
A stronger reservation I have against this property is that it temporarily defines the implementation as the expected value.
Implementation #
Not surprisingly, the simplest thing that passes all tests is this:
canAfford :: Budget a -> Bill a -> Bool canAfford budget bill = billCost bill <= totalLimit budget
Too close to the property for comfort.
Alternative properties #
When I made my first attempt at the kata, I approached the first property in a more traditional example-driven way. I first wrote one test to demonstrate that an affordable bill without categories is affordable:
testProperty "Affordable uncategorized bill" $ do UncategorizedBill bill <- arbitrary let cost = billCost bill NonNegative surplus <- arbitrary categories <- listOf (CategoryBudget <$> arbitrary <*> arbitrary) let budget = Budget (cost + surplus) categories let actual = canAfford budget bill let errMsg = "budget: " ++ show budget ++ ", bill: " ++ show bill return $ counterexample errMsg actual
This property makes use of slightly different data definitions. You can see details in the first-attempt branch if you want.
The point is that this property explicitly constructs a budget such that the bill is always affordable. It therefore asserts that actual is True.
The corresponding implementation is, of course,
canAfford :: Budget -> Bill -> Bool canAfford _ _ = True
Another property then explicitly checks the other partition, which is when a bill without categories is always unaffordable.
testProperty "Unaffordable uncategorized bill" $ do UncategorizedBill bill <- arbitrary let cost = billCost bill Positive deficit <- arbitrary categories <- listOf (CategoryBudget <$> arbitrary <*> arbitrary) let budget = Budget (cost - deficit) categories let actual = canAfford budget bill let errMsg = "budget: " ++ show budget ++ ", bill: " ++ show bill return $ counterexample errMsg $ not actual
This property explicitly constructs a budget so that it always makes the bill unaffordable. It then asserts not actual; that is, that actual is False.
Together with the previous property, this then leads to the implementation
canAfford :: Budget -> Bill -> Bool canAfford budget bill = billCost bill <= totalLimit budget
This test design avoids duplicating implementation code as test code, so why didn't I stay that course?
What I don't like about this approach is the test duplication. Notice how similar the two tests are. Some people might point out that tests may be DAMP, but as I've already been over, DRY and DAMP should be treated as an intersection rather than a dichotomy.
Even so, I can live with a small degree of duplication if it serves a purpose. After all, if we follow the rule of three, we haven't even introduced a triplicate yet.
My problem with this duplication is rather that it seems to buy us nothing. Together, those two tests exhibits just as much 'knowledge' about the implementation than the single "Uncategorized bill is only determined by its cost" property does.
The "Affordable uncategorized bill" property knows (or rather, specifies) that it can go right to the limit of billCost bill. It can add 0, or anything greater than 0, to billCost bill, and actual will remain True.
Likewise, "Unaffordable uncategorized bill" knows (or, again, specifies) that it must subtract at least 1 from billCost bill for actual to become False.
Let lim = cost + surplus or lim = cost - deficit, respectively. You now have two tests that effectively say
if billCost bill <= lim then True else False
which is just a long-winded way of saying
billCost bill <= lim
which hlint will also tell you.
So my reasoning is that the two alternative properties are effectively equivalent to the single "Uncategorized bill is only determined by its cost" property.
I'm still not blissful about duplicating production code as test code, but I take solace in the prediction that the implementation of canAfford is not going to stay that simple.
Conclusion #
In this article, you saw data definitions and an initial property to get started on the problem. The property is one of the simplest we are going to cover, but on the other hand, now that we have covered the data structures and the APIs, these will not change in any significant way. The next articles are more devoted to the properties being introduced.
Next: QuickCheck property: Forced category limit applies.
