使用Haskell的Quickcheck检查传递性 [英] Using Haskell's Quickcheck to check transitivity

问题描述

如何获取Quickcheck来检查以下代码中的可传递属性?该代码表示​​物理块的堆栈.只能使用 MoveOnto bl b2 s 操作将块放置在空表或另一个块上，该操作在 b2 移入和移出 bl s 上的code>.我的Quickcheck尝试只是挂起，没有任何结果.

How can I get Quickcheck to check the transitive property in the code below? The code represents a stack of physical blocks. Blocks can only be placed on an empty table or another block using the operation MoveOnto bl b2 s, which is read as b2 is moved into and onto bl on stack or table s. My Quickcheck attempt just hangs and produces no result.

import Test.QuickCheck
data Block = Block Int deriving (Show,Eq)
data Stack = EmptyTable  |  MoveOnto Block Block Stack deriving  (Show,Eq) 
isOn :: Block -> Block -> Stack -> Bool
isOn b1 b2 (MoveOnto b3 b4 s) |  ((b1 == b3) && (b4 == b2)) || (isOn b4 b2 s)   =  True
isOn _ _ _  = False

b1' = Block 1
b2' = Block 2
b3' = Block 3
b4' = Block 4
b5' = Block 5
b6' = Block 6
b7' = Block 7
b8' = Block 8

-- Hand made test
testTransitivityTrue b1 b2 b3 b4 b5  = isOn b1 b5 (MoveOnto b1 b2 (MoveOnto b2 b3 (MoveOnto b3 b4 (MoveOnto b4 b5 EmptyTable))))

instance Arbitrary (Block) where
  arbitrary =  arbitrary


instance Arbitrary (Stack) where
  arbitrary = oneof [return EmptyTable, MoveOnto <$> arbitrary <*> arbitrary <*> arbitrary]

prop_pass b1 b2 s   = isOn b1 b2 (MoveOnto b1 b2 s)

推荐答案

由于尝试构建任意 Block 时，您执行了无数递归，因此它挂起了.确实:

It hangs since in the attempt to construct an arbitrary Block, you perform endless recursion. Indeed:

instance Arbitrary (Block) where
  arbitrary = arbitrary

所以在这里这意味着您写道，可以通过生成任意块来生成任意块.这当然是行不通的.您可以定义一个任意的 Int ，然后使用以下方法为其构建一个块:

So here that means that you wrote that one can generate an arbitrary block by generating an arbitrary block. This will of course not work. You can define an arbitrary Int, and then construct a block for that with:

instance Arbitrary (Block) where
  arbitrary = fmap Block arbitrary

现在可以构造任意的块，也可以构造任意的堆栈，尽管如果我们将概率建模为统一的，则完全有可能无限期地运行(由于技术原因)，我们知道最终堆栈构建将停止.

Now that arbitrary blocks can be constructed, arbitrary stacks can be constructed as well, although there is strictly speeking a possibility that this will run for an infinite time as well (due to technical reasons), if we model the probabilities as uniform, we know that eventually the stack building will stop.

这篇关于使用Haskell的Quickcheck检查传递性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！