如何從列表中選擇每第n個元素

可能重複：
How to get every Nth element of an infinite list in Haskell?如何從列表中選擇每第n個元素

簡單的任務 - 我們有一個列表，並希望只留下每個第n個元素在該列表。哈斯克爾最習慣的方式是什麼？

了我的頭頂部是這樣的：

dr n [] = [] 
dr n (x : xs) = x : (dr n $ drop n xs)

，但我有我的過分複雜問題的一種強烈的感覺。

來源

2011-09-29 shabunc

小艾習慣給我。 –

不認爲你會得到這個更便宜 - 看起來很好。唯一的一點是，這不符合你的描述，因爲'dr k [1 ..]'不會產生你的問題序列。 – Carsten

你的解決方案是好的，但這裏有三個其他解決方案使用Haskell的基礎庫函數。

dr1 m = concatMap (take 1) . iterate (drop m)

粗糙的，這永遠不會終止（因爲iterate永遠不會終止）。因此，也許一個更好的解決辦法是使用unfoldr：

{-# LANGUAGE TupleSections #-} 
import Data.Maybe 
dr2 m = unfoldr ((\x-> fmap (,drop m x) (listToMaybe x)))

傳遞給一個展開函數可以得到一個有點難看，如果你不知道GHC擴展和概念，如函子，下面的解決方法還是沒有花哨的腳工作（未經測試）：

dr2 m = unfoldr ((\x -> case listToMaybe x of 
         Nothing -> Nothing 
         Just i -> Just (i,drop m x)))

如果您不喜歡展開再考慮壓縮和過濾器：

dr3 m = map snd . filter ((== 1) . fst) . zip (cycle [1..m])

評論

瞭解所有這些解決方案都略有不同。學習爲什麼會讓你成爲更好的Haskell程序員。 dr1採用迭代，從而不會終止（也許這是確定的無限列表，但可能不是一個很好的整體解決方案）：

> dr1 99 [1..400] 
[1,100,199,298,397^CInterrupted.

的dr2解決方案將通過在展開跳過值顯示每m個值。展開將傳遞給下一個展開的值和當前展開的結果放在一個元組中。

> dr2 99 [1..400] 
[1,100,199,298,397]

dr3解決方案稍長一些，但對初學者來說可能更容易理解。首先用一個循環[1..n, 1..n, 1..n ...]來標記列表中的每個元素。其次，您只選擇標有1的數字，實際跳過元素的n-1。第三你刪除標籤。

> dr3 99 [1..400] 
[1,100,199,298,397]

來源

2011-09-29 16:03:25

托馬斯，非常感謝。瞭解你可以執行相對簡單的任務的所有方式非常重要，並且你剛剛給了我一些新的想法。 – shabunc

我的變種是：

each :: Int -> [a] -> [a] 
each n = map head . takeWhile (not . null) . iterate (drop n)

快速和懶惰打得很好。

來源

2011-09-29 16:11:25 ertes

這一個很好！ – shabunc

是的，這是非常好的。我不想討論懶惰（並且誠實地不考慮增加一名空檔警衛），但是這是我第一個破例的好選擇。 –

很多方法可以剃這個犛牛！這裏是另一個：

import Data.List.Split -- from the "split" package on Hackage 
dr n = map head . chunk n

來源

2011-09-29 18:37:09

塊非常相似，實際上' - | split = chunk :: Int - > [a] - > [[a]] chunk _ [] = [[]] chunk n xs = y1：chunk n y2 其中（y1，y2）= splitAt n xs' – shabunc

@shabunc你打賭！代碼重用是遊戲的名稱。 –

試試這個：

getEach :: Int -> [a] -> [a] 
getEach _ [] = [] 
getEach n list 
| n < 1  = [] 
| otherwise = foldr (\i acc -> list !! (i - 1):acc) [] [n, (2 * n)..(length list)]

然後在GHC：

*Main> getEach 2 [1..10] 
[10,8,6,4,2]

來源

2011-09-29 20:45:04 franza

該解決方案不適用於無限列表（因爲「長度列表」）;泄漏空間（它強制列表脊柱，但不會釋放列表的開始，直到它終止）;從列表中獲取元素是低效的（'!!'是O（n）;這是[Schlemiel the Painter's algorithm]（http://en.wikipedia.org/wiki/Schlemiel_the_Painter%27s_algorithm））;太複雜了。 – dave4420

如何從列表中選擇每第n個元素

回答

相關問題