CODEWITHSUNDEEP
haskell
Arushi
Arushi

Reputation: 85

Every n-th element of a list in the form of a list

I went through a post for this problem but I do not understand it. Could someone please explain it?

Q: Find every n-th element of the list in the form of a list start from the n-th element itself.

everyNth :: Int -> [t] -> [t]
everyNth elt = map snd . filter (\(lst,y) -> (mod lst elt) == 0) . zip [1..]

Also, please explain how pattern matching can be used for this problem. That is using

[]->[]

Upvotes: 1

Views: 1334

Answers (4)

Michael
Michael

Reputation: 2909

It's easy to use pattern matching to 'select every nth element' for particular cases of n:

every2nd (first:second:rest) = second : every2nd rest
every2nd _ = []
-- >>> every2nd [1..12]
-- [2,4,6,8,10,12]

every3rd (first:second:third:rest) = third : every3rd rest
every3rd _ = []
-- >>> every3rd [1..13]
-- [3,6,9,12]

every4th (first:second:third:fourth:rest) = fourth : every4th rest
every4th _ = []
-- >>> every4th [1..12]
-- [4,8,12]

For the general case, though, we're out of luck, at least with that particular approach. Patterns like those above will need some definite length to be definite patterns. The composed function you mention starts from the thought that we do know how to find every nth member of [1..], namely if it's a multiple of n

multiple n m = m `mod` n == 0
-- >>> filter (multiple 3) [1..12]
-- [3,6,9,12]

So the solution you are trying to understand zips [1..] with the list

index xs = zip [1..] xs
-- >>> index [1..5]
-- [(1,1),(2,2),(3,3),(4,4),(5,5)]
-- >>> index "hello"
-- [(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')]

Then it filters out just those pairs whose first element is a multiple of n

every_nth_with_index n xs = filter (\(m,a) -> multiple n m) (index xs)
-- >>> every_nth_with_index 3 [1..12]
-- [(3,3),(6,6),(9,9),(12,12)]
-- >>> every_nth_with_index 3 "stackoverflow.com"
-- [(3,'a'),(6,'o'),(9,'r'),(12,'o'),(15,'c')]

Then it gets rid of the ancillary construction, leaving us with just the second element of each pair:

every_nth n xs = map snd (every_nth_with_index n xs)
-- >>> every_nth 3 [1..12]
-- [3,6,9,12]
-- >>> every_nth 3 "stackoverflow.com"
-- "aoroc"

Retracinging our steps we see that this is the same as 

everyNth elt = map snd . filter (\(lst,y) -> (mod lst elt) == 0) . zip [1..]

Upvotes: 4

Paul Johnson
Paul Johnson

Reputation: 17786

If you have never seen Haskell before then this takes a bit of explaining.

everyNth :: Int -> [t] -> [t]
everyNth elt = map snd . filter (\(lst,y) -> (mod lst elt) == 0) . zip [1..]

First, note that the type has two arguments, but the definition has only one. This is because the value returned by everyNth is in fact another function. elt is the Int, and the expression in the second line creates a new function that does the job.

Second, note the "." operators. This is an operator that joins two functions together. It is defined like this:

(f . g) x = f (g x)

Here is an equivalent version of the definition with the second argument made explicit:

everyNth elt xs = map snd (filter (\(lst y) -> (mod lst elt) == 0) (zip xs))

When you see a bunch of functions in a chain linked by "." operators you need to read it from right to left. In my second version pay attention to the bracket nesting. zip [1..] xs is the inner-most expression, so it gets evaluated first. It turns a list like ["foo", "bar"] into [(1, "foo"),(2, "bar")]. Then this is filtered to find entries where the number is a multiple of elt. Finally the map snd strips the numbers back out to return just the required entries.

Upvotes: 2

chepner
chepner

Reputation: 532053

With a little cheating, you can define everyNth using pattern matching. Really, we're abstracting out the part that makes pattern matching difficult, as pointed out in Michael's answer.

everyNth n lst = e (shorten lst)
                 where shorten = drop (n-1) -- here's the cheat
                       e [] = []
                       e (first:rest) = first : e (shorten rest)

Upvotes: 3

dfeuer
dfeuer

Reputation: 48611

The notorious fold fan strikes again.

everyNth n xs = foldr go (`seq` []) xs n where
  go x r 0 = x : r (n - 1)
  go _ r k = r (k - 1)

This is very similar to chepner's approach but it integrates the dropping into the recursion. Rewritten without the fold, it's pure pattern matching:

everyNth n = go n where
  go k [] = k `seq` []
  go 0 (x : xs) = x : go (n - 1) xs
  go k (_ : xs) = go (k - 1) xs

Upvotes: 3

Related Questions