list - 为什么使用头/尾而不是模式匹配会使评估终止？

Question

作为练习，我试图定义一个 ruler值(value)

ruler :: (Num a, Enum a) => [a]

对应于标尺功能

0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2...

n ' 列表的第一个元素(假设第一个元素对应于 n=1 )是 2 的最大幂，它整除 n .为了让它更有趣，我正在尝试实现 ruler无需进行任何可分性测试。

使用辅助函数

interleave :: [a] -> [a] -> [a]

它只是交替了两个给定列表中的元素，我想出了这个 - 但可惜它不起作用:

interleave :: [a] -> [a] -> [a]
interleave  (x:xs) (y:ys) = x : y : interleave xs ys
interleave  _      _      = []

ruler :: (Num a, Enum a) => [a]
ruler = foldr1 interleave . map repeat $ [0..]

main :: IO ()
main = print (take 20 ruler)

该程序最终会耗尽所有堆栈空间。

现在，奇怪的是，如果我调整 interleave 的定义，程序就可以正常工作了。所以它读

interleave (x:xs) ys = x : head ys : interleave xs (tail ys)

IE。我不再对第二个参数使用模式匹配。为什么使用 head和 tail在这里制作 ruler终止 - 毕竟，模式匹配是相当防御性的(我只评估列表脊椎的第一个元素，不是吗？)。

Answer 1

您正在申请foldr对无限列表具有严格的组合功能。

归结为一个最小的示例，您可以在此处查看此行为:

*Main> :t const
const :: a -> b -> a
*Main> :t flip seq
flip seq :: c -> a -> c
*Main> foldr1 const [0..]
0
*Main> foldr1 (flip seq) [0..]
^CInterrupted.

正如其他答案中所解释的，修复是使 interleave懒惰的。

更具体地说，这就是发生的事情。首先我们解决 foldr1 , 替换每个 : interleave 的外部列表:

foldr1 interleave [[0..], [1...], ...]
= interleave [0...] (interleave [1...] (...))

为了进步，第一个 interleave想要在产生第一个值之前评估第二个参数。但是第二个想要评估它的第二个参数，依此类推。

使用 interleave 的惰性定义，第一个值是在评估第二个参数之前产生的。特别是， interleave [1...] (...)将评估为 1 : ... (这有助于第一个 interleave 取得进展)，然后再进一步评估内容。