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

Question

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

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

Answer 1

Моя версия с использованием drop:

every n xs = case drop (n-1) xs of
              (y:ys) -> y : every n ys
              [] -> []

Редактировать: это также работает для конечных списков. Только для бесконечных списков решение Чарльза Стюарта немного короче.

Answer 2

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

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

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

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

Answer 3

У меня нет ничего, чтобы проверить это на работе, но что-то вроде:

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

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

(Правка: проверено и исправлено.)

Answer 4

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

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

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

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

Answer 5

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

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

Отчет на Haskell 98: арифметические последовательности

Answer 6

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

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

Answer 7

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

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

Answer 8

Альтернативный раствор для избавления от mod:

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

Answer 9

Еще один способ сделать это:

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

Answer 10

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

{-# 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
                 _           -> []