Как получить каждый N-й элемент бесконечного списка в Haskell?

Question

Более конкретно, как мне сгенерировать новый список каждого N-го элемента из существующего бесконечного списка?

например. если список равен [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ...], то получение каждого третьего элемента приведет к этому списку [0,0,0,0,0 ...]

Answer 1

Явная рекурсия - это зло! Вместо этого используйте библиотечную конструкцию, такую ​​как карта, фильтр, сложить, отсканировать, воспроизвести, повторить и т. Д. Если это не делает код значительно более легким для чтения даже для тех, кто на самом деле работает с библиотеками, то это просто делает ваш код менее модульным, более подробным и более сложным для рассуждений.

Серьезно, за явно рекурсивные версии нужно проголосовать отрицательно за такую ​​простую задачу, как эта. Теперь я думаю, что должен сказать что-то конструктивное, чтобы уравновесить мой карп.

Я предпочитаю использовать карту:

каждый n xs = карта (xs !!) [n-1, n-1 + n ..]

, а не понимание списка ja, так что читателю не нужно беспокоиться о том, кто я. Но в любом случае это O (n ^ 2), когда это может быть O (n), так что, возможно, это лучше:

каждый n = карта (!! (n-1)). повторение (исключение n)

Answer 2

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

Я собирался гордиться собой, пока не увидел, что Грег получил примерно такой же ответ и до меня

Answer 3

Немного глупая версия с 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)

Answer 4

И очень функциональный без очевидных условий:

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

(Обратите внимание, что этот элемент принимает каждый элемент, индекс которого кратен n. Это немного отличается от исходного вопроса, но его легко конвертировать.)

Answer 5

Data.List.HT из utility-ht имеет sieve :: Int -> [a] -> [a].

См. документацию и источник :

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

Answer 6

Сначала проще решить связанную проблему: сохранить каждый элемент, индекс которого делится на n.

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

А затем, чтобы решить пример, используйте

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

everyNthFirst 3 [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ...] дает [0, 0, 0, ...]

Answer 7

Многие ответы здесь уже используют Data.List.unfoldr, но я хотел бы предложить интересный способ написания несколько раздражающего раскрытия, которое может быть полезно в других контекстах:

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

Если список пуст, listToMaybe возвращает Nothing, а fmap аналогично будет Nothing. Однако если создается Just, то правильный кортеж создается путем превращения заголовка списка в кортеж заголовка и остальных значений, которые будут использоваться в следующей итерации.

Answer 8

Старый вопрос, но я выложу, что я придумал:

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

Я поставил аргумент list перед Int, чтобы я мог каррировать функцию и список, а затем сопоставить его со списком Int s, если мне когда-либо понадобится.

Answer 9

Это выглядит немного лучше, если использовать развертывание:

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

Или, что еще лучше, используйте Data.List.Spit:

everyNth n = (map head) . chunksOf n

Answer 10

Более уродливый и более ограниченный вариант принятого ответа

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

Для "игры в гольф" это можно записать так:

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

(он более ограничен, потому что имеет ненужное ограничение Eq a.)