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

泰莎·奥特曼（Tessa Altman）

我正在尝试学习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的评估比较懒惰，所以我仍然应该能够获得相同的结果吗？是length吗一旦长度大于，前两个条件就不应该评估为falsen吗？

我误会了什么？

威廉·范昂塞姆

使用此length方法不是一个好主意的主要原因之一是因为当必须在一个无限列表上对其求值时，它将陷入无限循环中。

好消息是，我们不需要length。这也将使时间复杂度恶化。我们可以使用两个枚举器，一个枚举器比另一个枚举器多n-1个位置。如果此枚举数到达列表的末尾，那么我们知道第一个枚举数仍具有n-1个元素，因此我们可以停止产生值：

conseq :: Int -> [a] -> [[a]]
conseq n ys = go (drop (n-1) 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]]

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。