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 ...]
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.
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.
Commented
Oct 20, 2013 at 14:01
[] -> []
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
[] -> []
should come before (y:ys) -> y : every n ys
.
Commented
Feb 5, 2016 at 6:04
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.
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.)
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)
everyf n = map head . takeWhile (not . null) . iterate (drop n)
or every n = map head . takeWhile (not . null) . iterate (drop n) . drop (n-1)
.
Commented
Jan 8, 2010 at 18:39
. 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... :)
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..]]
l
's retention in memory - prevents l
from being garbage collected, from being made ephemeral and not being allocated at all.
Commented
Oct 26, 2017 at 9:05
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]))
cycle $ replicate (n-1) False ++ [True]
since OP wants to start at index n-1
, not index 0
.
Commented
Jan 8, 2010 at 18:37
Alternate solution to get rid of mod
:
extractEvery n = map snd . filter ((== n) . fst) . zip (cycle [1..n])
mod
, ==
, what's the difference? still doing tests with predictable results... I don't think you'd code it like this, today. :)
Commented
Oct 26, 2017 at 9:16
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
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
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)
!!
, 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
.
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
_ -> []
splitAt
instead of drop
if you never even look at the fst
of the resulting tuple.
Commented
Jan 9, 2010 at 6:30
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...
Commented
Jan 9, 2010 at 7:23
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.
Commented
Jan 9, 2010 at 8:32
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
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.
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)
GHC.List.build
around this to make it fuse the other way too.
(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]
n
as a leftmost parameter of your every'
function, as it is constant and provided by the outer scope.
Commented
Oct 31, 2020 at 10:55
every n = every' n (n-1)
, or, as @jpmarinier points out, even every n = every' (n-1)
.
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
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 Int
s if ever I need to.
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, ...]
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
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
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.)
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.
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.
every 3 [1,2,3,4,5,6]
yields [[1,2,3],[4,5,6]]
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.)