无限的名单，懒惰的评价和长度 [英] infinite lists, lazy evaluation and length

问题描述

Haskell noob here：我仍然试图理解语言的机制，所以如果我的问题很愚蠢，请原谅我，并指向我可以学习的一些链接（我已经在类似主题中搜索了一段时间这里在stackoverflow，但我仍然无法得到这个）。

我出来这个函数：

  chunks :: Int  - > [a]  - > [[a]] 
 chunks n xs 
 |长度xs <= n = [xs] 
 |否则= let（ch，rest）= splitAt n xs in ch：chunks n rest 
  

/ p>

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

我对此非常满意，然后我认为有一种懒惰的评价！我甚至可以在无限的序列中使用它！。所以我尝试了取4个$ chunks 3 [1 ..] 。我希望懒惰的哈斯克尔魔法会产生 [[1,2,3]，[4,5,6]，[7,8,9]，[10,11,12]] ，反而看起来像这个时候懒惰不能帮助我：它不能达到计算的末尾（是否一直走到的结尾[ 1 ..] ？）

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

解决方案

是。

$ b是实际迭代整个列表的长度以给出响应吗？ $ b

我想每次尝试实现一些与懒惰评估相配的工作时都应避免使用长度

不仅如此，当懒惰不是一个因素时（O（n）在O（1）检查通常满足的情况下），它也会给你带来不好的运行时间，所以您应该避免大部分时间。

如何改进我的示例以使用无限列表？

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

---

¹ code> f xs |可以用 f（x1：x2：xs）= ... ，即O（n） c $ c>，这是O（1）。

Haskell noob here: I'm still trying to understand the mechanics of the language, so if my question is plain stupid, forgive me and point me to some link which I can learn from (I've searched awhile in similar topics here on stackoverflow, but still I can't get this).

I came out with this function:

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

so that

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

I was pretty satisfied with that, then I thought "there's lazy evaluation! I can use this even on an infinite sequence!". So i tried take 4 $ chunks 3 [1..]. I was hoping that the lazy haskell magic would have produced [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]], instead it seems like this time lazyness can't help me: it can't reach the end of the computation (is it walking all the way long to the end of [1..]?)

I think the problem is in the "length xs" part: ghci seems to get stuck also on a simple length [1..]. So I'm asking: is length actually iterating the whole list to give a response? If so, I guess length is to be avoided every time I try to implement something working well with the lazy evaluation, so there is some alternative? (for instance, how can I improve my example to work with infinite lists?)

解决方案

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

Yes.

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

Not just that, it also gives you bad runtimes when laziness isn't a factor (being O(n) in cases where an O(1) check often suffices¹), so you should avoid it most of the time in general.

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

You don't need to check whether the length of the list is less than n, you just need to check whether it's zero. And that you can do with a simple pattern match.

---

¹ For example something like f xs | length xs >= 2 = ..., which is O(n), can be replaced with f (x1 : x2 : xs) = ..., which is O(1).

这篇关于无限的名单，懒惰的评价和长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！