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

Question

我正在尝试学习 haskell 并实现了一个函数 conseq，它将 return 大小为 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 有惰性评估，所以我应该仍然能够得到相同的结果，对吗？是length吗？一旦长度大于 n，前两个条件是否应该评估为 false？

我误会了什么？

Answer 1

您的函数做的第一件事是计算 length(x)，因此它知道它应该 return [x]、[x] 还是 [take n x] ++ (conseq n (drop 1 x))

length 计算列表中元素的数量 - 所有元素。如果你问一个无限列表的长度，它永远不会计数完。

Answer 2

使用 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]]

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

Why does my function not work with an infinite list?

haskell

lazy-evaluation