如何在Haskell中获得无限列表的每n个元素?

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

编辑:这也适用于有限列表。仅对于无限列表,Charles Stewart的解略短。

所有的解决方案都使用 zip .

可读性是最重要的 . 没有人想很快得到错误的答案。但在函数式编程中,经常会出现多种解决方案,所有解决方案都具有相同的可读性,其中一些是分配的,而另一些是不分配的。养成寻找这些东西的习惯真的很重要 解决。

您可能会认为优化器可以消除分配,但您只对了一半。GHC是世界上最好的Haskell优化编译器,它确实避免了为每个元素分配一对;它融合了 filter - 合成 foldr2 [1..] 残余现在你可能不会认为这很糟糕,但是流融合,这是GHC当前的技术,是一个有点脆弱的优化。即使是专家也很难仅仅通过查看代码就准确预测它什么时候会起作用。更一般的一点是 当涉及到像分配这样的关键属性时,您不想依赖一个花哨的优化器,它的结果是您无法预测的 . 只要您能够以同样可读的方式编写代码,就最好不要引入这些分配。

drop 是目前为止最引人注目的。唯一分配的值正是那些cons单元格(带有 : )那 必须 成为最终答案的一部分。此外,使用 滴 使解决方案不仅仅易于阅读:它非常清晰,显然是正确的。

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

即使在无限的列表上也应该工作。

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

从第一个元素开始:

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

从第n个元素开始:

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

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

The Haskell 98 Report: Arithmetic Sequences

姆哈里斯的回答很好。但我喜欢避免使用 \

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

另一种解决方法 mod :

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

前几天我对我的Haskell版本进行了裸机测试,因此未经测试,但以下内容似乎比其他版本更简单(利用模式匹配和drop来避免zip和mod):

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

另一种方法是:

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

{-# LANGUAGE ViewPatterns #-}

everynth n (drop (n-1) -> l)
  | null l = []
  | otherwise = head l : everynth n (tail l)

Nefrubyr回答的丑陋版本被保留下来,因此评论是有意义的。

everynth :: Int -> [a] -> [a]
everynth n l = case splitAt (n-1) l of
                 (_, (x:xs)) -> x : everynth n xs
                 _           -> []

显式递归是邪恶的!使用诸如映射、过滤、折叠、扫描、复制、迭代等库结构。除非它使代码变得非常容易阅读,甚至对那些熟悉库的人来说也是如此,否则它只会使您的代码更少模块化,更冗长,更难推理。

我更喜欢使用地图:

every n xs = map (xs!!) [n-1,n-1+n..]

而不是ja的列表理解,这样读者就不必担心我是什么。但无论哪种方式,当它可能是O(n)时,它都是O(n^2),所以这可能更好:

every n = map (!!(n-1)) . iterate (drop n)

extractEvery n l = map head (iterate (drop n) (drop (n-1) l))

我会为自己感到骄傲,直到我看到格雷格在我面前得到了同样的答案

这里的许多答案已经使用了Data.List.unfover,但我想提出一种有趣的方法来编写有点烦人的unfover,这在其他上下文中可能会有所帮助:

{-# LANGUAGE TupleSections #-}
import Data.List (unfoldr)
import Data.Maybe (listToMaybe)

every n = unfoldr f . drop (n - 1)
    where f xs = (,drop n xs) <$> listToMaybe xs

当列表为空时, listToMaybe 返回一个 Nothing ,及 fmap 没有什么 . 然而,如果 Just

有点傻的版本 foldr :

everyNth n l = foldr cons nil l (n-1) where
  nil _ = []
  cons x rest 0 = x : rest n
  cons x rest n = rest (n-1)

(这是针对 a comment 要求解决方案(不间断)

every _ []     = []
every n (x:xs) = every' n (n-1) (x:xs)
                 where every' n c []     = []
                       every' n 0 (x:xs) = x : every' n (n-1) xs
                       every' n c (x:xs) = every' n (c-1) xs

适用于有限和无限列表:

take 15 (every 3 [1..])
-- [3,6,9,12,15,18,21,24,27,30,33,36,39,42,45]

这似乎是“展开”的更好用法:

everyNth :: Int -> [a] -> [a]
everyNth n = unfoldr g
  where
    g [] = Nothing
    g xs = let (ys, zs) = splitAt n xs in Just (head ys, zs)

everyNth n = (map head) . chunksOf n

老问题,但我会发布我的想法:

everyNth :: [a] -> Int -> [a]
everyNth xs n = [snd x | x <- (zip [1..] xs), fst x `mod` n == 0]

我把list参数放在 Int 所以我可以用curry函数和一个列表,然后把它映射到一个 如果我需要的话。

everyNth n [] = []
everyNth n (x:xs) = x : (everyNth n . drop (n-1)) xs

然后使用

everyNthFirst n = everyNth n . drop (n-1)

everyNthFirst 3 [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ...] 给予 [0, 0, 0, ...]

Data.List.HT 从…起 utility-ht 有 sieve :: Int -> [a] -> [a] .

看见 documentation 和 source :

{-| keep every k-th value from the list -}
sieve, sieve', sieve'', sieve''' :: Int -> [a] -> [a]
sieve k =
   unfoldr (\xs -> toMaybe (not (null xs)) (head xs, drop k xs))

sieve' k = map head . sliceVertical k

sieve'' k x = map (x!!) [0,k..(length x-1)]

sieve''' k = map head . takeWhile (not . null) . iterate (drop k)

propSieve :: Eq a => Int -> [a] -> Bool
propSieve n x =
   sieve n x == sieve'  n x   &&
   sieve n x == sieve'' n x

一个没有明显条件的非常实用的函数:

everyNth :: Int -> [a] -> [a]
everyNth 0 = take 1
everyNth n = foldr ($) [] . zipWith ($) operations where
  operations = cycle $ (:) : replicate (n-1) (const id)

我们可以使用列表:

takeEvery :: Int -> [a] -> [a]
takeEvery n xs = [x | (x, i) <- zip xs [1..], i `mod` n == 0]

我的解决办法是:

every :: Int -> [a] -> [[a]]
every _ [] = []
every n list = take n list : (every n $ drop n list)

公认答案的更丑陋、更有限的版本

every :: Eq a => Int -> [a] -> [a]
every n xs = if rest == [] 
                then [] 
                else head rest : every n (tail rest)
    where rest = drop (n-1) xs

对于“线高尔夫”,可以这样写:

every n xs = if rest == [] then [] else head rest : every n (tail rest) 
    where rest = drop (n-1) xs

(因为它有一个不必要的 Eq a 约束条件。)