34

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 ...]

23 Answers 23

61

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.

10
  • 1
    I would be inclined to name this takeEvery or takeNth; unfortunately, both of those in various other languages refer to a version that always includes the first element and only starts skipping N thereafter. Not sure how best to distinguish those intents in the name.
    – Mark Reed
    Commented Oct 20, 2013 at 14:01
  • Deciphering session would be great. What [] -> [] does?
    – user3292534
    Commented Feb 2, 2016 at 12:16
  • 1
    @kaboom [] -> [] is using pattern matching to return an empty list when drop (n-1) xs returns an empty list. Commented Feb 5, 2016 at 6:01
  • I would also like to add that the two patterns of this function should be switched for a properly formatted tail call. So [] -> [] should come before (y:ys) -> y : every n ys. Commented Feb 5, 2016 at 6:04
  • 2
    I'm still fresh with Haskell, this is melting my brain. But I shall not stop trying :) Thanks for the answers!
    – user3292534
    Commented Feb 5, 2016 at 9:31
37

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.

9
  • 2
    I agree, and I find Nefrubyr's solution easier to follow as well. Commented Jan 9, 2010 at 5:48
  • 2
    I'm sure a good compiler will avoid the unnessary allocations. Commented Jan 9, 2010 at 6:58
  • 5
    -1, i would recommend coding for readability then profiling then optimizing the profiled portions. No point in making code readability sacrifices when it may not even cause a problem
    – RCIX
    Commented Jan 9, 2010 at 7:51
  • 1
    @trinithis: I checked with GHC, and you are mostly right. But you make a good point, so I have edited my answer to make it clear why you don't necessarily want to throw an optimizer at some code and hope for the best. Commented Jan 9, 2010 at 20:56
  • 4
    @RCIX: I agree with you, but only in part. Certainly readability is paramount. But if you ignore allocation everywhere, then you will slow down all of your program, and there won't necessarily be "hot spots" that you can find easily by profiling. I've updated my asnwer to try to reflect a more nuanced view. Commented Jan 9, 2010 at 20:57
16

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.)

2
  • Thanks, this works well, although I don't quite understand it yet (I'm still a beginner in Haskell). Commented Jan 9, 2010 at 5:26
  • doing lots of work with predictable results... never do this in real code.
    – Will Ness
    Commented Oct 26, 2017 at 9:10
14

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)
3
  • 7
    Taking this to the logical next step, everyf n = map head . takeWhile (not . null) . iterate (drop n) or every n = map head . takeWhile (not . null) . iterate (drop n) . drop (n-1).
    – ephemient
    Commented Jan 8, 2010 at 18:39
  • 1
    . drop (n-1) instead of (drop (n-1) as) makes it so much nicer and more readable that I now just had to use that in my answer... :)
    – sth
    Commented Jan 9, 2010 at 1:14
  • Very nice. I like how you gave two functions to get either [0, N1, N2, N3...] or [N1, N2, N3...]. Commented Jan 9, 2010 at 6:23
14

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..]]

The Haskell 98 Report: Arithmetic Sequences

3
  • 3
    This one has by-far the best Golf score but no upvotes. There's no justice. Commented Jun 13, 2014 at 17:28
  • I don't really care about golf score but this is a really neat solution for infinite lists. Should be noted it doesn't work on finite lists though.
    – phunehehe
    Commented Feb 21, 2016 at 8:28
  • 4
    @phunehehe no, it is a terrible solution, because it re-traverses the list from the start and so has quadratic behaviour; and causes l's retention in memory - prevents l from being garbage collected, from being made ephemeral and not being allocated at all.
    – Will Ness
    Commented Oct 26, 2017 at 9:05
11

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

extractEvery n
  = map snd . filter fst
  . zip (cycle (replicate (n-1) False ++ [True]))
2
  • 4
    Or cycle $ replicate (n-1) False ++ [True] since OP wants to start at index n-1, not index 0.
    – ephemient
    Commented Jan 8, 2010 at 18:37
  • Yes, ephemient's modification does what I originally asked for. Commented Jan 9, 2010 at 5:34
10

Alternate solution to get rid of mod:

extractEvery n = map snd . filter ((== n) . fst) . zip (cycle [1..n])
1
  • mod, ==, what's the difference? still doing tests with predictable results... I don't think you'd code it like this, today. :)
    – Will Ness
    Commented Oct 26, 2017 at 9:16
10

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 :: Int -> [a] -> [a]
everynth n xs = y : everynth n ys
         where y : ys = drop (n-1) xs
3
  • 2
    I started with this, and then tested it: it fails for finite lists when (y:ys) cannot match the empty list. But the question is for infinite lists so I guess that's OK!
    – Nefrubyr
    Commented Jan 8, 2010 at 14:37
  • Indeed, this works fine for infinite lists, but not for finite lists. I like how simple the solution looks -- if only it worked for finite lists as well... Commented Jan 9, 2010 at 5:41
  • The failure of this to work for finite lists hints that the version that keeps every element whose index is a multiple of n is more 'natural'.
    – Matthias
    Commented Nov 21, 2018 at 19:59
5

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
0
3

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)
2
  • 3
    I did try to rewrite my answer as a map or fold but in this case I found the explicit recursion cleanest. As a general principle I agree with you that library functions such as maps and folds are preferred. primodemus's answer using unfoldr is the sort of thing I was aiming for, but I'm glad I stopped where I did ;-) Your solution walks each section of the list twice (once for !!, once for drop); ephemient's comment on sth's answer gives the best solution along these lines by "sliding" the list along and using map head.
    – Nefrubyr
    Commented Jan 11, 2010 at 10:03
  • Missed that comment! Was a toss-up whether to post that or mine, decided simpler code was more important than a constant factor. People frequently do find explicit recursion clearer before they're used to the libraries, but the way to get used to the libraries is to use them. Voting up explicitly-recursive solutions to something like this is a good way to prevent them learning to do it right.
    – Greg M
    Commented Jan 12, 2010 at 3:44
2

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
                 _           -> []
4
  • 2
    Seems rather pointless to use splitAt instead of drop if you never even look at the fst of the resulting tuple.
    – ephemient
    Commented Jan 9, 2010 at 6:30
  • I see now that it's a muddier version of Nefrubyr's answer.
    – Greg Bacon
    Commented Jan 9, 2010 at 6:43
  • Go ahead and remove it if you want; anybody confused can look through edit history, or I can delete my comment. That aside: documentation for ViewPatterns says that the implementation shall tries to gather common views together for execution efficiency, so I think the guards are just confounding. Subjective, of course...
    – ephemient
    Commented Jan 9, 2010 at 7:23
  • Maybe it'll spare someone thinking, 'No one's used splitAt yet!' I agree that the guards aren't ideal, but the alternatives aren't great either: I'd have to repeat the same code in separate cases or define a helper function at the outer scope—nicer if cases of a function could share a where clause.
    – Greg Bacon
    Commented Jan 9, 2010 at 8:32
1

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

1

A lot of answers here already use Data.List.unfoldr, but I wanted to bring up an interesting way of writing the somewhat annoying unfold that may be helpful in other contexts:

{-# 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

When the list is null, listToMaybe returns a Nothing, and fmap similarly will then be Nothing. However, if a Just is produced, then the proper tuple is constructed by turning the head of the list into a tuple of the head and the rest of the values to use in the next iteration.

1

A slightly silly version with 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)
2
  • 1
    Not silly in the least! This should be able to fuse with a "good producer" to (potentially) avoid realizing the argument list. I imagine you could wrap GHC.List.build around this to make it fuse the other way too.
    – dfeuer
    Commented Nov 20, 2018 at 15:06
  • You can probably also make it take any foldable, rather than insisting on a list.
    – Matthias
    Commented Nov 21, 2018 at 16:30
1

(This was in response to a comment asking for a solution without drop)

I couldn't see this solution, so:

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

works for finite and infinite list:

take 15 (every 3 [1..])
-- [3,6,9,12,15,18,21,24,27,30,33,36,39,42,45]
3
  • @WillNess yes, but the comment asked for a solution without drop :-D I considered doing a fold, but that felt out of the spirit of the challenge.
    – Matt Ellen
    Commented Aug 13, 2019 at 15:50
  • Great ! Note that you don't need n as a leftmost parameter of your every' function, as it is constant and provided by the outer scope.
    – jpmarinier
    Commented Oct 31, 2020 at 10:55
  • No need for the outer matching. Just every n = every' n (n-1), or, as @jpmarinier points out, even every n = every' (n-1).
    – dfeuer
    Commented Jan 23, 2021 at 22:07
0

This seems a slightly better use of unfold:

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

Or even better, use Data.List.Spit:

everyNth n = (map head) . chunksOf n
0

Old question but I'll post what I came up with:

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

I put the list argument before the Int so I can curry the function and a list then map that over a list of Ints if ever I need to.

0

It's more elegant to solve a related problem first: Keep every element whose index is divisible by n.

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

And then to solve the example, use

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

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

2
  • Hmm I get Prelude> everyNthFirst 3 $ take 10 [1..] [3,7*** Exception: <interactive>:2:1-48: Non-exhaustive patterns in function everyNth in GHCi (ghc 8.4.3). Compiling into a short program though, I get [2,6,10,14,18,22,26,30,34,38,42,46] if I do putStrLn $ show $ everyNthFirst 3 $ take 50 $ [0..]. The correct behavior should instead be [2, 5, 8, 11, ...] right? Commented Nov 18, 2018 at 18:05
  • 1
    Thanks. I fixed the bug, should work. If you want to try in ghci, put both equations of the definition on one line separated by semicolon ; otherwise you define two functions, with the second shadowing the first.
    – Matthias
    Commented Nov 20, 2018 at 13:27
0

Data.List.HT from utility-ht has sieve :: Int -> [a] -> [a].

See documentation and 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
0

And a very functional one without apparent conditionals:

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

(Note, this one takes every element whose index is a multiple of n. Which is slightly different from the original question, but easy to convert.)

0

We can use a list comprehension:

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

From all value-index pairs (x, i), take x if i is divisible by n. Note that the index starts from one here.

-1

My solution is:

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

It do not use zip but I can't tell about it's performances and memory profile.

1
  • 1
    This code does not work. E.g. every 3 [1,2,3,4,5,6] yields [[1,2,3],[4,5,6]]
    – Eugen
    Commented Feb 4, 2011 at 21:54
-1

An uglier, and more limited version of the accepted answer

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

For "line golfing" it can be written like this:

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

(It's more limited because it has an unnecessary Eq a constraint.)

2
  • 2
    What's the point in contributing an uglier version of an accepted answer? To appreciate the accepted answer more? :-) Commented Apr 21, 2012 at 17:17
  • Ugly functions need love, too ;).
    – Eugen
    Commented Mar 29, 2018 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.