反向列表使用map/reduce

Question

我正在學習函數式編程的概念並嘗試練習問題。 練習， 使用map/reduce顛倒一個列表。 我的解決方案：

lists = [ 1, 2, 3, 5 ,6] 

def tree_reverse(lists): 
    return reduce(lambda a, x: a + [a.insert(0,x)], lists, []) 

print tree_reverse(lists) 

輸出：

[6, 5, 3, 2, 1, None, None, None, None, None] 

我不明白爲什麼有諾內斯等於列表中元素的個數。

編輯：擴展問題的情況下嵌套列表。

lists = [ 1 ,2 ,3 , [5,6,7], 8, [9, 0, 1 ,4 ]] 

Answer 1

起初，我不知道Python的不夠好，但你打上了一個問題，「功能編程」，你說你想在一般的瞭解我想對你的問題給出一些一般的解釋。 首先，您應該重新思考map和reduce的操作以及他們的期望。我們從map函數開始。

A map函數列表（在函數式編程中，您不只有一個映射，每個泛型類型都有一個映射）對每個參數執行一個函數。該函數可以對單個參數進行操作並對其進行轉換。這一轉變的結果變成了新的清單。一個重要的注意事項是，您傳遞給map的功能只能看到一個元素，因此您不能使用map本身來整體轉換列表。你只能轉換列表中的每一個元素。但改變順序需要有一個列表中至少有兩個元素的想法，而一個地圖只能獲得一個元素。這就是反向邏輯不能在map中並且必須是reduce操作的一部分的原因。

另一方面，reduce函數需要一個函數，它接受兩個相同類型的東西，並返回一個相同類型的單個項目。例如reduce函數可以採用「+」函數。 「+」是一個函數，它需要兩個int並返回一個新的int。簽名基本上是int + int = int。減少的本質是把兩件事情變成一件新事物。例如，如果您的例子有類似「Foo」的更復雜的東西，那麼您必須提供的函數才能減少需要簽名Foo * Foo -> Foo。意思是以Foo作爲第一和第二個參數，並返回一個新的Foo。

同樣重要的是要注意reduce將如何與該功能的工作。讓我們假設你有上名列榜首[1,2,3,4,5]讓我們假設你有一個accumulator function帶兩個int，只是將它們相加。你能想到會發生什麼是以下幾點。

1. 的reduce函數採用列表的前兩個參數（1和2在這種情況下）
2. 通行證那些在所述accumulator function（1 + 2 = 3）
3. 並取代兩個參數列出結果。 [3,3,4,5]
4. 回到1），並重復這一過程，直到你的名單隻有一個單一的項目
5. 返回的是單個項目

所以你可以想像會發生什麼是以下

[1,2,3,4,5] -> 1 + 2 = 3 
[3,3,4,5] -> 3 + 3 = 6 
[6,4,5]  -> 6 + 4 = 10 
[10,5]  -> 10 + 5 = 15 
[15]  -> Return just "15". Not a "[15]" 

其實進程內部通常工作有點不同。但是這是你可以想象發生什麼的過程。請務必注意，您從不修改列表。你總是在那個過程中創建新的列表。另一個重要說明。在reduce函數的末尾，您有一個單個項目的列表。但reduce函數不會返回整個列表。它只返回單個元素。所以你得到15和int。您沒有得到包含15的單個項目的列表。 Reduce將只返回那個單個元素。不管是什麼。另一種思考方式。你總是得到你的accumulator function的類型。如果你傳遞一個accumulator function採用兩個int增加了他們，並返回一個新int。您的減少功能也將返回一個int。如果你傳遞一個accumulator function，它有兩個Foo類，並返回一個新Foo。作爲結果，您的reduce函數也將返回Foo。 reduce的退貨類型始終與您的accumulator function的類型相同。

現在，讓我們所有的碎片，把它們放在一起。目標是扭轉一個列表。第一件重要的事情是。您的結果類型將是list。這也意味着您傳遞到reduce的功能也必須返回list。但是由於輸入始終與輸出相同。您現在必須提供一個帶有兩個列表的accumulator function，並返回一個新的列表。

但現在，讓我們退後一步。如果直接使用列表「[1,2,3,4,5]」作爲輸入來減少，會發生什麼？簡單的答案是，它不會起作用。 reduce將採用您的列表的兩個參數。但是你有什麼是int列表。但你的accumulator function期望兩個列表不是兩個int。爲了解決這個問題，你現在可以做的就是將列表中的每一個單元轉換成它自己的列表。那麼我們如何變換列表中的每一個元素呢？對！用map！所以你必須做的是以下幾點。您首先將您的列表映射到列表的列表中。

[1,2,3,4,5] -> [[1],[2],[3],[4],[5]] 

現在你的reduce函數得到你的第一個列表的前兩個元素。這意味着您現在有一個累加器函數，它獲取[1]和[2]作爲它的參數。兩個單獨的名單。但是你的累加器函數必須返回一個新的列表。如果不清楚，只是提醒累加器函數帶回的。

int, int -> int 
float,float -> float 
Foo,Foo  -> Foo 
list,list -> list 

所以你現在要做的就是將這兩個列表合併成一個新的列表。換句話說，你必須追加/連接這兩個列表。我不知道你如何在Python中連接兩個列表讓我們假設這裏的操作是「++」。所以如果你僅僅連接第一個參數和第二個參數，你就不會得到你想要的。

[[1],[2],[3],[4],[5]] -> [1]  ++ [2] = [1,2] 
[[1,2],[3],[4],[5]] -> [1,2]  ++ [3] = [1,2,3] 
[[1,2,3],[4],[5]]  -> [1,2,3] ++ [4] = [1,2,3,4] 
[[1,2,3,4],[5]]  -> [1,2,3,4] ++ [5] = [1,2,3,4,5] 
[[1,2,3,4,5]]   -> Return first element [1,2,3,4,5] 

所以你要做的是將第二個參數連接到第一個參數。

[[1],[2],[3],[4],[5]] -> [2] ++ [1]  = [2,1] 
[[2,1],[3],[4],[5]] -> [3] ++ [2,1]  = [3,2,1] 
[[3,2,1],[4],[5]]  -> [4] ++ [3,2,1] = [4,3,2,1] 
[[4,3,2,1],[5]]  -> [5] ++ [4,3,2,1] = [5,4,3,2,1] 
[[5,4,3,2,1]]   -> Return first element [5,4,3,2,1] 

現在你得到的是你的反轉列表。所以你有什麼待辦事項

1. 將每個元素映射到列表。所以，你得到的目錄列表
2. 使用減少列表的每個列表Concat的到以相反的順序一個新的列表。

例如，在F＃整個代碼是這樣的。

let list = [1;2;3;4;5] 

let reversed = 
    list 
    |> List.map (fun x -> [x]) // map every element to a list 
    |> List.reduce (fun xs ys -> List.append ys xs) // Note ys ++ xs - reversed order for appending 

printfn "%A" reversed 
// prints: [5;4;3;2;1] 

我想你應該可以把它翻譯成Python。作爲進一步通知。在函數式編程中，執行「映射」和「連續」操作（不反轉）也稱爲「綁定」。

Answer 2

你減少操作追加None到列表a結束，因爲a.insert(0,x)將返回None。

因此，您正在修改列表a，但在同一時間附加了None值。

如果你重寫你的reduce操作使用for循環，它會看起來像：

def reverse_list(lists): 
    r = [] 
    for x in lists: 
     val = r.insert(0,x) 
     r = r + [val] # val (the return value of r.insert) is None 
    return r 

Answer 3

在嵌套列表的情況。我張貼答案供參考。

lists = [ 1 ,2 ,3 , [5,6,7], 8, [9, 0, 1 ,4 ]] 

def tree_reverse(lists): 
    return reduce(lambda a, x: (map(tree_reverse, [x]) if isinstance(x,list) else [x]) + a , lists , []) 

print tree_reverse(lists) 

輸出：

[[4, 1, 0, 9], 8, [7, 6, 5], 3, 2, 1] 

Answer 4

函數式編程語言會經常使用遞歸來實現迭代。

遞歸tree_reverse功能可能看起來像

def tree_reverse(lists): 
    return tree_reverse(lists[1:]) + [lists[0]] if lists else [] 

如果你看看哈斯克爾它可能像這樣

reverse' :: [a] -> [a] 
reverse' [] = [] 
reverse' (x:xs) = reverse' xs ++ [x] 

凡x是列表的頭（第一個元素）和實現xs是尾部（列表減去頭部），您可以看到reverse'被遞歸調用，這些元素顛倒並且迭代地構建反轉列表。