Aidan Delaney’s weblog

I always write semi-automated tests, whatever language I’m using. In Haskell my preferred framework is QuickCheck, which goes beyond what an XUnit framework is capable of. I come to QuickCheck as a convert from the old religion of Object Oriented programming. However much I’ve adopted functional practices I find myself, in the darkest of times, falling back on idioms from a past life. Recently I’ve been testing code that looks like the following:

data Squad = Squad { players :: Set Char,
team :: Set Char }

So what I’ve got is some type which is composed of a set and some other set which is a subset of the original. I hope the Squad metaphor is reasonable. In many sports you’ll have a panel of players, called the squad, and then for any given game you’ll have a team which is a subset of the players in your squad. To simplify this problem, each player is identified by a single character rather than a name. Now, we don’t have a dependent type system here. Just plain old Haskell. So the constraint that “team is a subset of players” is not enforced by the type system.

Now I want to tell Haskell to create Arbitrary instances of Squad.

randSubset :: Ord a => Set a -> Gen (Set a)
randSubset xs = do {
mask <- vectorOf (Set.size xs) arbitrary;
return (Set.fromList [ e | (e,True) <- zip (Set.toList xs) mask ]) }

instance Arbitrary Squad where
arbitrary = do {
players <- listOf1 (arbitrary :: Gen Char);
team <- randSubset (Set.fromList players);
return (Squad (Set.fromList players) team))}

The smarts here is in randSubset, but listOf1 ensures that there’s at least one player in our squad. I was struggling when playing around with a random number generator, to try and pull out random elements from a Set. Such thinking is a false idol. With some guidance from the only person on the planet to be 90% Real Jedi I realised you can just use the common generator combinators as provided by QuickCheck.

So the fragment

do {
mask <- vectorOf (Set.size xs) arbitrary;
return (Set.fromList [ e | (e,True) <- zip (Set.toList xs) mask ])}

asks for an arbitrary list of boolean values where the list is the same length as the size of the input Set. Then where the ith element of the list is true, the ith element of the set is considered to be in the subset, or omitted otherwise. It’s a nice idiom, useful anywhere you’re playing with sets that aren’t quite arbitrary themselves, but are constrained to be a subset of another.

This entry was posted on Tuesday, May 17th, 2011 at 3:48 pm and is filed under General, Haskell, Teaching. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.