如何在列表的長度上遞歸地調用一個函數？

Question

我有一個面試問題，從那時起它一直在竊聽我。

我有一個函數，填充，做計算就像取兩個列表，然後在第二個列表中替換2s，其中第一個列表中有2個，並且第一個列表中的第二個列表中還有一個2s被填充列表，那麼它可以流動直到遇到1。例如：

兩個列表[2,1,2,1,2][0,0,1,0,0]通過了，所以我得到的輸出是[2,2,1,2,2]。現在，我想寫一個函數，它的參數是這樣的：[[2,1,2,1,2],[0,0,1,0,0],[0,0,0,0,0]]，我想遞歸地應用我的上面的函數，直到這個列表的末尾。所以像第一個[2,1,2,1,2][0,0,1,0,0]都通過填寫，那麼它應該得到結果[2,2,1,2,2]，那麼應該通過[2,2,1,2,2]和[0,0,0,0,0]，得到結果[2,2,2,2,2]。我怎樣才能做到這一點？

編輯：

我這樣做：

fillAll::[[Int]]->[Int] 
fillAll [] = [] 
fillAll (x:xs) = 
    (foldl' seep x xs) $ 
    helper2 x 


helper2:: [Int] -> Bool 
helper2 lst = 
    if 2 `elem` lst then True else False 

Answer 1

所以，你有你的功能fill：

fill :: [Int] -> [Int] -> [Int] 

而且要打開這個後者採用列表的功能列表：

fillRec :: [[Int]] -> [Int] 

這是一個摺疊的自然案例。這個重複使用組合函數「摺疊」列表中的每個元素。我們需要確保該列表不爲空：

fillRec [] = [] 
fillRec (x : xs) = foldl fill x xs 

這個版本的foldl（例如褶皺從左邊，而不是右邊）是不嚴格的，這可能會導致大內存的積累。這是更好地從Data.List用嚴格的方式foldl'：

fillRec (x : xs) = foldl' fill x xs 

Answer 2

我會假設你已經有fill :: [Int] -> [Int] -> [Int]定義。如果是這樣，使用fold這個問題很容易解決。明確地說，你可以不喜歡

fillAll :: [[Int]] -> [Int] 
fillAll [] = [] 
fillAll (x:xs) = go x xs 
    where 
     go first [] = first 
     go first (second:rest) = go (fill first second) rest 

或者你可以使用內置的fold S的一個：

fillAll [] = [] 
fillAll (x:xs) = foldl fill x xs 

但Impredicative所指出的，你將有更好的性能foldl'從數據.List