haskell 检查应用同态属性(二叉树)时,QuickCheck返回“0测试”

bogh5gae  于 2023-01-21  发布在  其他
关注(0)|答案(1)|浏览(210)

我想检查同态Applicative定律是否适用于数据类型BinTree

  1. {-# LANGUAGE ScopedTypeVariables #-}
  2. {-# LANGUAGE AllowAmbiguousTypes #-}
  3. {-# LANGUAGE TypeApplications #-}
  4. {-# LANGUAGE ViewPatterns #-}
  5. module Laws where
  6. import Control.Applicative ((<$>), liftA3)
  7. import Data.Monoid
  8. import Test.QuickCheck
  9. import Test.QuickCheck.Function
  10. import Test.QuickCheck.Gen
  11. data BinTree a = Empty | Node a (BinTree a) (BinTree a) deriving (Show, Eq)
  12. instance Functor BinTree where
  13. fmap _ Empty = Empty
  14. fmap f (Node x hi hd) = Node (f x) (fmap f hi) (fmap f hd)
  15. instance Applicative BinTree where
  16. -- pure :: a -> BinTree a
  17. pure x = Node x (pure x) (pure x)
  18. -- <*> :: BinTree (a -> b) -> BinTree a -> BinTree b
  19. _ <*> Empty = Empty -- L1,
  20. Empty <*> t = Empty
  21. (Node f l r) <*> (Node x l' r') = Node (f x) (l <*> l') (r <*> r')
  22. instance (Arbitrary a) => Arbitrary (BinTree a) where
  23. arbitrary = oneof [return Empty, -- oneof :: [Gen a] -> Gen a
  24. liftA3 Node arbitrary arbitrary arbitrary]
  25. -- Identity
  26. apIdentityProp :: (Applicative f, Eq (f a)) => f a -> Bool
  27. apIdentityProp v = (pure id <*> v) == v
  28. apHomomorphismProp :: forall f a b. (Applicative f, Eq (f b)) => Fun a b -> a -> Bool
  29. apHomomorphismProp (apply -> g) x = (pure @f g <*> pure x) == pure (g x)
  30. main = quickCheck $ apHomomorphismProp @BinTree @Int @Int

但是,当我执行代码时,应用于applicative属性的quickCheck返回:
(0次测试)
我该如何解决这个问题?

wfauudbj

wfauudbj1#

很简单,您的pure实现生成了一棵无限树,<*>保留了树两边的无限大小,然后将生成的无限树与另一棵无限树进行比较,看是否相等。
很明显,它没有发现它们之间的任何差异......但是它也没有终止。所以QuickCheck实际上从来没有设法确认哪怕一个测试用例是正确的。
一种解决方法是不使用==,而是使用一个等式运算符,该运算符只检查有限深度内的等式,并假设在更深的深度内也是相等的(注意,它仍然是指数级开销,所以你甚至不能检查非常深的深度!)

相关问题