How to get every Nth element of an infinite list in Haskell?

Question

More specifically, how do I generate a new list of every Nth element from an existing infinite list?

E.g. if the list is [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ...] then getting every 3rd element would result in this list [0,0,0,0,0 ...]

Answer 1

I don't have anything to test this with at work, but something like:

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

should work even on infinite lists.

(Edit: tested and corrected.)

Answer 2

MHarris's answer is great. But I like to avoid using \, so here's my golf:

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

Answer 3

Alternate solution to get rid of mod:

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

Answer 4

I nuked my version of Haskell the other day, so untested, but the following seems a little simpler than the others (leverages pattern matching and drop to avoid zip and mod)

everynth n xs = y:(everynth n ys) where y:ys = drop (n-1) xs

Answer 5

My version using drop:

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

Edit: this also works for finite lists. For infinite lists only, Charles Stewart's solution is slightly shorter.

Answer 6

Starting at the first element:

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

Starting at the nth element:

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

Answer 7

All the solutions using zip and so on do tons of unnecessary allocations. As a functional programmer, you want to get into the habit of not allocating unless you really have to. Allocation is expensive, and compared to allocation, everything else is free. And allocation doesn't just show up in the "hot spots" you would find with a profiler; if you don't pay attention to allocation, it kills you everywhere.

Now I agree with the commentators that readability is the most important thing. Nobody wants to get wrong answers fast. But it happens very often in functional programming that there are multiple solutions, all about equally readable, some of which allocate and some of which do not. It's really important to build a habit of looking for those readable, non-allocating solutions.

You might think that the optimizer would get rid of allocations, but you'd only be half right. GHC, the world's best optimizing compiler for Haskell, does manage to avoid allocating a pair per element; it fuses the filter-zip composition into a foldr2. The allocation of the list [1..] remains. Now you might not think this is so bad, but stream fusion, which is GHC's current technology, is a somewhat fragile optimization. It's hard even for experts to predict exactly when it's going to work, just by looking at the code. The more general point is that when it comes to a critical property like allocation, you don't want to rely on a fancy optimizer whose results you can't predict. As long as you can write your code in an equally readable way, you're much better off never introducing those allocations.

For these reason I find Nefrubyr's solution using drop to be by far the most compelling. The only values that are allocated are exactly those cons cells (with :) that must be part of the final answer. Added to that, the use of drop makes the solution more than just easy to read: it is crystal clear and obviously correct.

Answer 8

Another way of doing it:

takeEveryM m lst = [n | (i,n) <- zip [1..] lst, i `mod` m == 0]

Yet Another:

import Data.List

takeEveryMth m = 
  (unfoldr g)  . dr
     where 
       dr = drop (m-1)
       g (x:xs) = Just (x, dr xs)
       g []     = Nothing

Answer 9

the compiler or interpreter will compute the step size (subtract 1 since it's zero based):

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

http://www.haskell.org/onlinereport/exps.html#arithmetic-sequences

Answer 10

Use a view pattern!

{-# LANGUAGE ViewPatterns #-}

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

---

Ugly version of Nefrubyr's answer preserved so comments make sense.

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

Answer 11

Explicit recursion is evil! Use a library construct like map, filter, fold, scan, reproduce, iterate etc instead. Unless it makes the code drastically easier to read even to those au fait with the libraries, then it's just making your code less modular, more verbose and harder to reason about.

Seriously, the explicitly recursive versions need to be voted down to negative for a task as simple as this. Now I guess I should say something constructive to balance my carping.

I prefer to use a map:

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

rather than the ja's list comprehension so the reader doesn't have to worry about what i is. But either way it's O(n^2) when it could be O(n), so maybe this is better:

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

Answer 12

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

I was going to feel proud of myself, until I saw that Greg got about the same answer and before me