0

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 r1通过f1 (f2 r2)（在本例中为“val1”）访问该值。（事实上​​，这就是我尝试在自己的代码中使用这些类型的数据结构的方式。）

2 问题

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

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

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

r3 = T { f1 = "val1"
       , f2 = r2 
       } :: T

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

1 回答 1

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 == referenceis 且仅当对于所有值complexCondition n都是 false 。这是不可行的检查。n

但是，由于上的比较问题T是 coRE（它的补码是递归可枚举的），那么我们可以半决定补码。实际上，对于不同的 s ，生成的Eq实例将False在有限时间内返回。T这是可行的，因为只需要检查这些值的有限前缀才能声明False.

于 2016-05-17T07:24:01.240 回答