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

Мне не с чем это проверять на работе, но что-то вроде:

extractEvery m = map snd . filter (\(x,y) -> (mod x m) == 0) . zip [1..]

должно работать даже на бесконечных списках.

(Edit: test and corrected.)

]Используйте шаблон просмотра![

{-# LANGUAGE ViewPatterns #-}

everynth n (drop (n-1) -> l)
  | null l = []
  | otherwise = head l : everynth n (tail l)

]Уродливая версия ответа Нефрубира сохранилась, поэтому комментарии имеют смысл.[

everynth :: Int -> [a] -> [a]
everynth n l = case splitAt (n-1) l of
                 (_, (x:xs)) -> x : everynth n xs
                 _           -> []

]Компилятор или интерпретатор вычислит размер шага (вычитая 1, так как он основан на нулях):[

f l n = [l !! i | i <- [n-1,n-1+n..]]

][]Отчет Haskell 98: Arithmetic Sequences[][

Альтернативное решение для избавления от мода :

extractEvery n = map snd . filter ((== n) . fst) . zip (cycle [1..n])

Другой способ сделать это:

takeEveryM m lst = [n | (i,n) <- zip [1..] lst, i `mod` m == 0]

Еще один:

import Data.List

takeEveryMth m = 
  (unfoldr g)  . dr
     where 
       dr = drop (m-1)
       g (x:xs) = Just (x, dr xs)
       g []     = Nothing

Все решения, использующие zip и т. Д., Делают массу ненужных выделений. Как функциональный программист, вы хотите выработать привычку не выделять память, если в этом нет необходимости. Распределение дорого, и по сравнению с распределением все остальное бесплатно. И распределение не просто появляется в «горячих точках», которые можно найти с помощью профилировщика; если вы не обращаете внимания на распределение, оно убивает вас везде .

Теперь я согласен с комментаторами, что удобочитаемость - это самое главное . Никто не хочет быстро получать неправильные ответы. Но в функциональном программировании очень часто бывает, что существует несколько решений, все примерно одинаково читаемых, некоторые из которых выделяются, а некоторые нет. Очень важно выработать привычку искать эти читаемые решения без выделения памяти .

Вы могли подумать, что оптимизатор избавится от выделения памяти, но вы были правы только наполовину. GHC, лучшему в мире оптимизирующему компилятору для Haskell, удается избежать выделения пары на элемент; он объединяет композицию filter - zip в foldr2 . Размещение списка [1 ..] остается. Возможно, вы не думаете, что это так уж плохо, но слияние потоков, которое является современной технологией GHC, является несколько хрупкой оптимизацией. Даже экспертам сложно предсказать, когда это сработает, просто взглянув на код. Более общий момент заключается в том, что когда дело доходит до критического свойства, такого как распределение, вы не хотите полагаться на причудливый оптимизатор, результаты которого вы не можете предсказать . Пока вы можете писать свой код одинаково удобочитаемым способом, вам гораздо лучше никогда не вводить эти распределения.

По этой причине я считаю решение Нефрубира, использующее drop , безусловно, наиболее убедительным. Выделяются только те значения cons-ячеек (с : ), которые должны быть частью окончательного ответа. Кроме того, использование drop делает решение не просто простым для чтения: оно кристально чистое и, очевидно, правильное.

Начиная с первого элемента:

everyf n [] = []
everyf n as  = head as : everyf n (drop n as)

Начиная с n-го элемента:

every n = everyf n . drop (n-1)

Ответ Мхариса великолепен. Но мне нравится избегать использования \ , поэтому вот мой гольф:

extractEvery n
  = map snd . filter fst
  . zip (cycle (replicate (n-1) False ++ [True]))

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

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

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

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

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

каждый n = карта (!! (N-1)). Итерация (падение n)

Я носил мою версию Haskell на днях, настолько непроверен, но следующее кажется немного более простым, чем другие (использующие сопоставление шаблонов и падение, чтобы избежать Zip и мода):

everynth :: Int -> [a] -> [a]
everynth n xs = y : everynth n ys
         where y : ys = drop (n-1) xs

extractEvery n l = la tête de carte (réitèrent (laissent tomber n) (la goutte (n-1) l))

j'allais sentir fier de moi-même, jusqu'à ce que j'aie vu que Greg est arrivé de la même réponse et avant moi