Вот простая функция. Он принимает вход Int
и возвращает (возможно, пустой) список (Int, Int)
пар, где вход Int
- это сумма элементов в кубе любой из пар.
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)]
Я хочу проверить свойство, что вышесказанное верно; если я кубизирую каждый элемент и суммирую любой из возвращаемых кортежей, я получаю свой ввод обратно:
import Control.Arrow
cubedElementsSumToN :: Int -> Bool
cubedElementsSumToN n = all (== n) d
where d = map (uncurry (+) . ((^3) *** (^3))) (cubeDecomposition n)
По соображениям времени выполнения я хотел бы ограничить ввод Int
до определенного размера при тестировании с помощью QuickCheck. Я могу определить подходящий тип и Arbitrary
экземпляр:
{-# 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))
И затем, я думаю, мне нужно определить версии функции и свойства, которые используют SmallInt
, а не 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)]
Это работает нормально, и стандартные 100 тестов проходят, как и ожидалось. Но кажется излишним определять новый тип, экземпляр и функцию, когда все, что мне действительно нужно, - это настраиваемый генератор. Итак, я попробовал это:
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
Итак, первые несколько раз, когда я запускал это, все работало нормально, и все тесты прошли. Но при последующих запусках я наблюдал сбои. Увеличение размера теста надежно обнаружит:
*** Failed! Falsifiable (after 674 tests and 1 shrink):
0
8205379
Я немного сбит с толку из-за присутствия двух сжатых входных данных - 0 и 8205379 - возвращенных из QuickCheck, где я интуитивно ожидал одного. Кроме того, эти входные данные работают, как и предполагалось (по крайней мере, на моем показываемом свойстве):
*Main> cubedElementsSumToN 0
True
*Main> cubedElementsSumToN 8205379
True
Таким образом, очевидно, что проблема связана с тем свойством, которое использует определенный мной пользовательский Gen
.
Что я сделал не так?
n
иm
должны быть равны, поскольку я требовал, чтобы они были вcubedElementsSumToN''
. Таким образом, свойство становитсяFalse
всякий раз, когда ему передается элемент, который дает непустой список. Я, наверное, сам отвечу на этот вопрос через несколько минут. - person jtobin   schedule 13.11.2012newtype
. Вместо этого просто сопоставьте его с шаблоном, чтобы найти лежащий в основеInt
. Например, вы можете написатьcubedElementsSumToN' (SmallInt n) = ...
вместоforAll
. - person hammar   schedule 13.11.2012