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

Question

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

例如,如果列表是[5,3,0,1,8,0,3,4,0,93,211,0 ...]然后让每个第三元件将导致在此列表[0,0,0, 0,0 ......]

Answer 1

我的版本使用drop:

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

编辑:这也适用于有限列表.仅限无限列表,Charles Stewart的解决方案略短.

Answer 2

所有使用zip等的解决方案都会进行大量不必要的分配.作为一名功能性程序员,除非你真的需要,否则你要养成不分配的习惯.分配是昂贵的,与分配相比,其他一切都是免费的.并且分配不仅仅出现在您使用分析器找到的"热点"中; 如果你不注意分配,它会杀死你到处都是.

现在我赞同评论员认为可读性是最重要的.没有人想快速得到错误的答案.但它经常发生在函数式编程中,有多个解决方案,所有解决方案都具有相同的可读性,其中一些解决方案是分配的,而另一些则不是.建立寻找可读,非分配解决方案的习惯非常重要.

你可能会认为优化器会摆脱分配,但你只有一半是正确的.GHC是世界上最好的Haskell优化编译器,它确实设法避免为每个元素分配一对; 它融合了filter- zip组合成一个foldr2.清单的分配[1..]仍然存在.现在你可能不认为这是如此糟糕,但流融合,这是GHC目前的技术,是一个有点脆弱的优化.即使是专家也很难通过查看代码来准确预测它何时起作用.更普遍的一点是,当谈到像分配这样的关键属性时,你不想依赖于一个你无法预测其结果的花哨的优化器.只要你能以同样可读的方式编写代码,你就不会引入那些分配.

基于这些原因,我发现Nefrubyr的解决方案drop是最引人注目的.被分配的唯一值是完全相同的利弊细胞(带:),其必须是最后的答案的一部分.除此之外,使用它drop使解决方案不仅仅是易于阅读:它非常清晰,显然是正确的.

Answer 3

我没有任何东西可以在工作中测试这个,但是类似于:

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

甚至应该在无限列表上工作.

(编辑:经过测试和更正.)

Answer 4

从第一个元素开始:

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

从第n个元素开始:

every n = everyf n . drop (n-1)

Answer 5

MHarris的答案很棒.但我喜欢避免使用\,所以这是我的高尔夫:

extractEvery n
  = map snd . filter fst
  . zip (cycle (replicate (n-1) False ++ [True]))

Answer 6

编译器或解释器将计算步长(减去1,因为它基于零):

f l n = [l !! i | i <- [n-1,n-1+n..]]

Haskell 98报告:算术序列

Answer 7

替代解决方案摆脱mod:

extractEvery n = map snd . filter ((== n) . fst) . zip (cycle [1..n])

Answer 8

我前几天修改了我的Haskell版本,所以未经测试,但以下看起来比其他版本更简单(利用模式匹配和删除以避免zip和mod):

everynth :: Int -> [a] -> [a]
everynth n xs = y : everynth n ys
         where y : ys = drop (n-1) xs

Answer 9

另一种方法：

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