Wednesday, March 30, 2011

Playing Around with QuickCheck

So I saw the new parallel monad and I wanted to give it a spin.  A simple package that factors numbers seemed to be just the thing. It parallelizes nicely. More about that in the companion post -- this post is about my first steps with QuickCheck  I wanted to test this factor code:
factors :: Integer -> [Integer]
factors x
  | x < 2 = [1] | otherwise = sort $ factors' x 2 [1,x]

factors' :: Integer -> Integer -> [Integer] -> [Integer]
factors' x y zs
  | fromInteger y > (sqrt $ fromInteger x) = zs
  | x `mod` y == 0 && y*y /= x =
                 factors' x (y+1) (y : x `div` y : zs)
  | x `mod` y == 0 && y*y == x =
                 factors' x (y+1) (y : zs)
  | otherwise = factors' x (y+1) zs
The first lesson I learned along the way is that the result of a QuickCheck test is a Property, not a Bool; just a heads-up for other newbies. BTW, one of my favorite things about Real World Haskell is that it gives more than a passing thought to stuff like Cabal and QuickCheck. 

The test machinery was rather more involved than the code itself.  First I had to put together a list of prime numbers, then I could write code that would test factorization over primes and over products of two primes. 
sieve :: Integral a => [a] -> [a]
sieve (p:xs) = p : sieve [x | x <- xs, 0 /= x `mod` p] primes :: Integral a => [a]
primes = sieve [2..]

primesInteger = primes :: [Integer]
getPrime x = primesInteger !! (x `mod` 100)

buildAssocList :: Integral a => [a] -> [a] -> [a]
buildAssocList xs ys = sort $ nub [a*b|a <- xs,b <- ys]

propAssoc x y = x > 0 ==> y > 0 ==>
  factors (x*y) == buildAssocList (factors x)
                                  (factors y)

propPrime x = x > 0 ==>
  let prime = getPrime x in factors prime == [1,prime]

propSimple x y = x > 0 ==> y > 0 ==>
  let primeX = getPrime x
      primeY = getPrime y
  in (factors $ primeX * primeY) ==
          (sort $ nub [1,primeX,primeY,primeX*primeY])
This is all straightforward.  Getting the final piece of test code took rather more time, but it refactored down to
testDepth = 8          -- actually N-1

check :: Integer -> [Integer] -> Integer -> [Integer] -> Bool
check 0 _ _ _ = True
check y xs n ns =
  let p = getPrime (1 + abs(fromIntegral $ head xs))
      ps = factors p
      p_list = build_assoc_list ns ps
  in factors (n*p) == p_list &&
     check (y-1) (tail xs) (n*p) (p_list)

prop_complex z zs = z > 0 &&
     (fromIntegral $ length zs) >=
         (fromIntegral (z `mod` testDepth))   ==>
  check (z `mod` testDepth) zs 1 [1]
This works, though I've got to say that the prop_complex check on the length of zs is not exactly elegant.   I'd love to hear comments on how to make it more idiomatic Haskell (and that applies to all the code).

No comments:

Post a Comment