logo标签列表

如何在Haskell中获取无限列表的每个第N个元素？

listhaskellfunctional-programming
34

更具体地说，如何从现有的无限列表生成每第N个元素的新列表？

例如，如果列表是[5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ...]，那么获取每3个元素将导致这个列表[0,0,0,0,0 ...]

23个回答
61

使用drop的我的版本:

every n xs = case drop (n-1) xs of
              y : ys -> y : every n ys
              [] -> []

编辑：这个方法同样适用于有限列表。对于仅限于无限列表的情况，Charles Stewart提供的解决方案略微更短。

1
我倾向于将其命名为 takeEvery 或 takeNth；不幸的是，在其他各种语言中，这两个名称均指始终包括第一个元素并仅从第 N 个元素开始跳过的版本。不确定如何最好地区分这些意图的名称。 - Mark Reed
解密会话会很棒。 [] -> [] 是什么意思？ - user3292534
1
@kaboom [] -> [] 使用模式匹配，当 drop (n-1) xs 返回一个空列表时返回一个空列表。 - Victor Johnson
我还想补充一点，这个函数的两种模式应该互换，以便正确格式化尾调用。因此，在[] -> []之前应该是(y:ys) -> y : every n ys。 - Victor Johnson
2
我对Haskell还很生疏，这让我感到头痛。但我不会停止尝试 :) 感谢你的回答！ - user3292534
显示剩余5条评论
37
所有使用“zip”等操作的解决方案都会进行大量不必要的分配。作为一个函数式编程者，您希望养成尽可能少分配内存的习惯，除非确实需要。分配内存是昂贵的，与分配内存相比，其他所有操作都是免费的。如果您不注意内存分配，它不仅会在性能瓶颈中出现；它还会在每个地方影响您。
现在我同意评论员们的观点，即可读性是最重要的。没有人想要迅速得到错误的答案。但是，在函数式编程中，经常存在多种解决方案，它们的可读性大致相同，有些需要分配内存，而另一些则不需要。因此，建立寻找那些易于阅读、无需分配内存的解决方案的习惯非常重要。
您可能认为优化器会消除分配，但您只对了一半。Haskell 的最佳优化编译器 GHC 确实成功避免分配每个元素的一对；它将“filter”-“zip”组合融合成了一个“foldr2”。列表“[1..]”的分配仍然存在。现在您可能认为这并不是很糟糕，但流融合（GHC 的当前技术）是一种相当脆弱的优化方法。即使对于专家来说，仅仅通过查看代码就能精确预测何时会发生这种情况也很困难。更普遍的观点是，在涉及分配等关键属性时，您不希望依赖于无法预测其结果的花哨优化器。只要您能以同样易于阅读的方式编写代码，最好永远不要引入那些内存分配。
因此，我认为 Nefrubyr 使用“drop”的解决方案是最有说服力的。唯一分配的值正是那些必须成为最终答案一部分的 cons 单元（带有“:”）。除此之外，“drop”的使用使得解决方案不仅易于阅读：它清晰明了且显然正确。
2
我同意，并且我发现Nefrubyr的解决方案更容易理解。 - Linus Arver
2
我相信一个好的编译器将避免不必要的分配。 - Thomas Eding
5
我建议编写易读的代码，然后进行性能分析和优化。如果可读性受损却不会导致问题，那么就没有必要做出这种牺牲。 - RCIX
1
@trinithis: 我已经检查了 GHC，你说得大部分正确。但你提出了一个很好的观点，所以我编辑了我的答案，以明确为什么你不一定希望将优化器应用于某些代码并期望得到最佳结果。 - Norman Ramsey
4
我同意你的观点，但只是在某种程度上。显然，可读性至关重要。但是如果你在所有地方都忽略分配，那么你会减慢整个程序的速度，并且不一定能够通过剖析轻松找到“热点”。我已经更新了我的答案，试图反映出更加细致入微的观点。 - Norman Ramsey
显示剩余4条评论
16

我在工作中没有任何测试的东西，但是类似这样的代码：

extractEvery m = map snd . filter (\(x,y) -> (mod x m) == 0) . zip [1..]

应该即使在无限列表上也能正常工作。

(编辑：已测试并更正。)

谢谢，这个很好用，虽然我还不太理解它（我在Haskell方面还是个初学者）。 - Linus Arver
在编写真实代码时，不要做大量预测结果的工作。 - Will Ness
14

从第一个元素开始：

everyf n [] = []
everyf n as  = head as : everyf n (drop n as)

从第n个元素开始：

every n = everyf n . drop (n-1)
7
将其带到逻辑上一步，everyf n = map head . takeWhile (not . null) . iterate (drop n) 或 every n = map head . takeWhile (not . null) . iterate (drop n) . drop (n-1)。 - ephemient
1
. drop (n-1) 而不是 (drop (n-1) as) 让代码更加优雅易读，我现在已经在我的答案中使用了它... :) - sth
非常好。我喜欢你提供了两个函数，一个可以获取 [0, N1, N2, N3...]，另一个可以获取 [N1, N2, N3...]。 - Linus Arver
14
3
这个人的高尔夫得分明显是最好的，但没有赞。真是不公平。 - Michael Fox
我并不真的关心高尔夫分数，但这是一个非常好的无限列表解决方案。应该注意，它不能用于有限列表。 - phunehehe
4
@phunehehe，不，这是一个可怕的解决方案，因为它从头重新遍历列表，导致二次行为; 并且会使l在内存中保留-防止l被垃圾收集器回收，使其短暂存在并根本不分配。 - Will Ness
11

MHarris的答案很好。但我喜欢避免使用\，所以这是我的高尔夫球：

extractEvery n
  = map snd . filter fst
  . zip (cycle (replicate (n-1) False ++ [True]))
4
为了从索引n-1开始而不是从索引0开始，可以使用以下代码：cycle $ replicate (n-1) False ++ [True]。其中replicate (n-1) False表示将False元素复制(n-1)次，然后通过++ [True]在末尾添加一个True元素。最后使用cycle函数将结果重复循环。 - ephemient
是的，ephemient的修改做到了我最初要求的。 - Linus Arver
10

另一种去除mod的解决方案：

extractEvery n = map snd . filter ((== n) . fst) . zip (cycle [1..n])
mod和==有什么区别？仍在进行可预测结果的测试...我不认为你今天会像这样编码。 :) - Will Ness
10

前几天我把我的Haskell版本删掉了，因此尚未经过测试，但以下代码似乎比其他代码简单一些（利用模式匹配和drop函数避免使用zip和mod）：

everynth :: Int -> [a] -> [a]
everynth n xs = y : everynth n ys
         where y : ys = drop (n-1) xs
2
我先从这个开始，然后测试了一下：当 (y:ys) 无法匹配空列表时，它会在有限列表上失败。但问题是关于无限列表的，所以我想应该没问题！ - Nefrubyr
确实，这对于无限列表运作良好，但对于有限列表则不行。我喜欢解决方案看起来很简单 - 只要它也适用于有限列表... - Linus Arver
这个无法适用于有限列表的失败暗示着保留每个索引是n的倍数的元素的版本更加“自然”。 - Matthias
5
另一种做法是：
takeEveryM m lst = [n | (i,n) <- zip [1..] lst, i `mod` m == 0]

另一个：

import Data.List

takeEveryMth m = 
  (unfoldr g)  . dr
     where 
       dr = drop (m-1)
       g (x:xs) = Just (x, dr xs)
       g []     = Nothing
3
明确的递归非常不好！使用像 map、filter、fold、scan、reproduce、iterate 等库构造代替。除非它可以使代码对于那些熟悉这些库的人来说更易读，否则它只会使你的代码不太模块化、更冗长且更难以理解。
说真的，对于这么简单的任务，明确的递归版本需要被评为负分。现在我想说点有建设性的话来平衡我的抱怨。
我更喜欢使用 map：
every n xs = map (xs!!) [n-1,n-1+n..]

为了让读者不必担心 i 是什么，建议使用以下代码而非 JA 的列表推导式。但无论哪种方式，都需要 O(n^2) 的时间复杂度，而实际上可以优化到 O(n)，因此也许以下代码更好：

every n = map (!!(n-1)) . iterate (drop n)
3
我曾试图将我的答案重写为 map 或 fold 的形式，但在这种情况下，我觉得显式递归最简洁。作为一个一般原则，我同意你的观点，认为像 map 和 fold 这样的库函数更可取。primodemus 使用 unfoldr 的答案是我所追求的，但我很高兴我停在了这里；-）你的解决方案会对列表的每个部分进行两次遍历（一次是为了 !!，一次是为了 drop）；ephemient 对 sth 的答案的评论给出了这类问题的最佳解决方案，通过“滑动”列表并使用 map head。 - Nefrubyr
错过了那个评论！我在考虑是发表我的还是他的，最终决定简单的代码比一个常数因子更重要。人们通常在使用库之前会发现显式递归更清晰，但熟悉库的方法就是使用它们。对于像这样的问题，投票支持显式递归解决方案是防止他们学习正确方法的好方法。 - Greg M
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接