haskell - 为什么我的函数不适用于无限列表？

Question

我正在尝试学习 haskell 并实现了一个函数 conseq，它会返回大小为 n 的连续元素列表。

conseq :: Int -> [Int] -> [[Int]]
conseq n x 
      | n == length(x) = [x]
      | n > length(x) = [x]
      | otherwise = [take n x] ++ (conseq n (drop 1 x))

这可以正常工作。

> take 5 $ conseq 2 [1..10]  
[[1,2],[2,3],[3,4],[4,5],[5,6]]

但是，如果我传递 [1..] 而不是 [1..10]，程序就会陷入无限循环。

据我了解，haskell 具有惰性求值功能，所以我应该仍然能够获得相同的结果，对吗？是长度吗？长度大于 n 时，前两个条件是否应该立即评估为 false？

我误会了什么？

Answer 1

使用 length 不是一个好主意的主要原因之一是当它必须在无限列表上计算时，它会陷入无限循环。

好消息是，我们不需要length。这也会使时间复杂度变得更糟。我们可以使用两个枚举器，一个在另一个前面 n-1 个位置。如果这个枚举器到达列表的末尾，那么我们就知道第一个枚举器仍然有 n-1 个元素，因此我们可以停止产生值:

conseq :: Int -> [a] -> [[a]]
conseq n ys = go (<b>drop (n-1)</b> ys) ys
    where go [] _ = []
          go (_:as) ba@(~(_:bs)) = take n ba : go as bs

这给了我们:

Prelude> conseq 3 [1 ..]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10],[9,10,11],[10,11,12],[11,12,13],[12,13,14],[13,14,15],[14,15,16],[15,16,17],[16,17,18],[17,18,19],[18,19,20],[19,20,21],[20,21,22],[21,22,23],[22,23,24],[23,24,25],[24,25,26],[25,26,27],…
Prelude> conseq 3 [1 .. 4]
[[1,2,3],[2,3,4]]