How to select every n-th element from a list [duplicate]

Question

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

Simple task - we have a list and want to leave only each nth element in that list. What is the most idiomatic way to do it in haskell?

off the top of my head it is something like:

dr n [] = []
dr n (x : xs) = x : (dr n $ drop n xs)

but I have a strong feeling that I'm overcomplicating the problem.

Answer 1

My variant would be:

each :: Int -> [a] -> [a]
each n = map head . takeWhile (not . null) . iterate (drop n)

Fast and plays well with laziness.

Answer 2

Your solution is fine, but here are three other solutions using functions from Haskell's base library.

dr1 m = concatMap (take 1) . iterate (drop m)

Of coarse, this will never terminate (because iterate never terminates). So perhaps a better solution would be to use unfoldr:

{-# LANGUAGE TupleSections #-}
import Data.Maybe
dr2 m = unfoldr ((\x-> fmap (,drop m x) (listToMaybe x)))

The function you pass to an unfold can get a bit ugly if you don't know GHC extensions and concepts such as functors, here's that solution again without the fancy foot-work (untested):

dr2 m = unfoldr ((\x -> case listToMaybe x of
                         Nothing -> Nothing
                         Just i  -> Just (i,drop m x)))

If you don't like unfolds then consider a zip and a filter:

dr3 m = map snd . filter ((== 1) . fst) . zip (cycle [1..m])

Review

Understand all these solutions are slightly different. Learning why will make you a better Haskell progammer. dr1 uses iterate and will thus never terminate (perhaps this is ok for infinite lists, but probably not a good overall solution):

> dr1 99 [1..400]
[1,100,199,298,397^CInterrupted.

The dr2 solution will show every mth value by skipping values in the unfold. The unfold passes both the value to be used for the next unfolding and the result of the current unfolding in a single tuple.

> dr2 99 [1..400]
[1,100,199,298,397]

The dr3 solution is slightly longer but probably easier for a beginner to understand. First you tag every element in the list with a cycle of [1..n, 1..n, 1..n ...]. Second, you select only the numbers tagged with a 1, effectively skipping n-1 of the elements. Third you remove the tags.

> dr3 99 [1..400]
[1,100,199,298,397]