列表連接使用與foldl「 foldr相似

我現在學習Haskell，我面臨着以下問題：列表連接使用與foldl「 foldr相似

我想用與foldl重寫++函數」和foldr相似。我用foldr完成它：

myConcat xs ys = foldr (:) ys xs

我不能用foldl'來做。我讀過RealWorldHaskell，foldr對於做這種事情很有用。好吧，但我不能用foldl寫一個等價物給++嗎？有人可以告訴我我該如何做到這一點（如果可以做...本書沒有提及任何有關它的）...

Haskell的類型機制是否阻止我這樣做？每次我嘗試時，我得到一個類型錯誤...

來源

2011-06-17 Adi

我猜，你得到的是從嘗試到foldr到foldl'簡單地切換錯誤：

myConcat xs ys = foldl' (:) ys xs

產生的誤差（用我的擁抱REPL）：

ERROR - Type error in application 
*** Expression  : foldl' (:) xs ys 
*** Term   : (:) 
*** Type   : a -> [a] -> [a] 
*** Does not match : [a] -> a -> [a]

在公告最後兩行（提供的類型和預期類型）[a]和a的位置處於相反的位置。這意味着我們需要一個類似於(:)的函數，但它以相反的順序參數。

Haskell有一個功能，它爲我們做到這一點：flip函數。基本上，flip相當於

flip :: (a -> b -> c) -> (b -> a -> c) 
flip f y x = f x y

即，flip取二進制函數作爲參數，並返回原來的另一個二進制函數，其自變量被反轉（「翻轉」）。因此，儘管(:)的類型爲a -> [a] -> [a]，但我們看到flip (:)的類型爲[a] -> a -> [a]，因此它是foldl'的參數的完美候選者。

使用flip，我們現在有這樣的代碼：

myConcat xs ys = foldl' (flip (:)) ys xs

此結果與事實foldl'的類型是(a -> b -> c) -> a -> [b] -> c

帶參數運行此[1..5]和[6..10]，我們得到的[5,4,3,2,1,6,7,8,9,10]結果，這幾乎是我們想要的。唯一的問題是結果中第一個列表倒退。添加一個簡單的調用reverse賦予我們的myConcat最後定義：

myConcat xs ys = foldl' (flip (:)) ys (reverse xs)

縱觀這一過程顯示了經常出現的好東西之一，當寫Haskell代碼：當你碰到一個問題，您可以一次解決一個（小）步驟。當你已經有一個工作實現時，這是尤其如此，而你只是試圖編寫另一個實現。需要注意的是，如果您更改了實現的一部分（在這種情況下，將foldr更改爲foldl'），那麼其他許多其他必需的更改就會脫離類型定義。剩下的少數是可以很容易找到的糾正問題，無論是通過運行測試用例，還是通過查看所使用函數的確切性質。 PS：任何可以清理最後一行代碼的Haskell傢伙，都可以隨時這樣做。雖然它並不可怕，但我不覺得它很漂亮。不幸的是，我對Haskell不太瞭解。

來源

2011-06-17 05:10:48

您的帖子真實我幫助了我。感謝您的解釋:) – Adi 2011-06-17 12:54:07

data [] a = ... | a : [a] 
(:) :: a -> [a] -> [a]

（:) op對待左，右操作數不同。

a :: Char 
b :: Char 
c :: [Char]

a:[b]是確定

a:b是不正常

a:c是確定的。

尋找類型簽名foldr (:)和foldl (:)你會發現他們的不同。

來源

2011-06-17 04:07:38 Nybble

:運算符將一個單個元素（其左參數）連接到列表及其正確參數。

foldl到的參數，

摺疊功能
初始值
值的列表到步驟通過。

回想特別是摺疊函數採用，因爲它的左邊參數，電流值，它開始作爲初始值。因此，摺疊函數的左參數是一個列表，它的正確參數是單個值。如果你玩它，你可以[僅通過切換參數使類型匹配]得到的東西一樣，

> foldl (\x y -> y:x) [1, 2, 3] [4, 5, 6] 
[6,5,4,1,2,3]

但是，這是不是你想要的。你必須自己解決它;我可以使用foldl構建一個反向函數，並將其作爲子程序調用 - 但如果可以，請隨意以不同的方式解決它。

來源

2011-06-17 04:55:56 gatoatigrado

你的解決方案是優雅的:)謝謝你的幫助我理解 – Adi 2011-06-17 12:55:29

你可以做到這一點使用與foldl但相比使用與foldl來FOLDR根據實施

的例子，不會是有效的：

show $ (\xs ys -> foldl (\s e -> e:s) ys (reverse xs)) [1,2] [3,4]

來源

2011-06-17 05:23:07 Ankur

爲什麼foldr更有效率？ – 2015-05-12 04:41:46

它並不總是可能的，因爲foldr（以及++）在無限列表上工作，但foldl不。然而，foldl可以來編寫foldr方面：http://www.haskell.org/haskellwiki/Foldl_as_foldr

更新：對於有限名單，foldr可以也寫在條款foldl：

foldr :: (b -> a -> a) -> a -> [b] -> a 
foldr f a bs = 
    foldl (\g b x -> g (f b x)) id bs a

所以從這一點就可以實現(++)在foldl

來源

2011-06-17 06:31:51 newacct

列表連接使用與foldl「 foldr相似

回答

相關問題