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

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

我想检查同态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次测试)
我该如何解决这个问题?

wfauudbj

wfauudbj1#

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

相关问题