未能使用foldl來逆轉Haskell中的列表

我知道如何使用遞歸來逆轉列表，但我正在嘗試使用foldl來使其更有效。我的代碼如下：未能使用foldl來逆轉Haskell中的列表

reverse list = foldl (++) [] (map (\x -> [x]) list)

當在GHCi中運行它時，它將返回與輸入相同的列表。出了什麼問題？我也試着用foldr來完成它，但它沒有顯示任何改變。

來源

2017-09-02 YM.Zhou

見https://stackoverflow.com/questions/26847192/reverse-a-list-in-haskell – icc97

的[反在Haskell列表]可能的複製（HTTPS ：//sackoverflow.com/questions/26847192/reverse-a-list-in-haskell） – icc97

@ icc97雖然在這個問題中給出了正確的'foldl'解決方案，但問題本身並不是真的，所以我不會說它是重複的。 – leftaroundabout

foldl將累加器作爲第一個參數傳遞給該函數。 ++將第一個參數連接到第二個參數，但是，要反轉列表，需要將第二個參數連接到第一個參數。您可以使用flip (++)做到這一點：

Prelude> let reverse list = foldl (flip (++)) [] (map (\x -> [x]) list) 
Prelude> reverse [1..5] 
[5,4,3,2,1]

來源

2017-09-02 09:18:34 Dogbert

「連接...到」是非定向的;混亂。「之前」會好很多。 –

取代先轉換列表中的所有元素獨居列表（這是昂貴的爲好），你可以使用利弊(:)功能：

reverse :: Foldable t => t a -> [a] 
reverse = foldl (flip (:)) []

所以這裏我們使用flip (:) :: [a] -> a -> [a]作爲摺疊函數。它需要一個尾部[a]和一個頭部a，並構建一個頭部作爲第一個元素和尾部作爲最後一個元素的列表。

那麼什麼情況是：

foldl (flip (:)) [] [1,4,2,5] 
-> foldl (flip (:)) (1:[]) [4,2,5] 
-> foldl (flip (:)) (4:1:[]) [2,5] 
-> foldl (flip (:)) (2:4:1:[]) [5] 
-> foldl (flip (:)) (5:2:4:1:[]) [] 
-> (5:2:4:1:[]) 
-> [5,2,4,1]

來源

2017-09-02 09:26:26

我一直在與foldl vs foldr爭執不休，爲什麼要在這裏使用foldl？你會介意一個快速的解釋嗎？謝謝！ – Netwave

@DanielSanchez：'foldr'開始列表的右端（或更一般的可摺疊）。所以如果列表是'[a，b，c，d]'，它會計算出'f a（f b（f c（f d z）））''。 'foldl'將計算f（f（f（f z a）b）c）d'。用'z'作爲初始元素。 –

好吧，我現在好多了，謝謝！ – Netwave

未能使用foldl來逆轉Haskell中的列表

回答

相關問題