我想检查同态Applicative
定律是否适用于数据类型BinTree
:
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ViewPatterns #-}
module Laws where
import Control.Applicative ((<$>), liftA3)
import Data.Monoid
import Test.QuickCheck
import Test.QuickCheck.Function
import Test.QuickCheck.Gen
data BinTree a = Empty | Node a (BinTree a) (BinTree a) deriving (Show, Eq)
instance Functor BinTree where
fmap _ Empty = Empty
fmap f (Node x hi hd) = Node (f x) (fmap f hi) (fmap f hd)
instance Applicative BinTree where
-- pure :: a -> BinTree a
pure x = Node x (pure x) (pure x)
-- <*> :: BinTree (a -> b) -> BinTree a -> BinTree b
_ <*> Empty = Empty -- L1,
Empty <*> t = Empty
(Node f l r) <*> (Node x l' r') = Node (f x) (l <*> l') (r <*> r')
instance (Arbitrary a) => Arbitrary (BinTree a) where
arbitrary = oneof [return Empty, -- oneof :: [Gen a] -> Gen a
liftA3 Node arbitrary arbitrary arbitrary]
-- Identity
apIdentityProp :: (Applicative f, Eq (f a)) => f a -> Bool
apIdentityProp v = (pure id <*> v) == v
apHomomorphismProp :: forall f a b. (Applicative f, Eq (f b)) => Fun a b -> a -> Bool
apHomomorphismProp (apply -> g) x = (pure @f g <*> pure x) == pure (g x)
main = quickCheck $ apHomomorphismProp @BinTree @Int @Int
但是,当我执行代码时,应用于applicative属性的quickCheck
返回:
(0次测试)
我该如何解决这个问题?
1条答案
按热度按时间wfauudbj1#
很简单,您的
pure
实现生成了一棵无限树,<*>
保留了树两边的无限大小,然后将生成的无限树与另一棵无限树进行比较,看是否相等。很明显,它没有发现它们之间的任何差异......但是它也没有终止。所以QuickCheck实际上从来没有设法确认哪怕一个测试用例是正确的。
一种解决方法是不使用
==
,而是使用一个等式运算符,该运算符只检查有限深度内的等式,并假设在更深的深度内也是相等的(注意,它仍然是指数级开销,所以你甚至不能检查非常深的深度!)