4
votes

Here's a simple function. It takes an input Int and returns a (possibly empty) list of (Int, Int) pairs, where the input Int is the sum of the cubed elements of any of the pairs.

cubeDecomposition :: Int -> [(Int, Int)]
cubeDecomposition n = [(x, y) | x <- [1..m], y <- [x..m], x^3 + y^3 == n] 
  where m = truncate $ fromIntegral n ** (1/3)

-- cubeDecomposition 1729
-- [(1,12),(9,10)]

I want to test the property that the above is true; if I cube each element and sum any of the return tuples, then I get my input back:

import Control.Arrow 

cubedElementsSumToN :: Int -> Bool
cubedElementsSumToN n = all (== n) d
    where d = map (uncurry (+) . ((^3) *** (^3))) (cubeDecomposition n)

For runtime considerations, I'd like to limit the input Ints to a certain size when testing this with QuickCheck. I can define an appropriate type and Arbitrary instance:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Test.QuickCheck

newtype SmallInt = SmallInt Int
    deriving (Show, Eq, Enum, Ord, Num, Real, Integral)

instance Arbitrary SmallInt where
    arbitrary = fmap SmallInt (choose (-10000000, 10000000))

And then I guess I have to define versions of the function and property that use SmallInt rather than Int:

cubeDecompositionQC :: SmallInt -> [(SmallInt, SmallInt)]
cubeDecompositionQC n = [(x, y) | x <- [1..m], y <- [x..m], x^3 + y^3 == n] 
  where m = truncate $ fromIntegral n ** (1/3)

cubedElementsSumToN' :: SmallInt -> Bool
cubedElementsSumToN' n = all (== n) d
    where d = map (uncurry (+) . ((^3) *** (^3))) (cubeDecompositionQC n)

-- cubeDecompositionQC 1729
-- [(SmallInt 1,SmallInt 12),(SmallInt 9,SmallInt 10)]

This works fine, and the standard 100 tests pass as expected. But it seems unnecessary to define a new type, instance, and function when all I really need is a custom generator. So I tried this:

smallInts :: Gen Int
smallInts = choose (-10000000, 10000000)

cubedElementsSumToN'' :: Int -> Property
cubedElementsSumToN'' n = forAll smallInts $ \m -> all (== n) (d m)
    where d =   map (uncurry (+) . ((^3) *** (^3)))
              . cubeDecomposition

Now, the first few times I ran this, everything worked fine, and all tests pass. But on subsequent runs I observed failures. Bumping up the test size reliably finds one:

*** Failed! Falsifiable (after 674 tests and 1 shrink):  
0
8205379

I'm a bit confused here due to the presence of two shrunken inputs - 0 and 8205379 - returned from QuickCheck, where I would intuitively expect one. Also, those inputs work as predicted (on my show-able property, at least):

*Main> cubedElementsSumToN 0
True
*Main> cubedElementsSumToN 8205379
True

So it seems like obviously there's a problem in the property that uses the custom Gen I defined.

What have I done wrong?

1
It seems obvious to me now that there's no reason n and m should be equal, as I've required them to be in cubedElementsSumToN''. So, the property is turning out False whenever it's fed an element that yields a nonempty list. I'll probably answer this myself in a few minutes.jtobin
You don't need new versions of your functions to use with the newtype wrapper. Instead, just pattern match on it to get at the underlying Int. For example, you can write cubedElementsSumToN' (SmallInt n) = ... instead of using forAll.hammar

1 Answers

3
votes

I quickly realized that the property as I've written it is obviously incorrect. Here's the proper way to do it, using the original cubedElementsSumToN property:

quickCheck (forAll smallInts cubedElementsSumToN)

which reads quite naturally.