在HSpec中比较两个相互递归的相等值会引起问题

Question

1上下文

考虑以下Haskell片段：

data T = T { f1 :: String 
           , f2 :: T
           } deriving (Eq, Show)
r1 = T { f1 = "val1"
       , f2 = r2 
       } :: T
r2 = T { f1 = "val2"
       , f2 = r1
       } :: T

注意r1相对于r2是如何相互递归的。AFAIK，这在Haskell中是完全可以的（只要你不以这样的方式使用这两个值，从而导致一个永远不会终止的相互递归的调用循环）。例如，r2的用户可能希望通过f1 (f2 r2)（在本例中为"val1"）访问值f1 r1。（事实上，这就是我试图在自己的代码中使用这些数据结构的方式。）

2问题

现在考虑以下HSpec单元测试：

describe "A mutually recursive value should be equal to itself" $ do
    r1 `shouldBe` r1

这会导致测试编译器暂停一段时间，然后最终失败这是否意味着我的代码有问题，或者这只是shouldBe定义方式的一个怪癖（我假设它检查相等性的方式不是懒惰的，并且涉及到一个相互递归的非终止调用）？如果这只是HSpec的shouldBe函数的一个怪癖，那么有没有办法检查相互递归值之间的相等性？我最终想做的事情如下：

r3 = T { f1 = "val1"
       , f2 = r2 
       } :: T
describe "A mutually recursive value should be equal to itself" $ do
    r1 `shouldBe` r3

Answer 1

您无法在有限的时间内比较无限的值。

事实上，比较无限值通常是不可确定的，因此编译器不可能生成一个处理这些值的Eq实例。

为了强调这一点，请考虑以下代码：

complexCondition :: Integer -> Bool
complexCondition = ...
foo :: Integer -> T
foo n | complexCondition n = T { f1 = "found!", f2 = foo (n+1) }
      | otherwise          = T { f1 = "not yet", f2 = foo (n+1) }
reference :: T
reference = T { f1 = "not yet", f2 = reference }

我们将使foo 0 == reference是并且仅当complexCondition n对于所有值n都是false时。这是不可行的检查。

然而，由于T上的比较问题是coRE（其补码是递归可枚举的），因此我们可以半决定补码。事实上，对于不同的Ts，所生成的Eq实例将在有限时间内返回False。这是可行的，因为只需要检查这些值的有限前缀就可以声明False。