QuickCheck property: Forced category limit applies by Mark Seemann
A continued programming exercise using TDD with PBT.
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.
The first property specified that a bill doesn't exceed the total budget, and that's all there is to say about the total budget. All the complication lies in how category budgets are handled. In this article, we get started on that work, which will continue for another seven properties.
The code is available on GitHub, in the commit aefa192.
Per-category bounds #
My plan for this exercise was always to attempt it with test-driven development (TDD) using properties rather than singular examples. When doing TDD, I usually keep the transformation priority premise in mind: When given a choice between test cases, pick the one you predict will provoke the smallest change to the System Under Test.
Here, a good candidate may be a property specifying that for items that have no choice in which category to charge, the total cost of that category must not exceed the category limit. That description is dense, so let's unpack it. Each item in a bill comes with a set of categories. This set may be empty, a singleton, or contain multiple categories.
ghci> Item 1 1 Set.empty
Item {itemCost = 1, itemCount = 1, itemCategories = fromList []}
ghci> Item 1 1 $ Set.singleton "a"
Item {itemCost = 1, itemCount = 1, itemCategories = fromList ["a"]}
ghci> Item 1 1 $ Set.fromList ["a", "d"]
Item {itemCost = 1, itemCount = 1, itemCategories = fromList ["a","d"]}
Some or all of those categories may be 'unforced' or irrelevant categories. What matters is which categories are associated with limits in the budget. If the budget only comes with a limit for category "a", the first of the above examples has no category limit, and the two other items are uniquely constrained by the "a" limit. For the third example item, the "d" category is irrelevant, since there's no budget limit for "d".
Another way to put it: If the intersection between an item's categories and the budget category limits is a singleton, then the item is uniquely constrained by that category.
There could be more than a single item with the same intersection, but the sum of those items constitute the cost of that category, and (as long as the items are uniquely forced by a single category) that cost must not exceed the category limit.
Now that I write this explanation, I wonder whether I could have expressed a property like that, but here's the property that I actually wrote:
testProperty "Forced category limit applies" $ \ (fmap getItem . getNonEmpty -> bill :: Bill Char) (NonNegative catLim) -> Set.unions (itemCategories <$> bill) /= mempty ==> do cat <- elements $ Set.toList $ Set.unions (itemCategories <$> bill) -- Force the selected category by making it the only category for those -- items that have it. let bill' = (\i -> if Set.member cat (itemCategories i) then i { itemCategories = Set.singleton cat } else i) <$> bill budget = Budget (billCost bill') (Map.singleton cat catLim) actual = canAfford budget bill' expected = categoryCost cat bill' <= catLim return $ counterexample ("Budget: " ++ show budget) $ counterexample ("Bill: " ++ show bill') $ expected === actual
Like the previous property this one also uses view patterns to pull the bill out of a list of AnyItem values, but now this list is a NonEmptyList. Likewise, pattern matching on NonNegative makes catLim an Int. The entire type for the lambda expression (everything after $ \ ) is
NonEmptyList (AnyItem Char) -> NonNegative Int -> Property
Notice that I have now changed from Bill String to Bill Char. To be honest, I no longer remember why I did that, but it could be a remnant of an (uncommitted) attempt to constrain QuickCheck's choice of categories, so as to increase the chance that it would occasionally create a bill where a category would span more than a single item. Given that Char is actually a Unicode character with more than a million possible values, this was probably naive.
The property uses the implication operator ==> to make sure that the generated bill has at least one category on some item. It then picks one category from the set of all categories of the bill, and creates a modified bill' that replaces category sets with only that category for those items that originally included that category. For example, if cat is 'a' then
Item 1 1 $ Set.fromList ['a', 'd']
becomes
Item 1 1 $ Set.fromList ['a']
The property constructs a budget by setting a limit catLim only for the chosen category cat. Since catLim is any NonNegative number, this limit may or may not make the bill affordable. This limit, however, is the only deciding factor, since the budget is constructed with a total limit of billCost bill'; in other words, the total limit is always just permissive enough. Thus, the expected result is whether the categoryCost is less than or equal to catLim.
A questionable API #
I added the categoryCost function to the implementation code:
categoryCost cat = sum . fmap (liftA2 (*) itemCost itemCount) . filter (Set.member cat . itemCategories)
In retrospect, I'm not sure that this was a good idea, because one could argue that the cost of a category depends on how the final algorithm decides to distribute items among categories. For example, you could have a bill like this:
bill = [Item 2 1 $ Set.fromList ['a', 'c'], Item 2 1 $ Set.fromList ['b', 'c']]
and a budget like this:
budget = Budget 4 $ Map.fromList [('a', 2), ('b', 2), ('c', 1)]
A correct implementation of the decision algorithm would consider that bill affordable, because it can distribute the cost of the first item to the 'a' category, and the second item to the 'b' category. Effectively, the cost of category 'c' for that bill is nought. Even so, that's not what categoryCost answers:
ghci> categoryCost 'c' bill
4
In a sense, you could argue that this is correct, because categoryCost doesn't take the budget into account. Thus, it's rather an indication of the maximum cost of that category. Perhaps I should have named the function maxCategoryCost.
The simplest thing that works #
Given the two properties so far, the simplest thing I could think of that passes all test cases is this:
canAfford budget bill =
billCost bill <= totalLimit budget &&
all
(\(cat, lim) -> categoryCost cat bill <= lim)
(Map.toList $ categoryLimits budget)
It naively checks that for each budgeted category, the categoryCost must not exceed the the category limit. This is clearly incorrect, because it rejects, among many other examples, the bill and budget discussed above. More properties are needed.
Conclusion #
Attempting to do the budgeting exercise with TDD using QuickCheck properties, I added the first of many properties to describe the desired behaviour related to category limits. It specifies that if an item is unambiguously forced by a single category limit, then that limit must not be exceeded.
This property still feels a bit ad-hoc to me; as one of those 'examples on steroids' I've already discussed. Thus, I was keen to add something that sounded more like proper computer science.
Next: QuickCheck property: Monotonicity in items.
