有一個組合謎題（如Jan Gullberg 的Mathematics From the Birth of Numbers 中提到的），如果您將來自兩個類別的 15 個成員（例如類別的015個和類別的15 個，1總共30元素）按特定順序排列在一起，那么如果你以回圈方式連續沿著這條線走（即當你到達終點時繞回到起點，繼續計數）每九個元素都扔掉，你最終只會得到一個元素“喜歡” ( 1) 類別
line = [1,1,1,1,0,0,0,0,0,1,1,0,1,1,1,...]
line （請參閱下面的游程編碼元組版本）是實際排序，如果您每九個就扔掉一次，
line = [1,1,1,1,0,0,0,0,1,1,0,1,1,1,...] -- 9th thrown out
你總是會扔掉“不受歡迎的” 0。如果從 RLE 元組的角度來看（其中對或 the 的連續出現進行(0|1, n)編碼），（遞減）從 tuple ，即遞減，你最終會得到只有元組，當然扔掉完全耗盡的元組作為好吧，并在您進行時重新壓縮串列n01(0,x)x(1,y)(0,0)
line = [(1,4),(0,5),(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1)]
我有這個開始
tally = foldl (\acc elem -> if (snd(elem) acc) >= 9
then (snd(elem) acc)-9
else (snd(elem) acc)) 0
當我喂它的時候 line
tally [(1,4),(0,5),(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1)]
它獲取4第一個元組的 ，然后添加5第二個元組的 ，獲取9并重置累加器以再次開始“倒計時”。所以它準確地回傳3，實際上，這是經過一次傳遞并用第九個識別元組并重置累加器后累加器的剩余部分。我的明顯問題是如何超越僅僅識別第九個元素，實際上開始遞減0元組的元素，以及在它們下降(0,0)并重新運行時將它們扔掉。我敢肯定，將其構建line為更容易
line = [1,1,1,1,0,0,0,0,0,1,1,0,1,1,1,...]
并開始夾住（即洗掉）第九個，再次，它應該始終是一個0元素，（例如，第一個第九個已經從line
line = [1,1,1,1,0,0,0,0,1,1,0,1,1,1,...]
但這更多的是一個挑戰，因為我本質上需要一個折疊來與地圖相結合——這正是我想要學習的，即純粹的功能性、無計數器等風格。提示和幫助表示贊賞。此外，如果組合學知識中的某個人可以對這里發生的事情提供一些理論啟示，那也很好。
uj5u.com熱心網友回復：
尋找地圖和折疊可能是過度約束的事情，因為這里有一個可愛的簡潔功能供您開始：
-- Remove the n-th element (zero-indexed) of a run-length encoded sequence of a.
chuck :: Int -> [(a, Int)] -> [(a, Int)]
扔掉空箱子；我們不應該在這里。
chuck _ [] = error "unexpected empty list"
讓我們計算一下chuck n ((a,m) : l)。我們面臨m相同的元素a，我們想洗掉第n-th 個元素。這取決于是否n < m（即，搜索是在這些m元素的中間還是之后停止）。
如果n < m，那么我們將洗掉其中之一a。我們還可以為下一個周期準備結果，在a我們洗掉后立即恢復。我們實際上已經跳過了n它之前的其他元素，存盤這些n元素的好地方是串列的末尾，因為無論如何我們都應該在末尾回圈。如果我們想計算圈數，我們需要更復雜的東西，但除非另有說明，否則，YAGNI。仍有m-n-1元素，留在前面。rpt在我們嘗試添加零元素的情況下，一個小助手會有所幫助。
otherwise，我們跳過所有m元素，將它們存盤在后面，我們還有n-m更多內容要做。
chuck n ((a,m) : l)
| n < m = rpt a (m-n-1) l rpt a n
| otherwise = chuck (n-m) (l [(a,m)])
where rpt a 0 = []
rpt a n = [(a,n)]
（注：這將裂變(a,m)成(a,m-n-1)和(a,n)，但不會合并他們回來......作為練習留給讀者。）
由于結果是為下一次迭代準備的，我們可以很容易地通過鏈接chuck來查看線路的演變。請注意，在此實作中元素是零索引的，因此chuck 8洗掉“第九個”元素。
ghci
> line
[(1,4),(0,5),(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1)]
> chuck 8 line
[(1,2),(0,1),(1,3),(0,1),(1,1),(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1),(1,4),(0,4)]
> chuck 8 $ chuck 8 line
[(0,1),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1),(1,4),(0,4),(1,2),(0,1),(1,3),(0,1),(1,1)]
這有點難以遵循。至少，我們應該確保只有0's 被丟棄。那么讓我們計算一下元素：
tally :: [(Int,Int)] -> (Int, Int)
tally xs = (sum (map snd (filter ((== 0) . fst) xs)), sum (map snd (filter ((== 1) . fst) xs)))
正如預期的那樣，計數的右側似乎保持不變，而錯誤的一側較少：
> tally line
(15,15)
> tally $ chuck 8 line
(14,15)
> tally $ chuck 8 $ chuck 8 line
(13,15)
我們可以使用 更快iterate，它重復應用一個函式并在無限串列中回傳所有中間結果：
> :t iterate
iterate :: (a -> a) -> a -> [a]
迭代chuck 8，統計，只看我們期望停止的地方（在洗掉一側的所有 15 個元素之后）：
> take 16 $ map tally $ iterate (chuck 8) line
[(15,15),(14,15),(13,15),(12,15),(11,15),(10,15),(9,15),(8,15),(7,15),(6,15),(5,15),(4,15),(3,15),(2,15),(1,15),(0,15)]
uj5u.com熱心網友回復：
使用 RLE 會使事情復雜化。您所需要的只是計數：
line = [(1,4),(0,5),(1,2),(0,1),(1,3),(0,1),(1,1),
(0,2),(1,2),(0,3),(1,1),(0,2),(1,2),(0,1)]
unRLE rle = [c | (c,n) <- rle, c <- replicate n c]
test = count9 1 15 [] $ unRLE line
count9 _ 0 rev line = reverse rev line
count9 9 n rev (0:xs) = count9 1 (n-1) rev xs
-- removing 1 is error:
count9 9 n rev (1:xs) = error "attempt to remove 1"
count9 i n rev (x:xs) = count9 (i 1) n (x:rev) xs
count9 i n rev [] = count9 i n [] (reverse rev)
運行它
> test
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
如果您想查看line每個0被洗掉的狀態，您將需要調整它。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/389032.html