Более конкретно, как мне сгенерировать новый список каждого N-го элемента из существующего бесконечного списка?
Например, если список [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0...] то получение каждого третьего элемента приведет к этому списку [0,0,0,0,0...]
Моя версия, использующая drop:
every n xs = case drop (n-1) xs of
(y:ys) -> y : every n ys
[] -> []
Изменить: это также работает для конечных списков. Только для бесконечных списков решение Чарльза Стюарта немного короче.
Все решения с использованием zip и т.д. делают тонны ненужных распределений. Как функциональный программист, вы хотите привыкнуть не выделять, если вам действительно не нужно. Распределение дорогое, и по сравнению с распределением все остальное бесплатное. И распределение не просто появляется в "горячих точках", которые вы найдете в профилировщике; если вы не обращаете внимания на распределение, оно убивает вас повсюду.
Теперь я согласен с комментаторами в том, что читаемость является самой важной вещью. Никто не хочет быстро получать неправильные ответы. Но в функциональном программировании очень часто случается, что существует несколько решений, все примерно одинаково читаемые, некоторые из которых выделяются, а некоторые из них - нет. Очень важно создать привычку искать эти читаемые, не выделяющие решения.
Вы могли бы подумать, что оптимизатор избавится от распределений, но вы будете только наполовину правы. GHC, лучший в мире оптимизирующий компилятор для Haskell, не позволяет выделять пару на элемент; он сплавляет композицию filter - zip в foldr2. Распределение списка [1..] остается. Теперь вы можете не думать, что это так плохо, но потоковое слияние, которое является современной технологией GHC, является несколько хрупкой оптимизацией. Это трудно даже для экспертов, чтобы точно предсказать, когда он собирается работать, просто взглянув на код. Более общий момент состоит в том, что , когда дело доходит до критического свойства, такого как выделение, вы не хотите полагаться на фантастический оптимизатор, результаты которого вы не можете предсказать. До тех пор, пока вы можете написать свой код одинаково читаемым способом, вам гораздо лучше не вводить эти распределения.
По этой причине я нахожу решение Nefrubyr с использованием drop, безусловно, наиболее убедительным. Единственными значениями, которые выделяются, являются именно те ячейки cons (с :), которые должны быть частью окончательного ответа. В дополнение к этому использование drop делает решение более чем просто читаемым: оно кристально ясно и, очевидно, правильно.
У меня нет ничего, чтобы проверить это на работе, но что-то вроде:
extractEvery m = map snd . filter (\(x,y) -> (mod x m) == 0) . zip [1..]
должен работать даже в бесконечных списках.
(Изменить: проверено и исправлено.)
Начиная с первого элемента:
everyf n [] = []
everyf n as = head as : everyf n (drop n as)
Начиная с n-го элемента:
every n = everyf n . drop (n-1)
Ответ MHarris велик. Но мне нравится избегать использования \, поэтому вот мой гольф:
extractEvery n
= map snd . filter fst
. zip (cycle (replicate (n-1) False ++ [True]))
Компилятор или интерпретатор вычислит размер шага (вычтите 1, поскольку он основан на нулевом значении):
f l n = [l !! i | i <- [n-1,n-1+n..]]
Альтернативное решение, чтобы избавиться от mod:
extractEvery n = map snd . filter ((== n) . fst) . zip (cycle [1..n])
Я обстрелял свою версию Haskell на днях, так что не тестировал, но следующее кажется немного проще, чем другие (использует сопоставление с образцом и отбрасывание, чтобы избежать zip и mod):
everynth :: Int -> [a] -> [a]
everynth n xs = y : everynth n ys
where y : ys = drop (n-1) xs
Другой способ сделать это:
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
Используйте шаблон представления!
{-# LANGUAGE ViewPatterns #-}
everynth n (drop (n-1) -> l)
| null l = []
| otherwise = head l : everynth n (tail l)
Уродливая версия ответа Nefrubyr сохраняется, поэтому комментарии имеют смысл.
everynth :: Int -> [a] -> [a]
everynth n l = case splitAt (n-1) l of
(_, (x:xs)) -> x : everynth n xs
_ -> []
Явная рекурсия - это зло! Вместо этого используйте библиотечную конструкцию, такую как map, filter, fold, scan, reproduce, итерация и т.д. Если это не делает код значительно проще читать даже для тех, кто работает с библиотеками, то он просто делает ваш код менее модульным, более подробным и сложнее рассуждать.
Серьезно, явно рекурсивные версии должны быть отклонены до отрицательного для простой задачи. Теперь, я думаю, я должен сказать что-то конструктивное, чтобы сбалансировать мое придирчивость.
Я предпочитаю использовать карту:
каждое n xs = map (xs!!) [n-1, n-1 + n..]
вместо понимания ja-списка, поэтому читателю не нужно беспокоиться о том, что я есть. Но в любом случае это O (n ^ 2), когда это может быть O (n), поэтому, возможно, это лучше:
каждое n = отображение (!! (n-1)). итерация (падение n)
extractEvery n l = map head (iterate (drop n) (drop (n-1) l))
Я собирался себя гордиться собой, пока не увидел, что Грег получил тот же ответ и передо мной
Немного глупая версия с 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)
(Это было в ответ на комментарий с просьбой найти решение без опозданий)
Я не мог видеть это решение, поэтому:
every _ [] = []
every n (x:xs) = every' n (n-1) (x:xs)
where every' n c [] = []
every' n 0 (x:xs) = x : every' n (n-1) xs
every' n c (x:xs) = every' n (c-1) xs
работает для конечного и бесконечного списка:
take 15 (every 3 [1..])
-- [3,6,9,12,15,18,21,24,27,30,33,36,39,42,45]
Более уродливый и более ограниченный вариант принятого ответа
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 ограничение.)
Это кажется немного лучше использовать разворачиваться:
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
Старый вопрос, но я напишу, что я придумал:
everyNth :: [a] -> Int -> [a]
everyNth xs n = [snd x | x <- (zip [1..] xs), fst x `mod` n == 0]
Я помещаю аргумент списка перед Int, поэтому я могу заархивировать функцию, а список затем отобразить ее над списком Int, если мне это нужно.
Многие ответы здесь уже используют 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
Когда список имеет значение null, listToMaybe возвращает Nothing, и fmap аналогично будет Nothing. Однако, если создается Just, то правильный кортеж создается путем превращения заголовка списка в кортеж заголовка и остальных значений для использования в следующей итерации.
Во-первых, более элегантно решить связанную проблему: сохранить каждый элемент, индекс которого делится на 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,...]
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
И очень функциональный без очевидных условий:
everyNth :: Int -> [a] -> [a]
everyNth 0 = take 1
everyNth n = foldr ($) [] . zipWith ($) operations where
operations = cycle $ (:) : replicate (n-1) (const id)
(Обратите внимание, что этот элемент принимает каждый элемент, индекс которого кратен n. Это немного отличается от исходного вопроса, но его легко конвертировать.)
Мое решение:
every :: Int -> [a] -> [[a]]
every _ [] = []
every n list = take n list : (every n $ drop n list)
Он не использует zip, но я не могу сказать о его характеристиках и профиле памяти.