无限列表、懒惰求值和长度

Question

Haskell 菜鸟：我仍在努力理解这门语言的机制，所以如果我的问题很愚蠢，请原谅我并指出一些我可以学习的 link来自（我在 Whosebug 上的类似主题中搜索了一段时间，但我仍然无法理解）。

我想出了这个功能：

chunks :: Int -> [a] -> [[a]]
chunks n xs
    | length xs <= n = [xs]
    | otherwise = let (ch, rest) = splitAt n xs in ch:chunks n rest

所以

ghci> chunks 4 "abracadabra"
["abra","cada","bra"]
ghci> 
ghci> chunks 3 [1..6]
[[1,2,3],[4,5,6]]

我对此很满意，然后我想"there's lazy evaluation! I can use this even on an infinite sequence!"。所以我尝试了 take 4 $ chunks 3 [1..]。我希望懒惰的 haskell 魔法会产生 [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]，但这次懒惰似乎帮不了我：它无法到达计算的终点（它是不是走所有的距离 [1..] 的结尾还有很长的路要走？）

我认为问题出在 "length xs" 部分：ghci 似乎也卡在了一个简单的 length [1..] 上。所以我在问：长度实际上是在迭代整个列表以给出响应吗？如果是这样，我想每次我尝试实现与惰性评估一起工作的东西时都要避免长度，所以还有其他选择吗？（例如，我如何改进我的示例以使用无限列表？）

Answer 1

is length actually iterating the whole list to give a response?

是的，绝对是。

length is to be avoided every time I try to implement something working well with the lazy evaluation

是的，绝对。

so there is some alternative?

是：在不引用length的情况下解决问题。没有通用的解决问题的方法，所以你需要解决每个具体的问题。

how can I improve my example to work with infinite lists

你是一名铁路工人。如果汽车从您站立的地方开始并延伸到 horizon，那就是一列巨大的火车。你不知道它在哪里结束，如果有的话。你的工作是将它分成每列三节车厢的小火车。你如何进行？

Answer 2

is length actually iterating the whole list to give a response?

是的。

I guess length is to be avoided every time I try to implement something working well with the lazy evaluation

不仅如此，当懒惰不是一个因素时，它还会给你糟糕的运行时间（在 O(1) 检查通常就足够的情况下为 O(n)¹ ), 所以一般情况下你应该避免它。

how can I improve my example to work with infinite lists?

你不需要检查列表的长度是否小于n，你只需要检查它是否为零。您可以使用简单的模式匹配来做到这一点。

¹ 例如像 f xs | length xs >= 2 = ... 这样的 O(n)，可以用 f (x1 : x2 : xs) = ... 代替，也就是 O(1)。

Answer 3

你可以做的另一个技巧（我在 Data.Text 中看到过，但令我惊讶的是一般列表的 Prelude 中没有）是尽快使 length 短路通过返回 Ordering 而不是 Bool.

compareLength :: [a] -> Int -> Ordering
compareLength [] n = compare 0 n
compareLength _ 0 = GT
compareLength (x : xs) n = compareLength xs (n - 1)

然后就可以在chunks中使用了。

chunks :: Int -> [a] -> [[a]]
chunks n xs = case compareLength xs n of
                   LT -> [xs]
                   _  -> let (ch, rest) = splitAt n xs in ch:chunks n rest

这很好用。

*Main> take 4 $ chunks 3 [1..]
[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]

对于这种特殊情况，其他实现可能更惯用，但希望这是一个很好的技巧。

无限列表、懒惰求值和长度

infinite lists, lazy evaluation and length

haskell

infinite

lazy-evaluation