Haskell 中的递归循环

Question

我偶然发现了以下问题。说我有一个递归函数，比如

run :: [Int] -> [Int]
run [] = []
run (x:xs) = 1:x:run xs

重要的是，它head $ run <whatever>始终是1。这意味着以下将产生输出1：

head $ run [error "shouldnt get here"]

这证明 Haskell 在不需要的情况下不会评估参数——显然，因为这是 Haskell 最著名的特性之一。但是，如果我将结果用作参数，例如：

let out = run (cycle out) in head out

我收到运行时错误<<loop>>。

怎么来的？

我正在使用runghc 8.4.2. 这是一个错误还是我在这里遗漏了什么？

Answer 1

run (error "urk!") 会出错。

相反，run [error "urk!"]会成功返回1。

为什么？因为run由 case 定义：空列表、非空列表。因此，它必须评估它的参数，以知道列表是否为空。我们不必评估错误 in[error "urk!"]以查看列表不为空，但我们有 iferror "urk!"是列表本身。

在发布的代码中，我们进行了评估，run (cycle out)因此我们必须检查是否cycle out为空。这会触发 的评估cycle out，进而触发out(cycle也由案例定义)的评估。由于out是我们所定义的，我们得到了无限递归。

碰巧这种无限递归很容易被 GHC 运行时发现，它会发出异常<<loop>>而不是执行非终止计算。

为了强调这个概念，请考虑这些功能

strictPrepend :: [Int] -> [Int]
strictPrepend []     = 1 : []
strictPrepend (x:xs) = 1 : x : xs

lazyPrepend :: [Int] -> [Int]
lazyPrepend xs = 1 : xs

人们可能认为这些功能是平等的。实际上，第一个是由 case 定义的，但是在这两种情况下它执行相同的操作（前置1），因此它看起来与第二个相同。

具体来说，对于所有底部空闲列表ys，我们的结果strictPrepend ys与 相同lazyPrepend ys。

在存在底部（如error ".."、undefined或无限递归）时，这些函数不同。例如lazyPrepend undefined = 1 : undefined， whilestrictPrepend undefined = undefined因为它在生成初始元素之前引发异常1。

最后，

let ys = strictPrepend ys
    zs = lazyPrepend zs

定义ys为底部（无限递归）但是zs = 1:1:1:1:.....是1s的无限序列。这是产生1before 需要评估参数的效果。