quick and dirty port of http://hypothesis.works/articles/testing-optimizers-with-hypothesis/ to quickcheck

knapsack.hs

import Data.List
import Data.Ord
import Data.Bifunctor
import Test.QuickCheck

type Item = (Int, Weight)
type Weight = Int

knapsack :: Weight -> [Item] -> [Item] 
knapsack w xs = last $ filter ((<= w) . totalWeight) $ inits ordered
  where 
    ordered = sortOn (Down . ((,) <$> ratio <*> snd)) xs
    ratio (value, weight) = fromIntegral value / fromIntegral weight

totalWeight = sum . map snd
totalValue = sum . map fst

prop_duplicating_not_worse (Positive w) (NonEmpty xs') = do
  let xs = map (bimap getPositive getPositive) xs'
  x <- elements xs
  let v1 = totalValue (knapsack w xs)
  let v2 = totalValue (knapsack w (x:xs))
  return $ counterexample (show x)
         $ counterexample (show v1)
         $ counterexample (show v2)
         $ v1 <= v2

prop_subsequence_not_better (Positive w) (NonEmpty xs') = do
  let xs = map (bimap getPositive getPositive) xs'
  ys <- sublistOf xs
  let v1 = totalValue (knapsack w xs)
  let v2 = totalValue (knapsack w ys)
  return $ counterexample (show ys)
         $ counterexample (show v1)
         $ counterexample (show v2)
         $ v1 >= v2

props = [prop_duplicating_not_worse, prop_subsequence_not_better]

main = mapM_ quickCheck props