我目前正處於真實世界Haskell的第4章，我試圖圍繞implementing foldl in terms of foldr環繞我的頭。使用foldr實現郵編
（這裏是他們的代碼:)
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
我想我會嘗試使用相同的技術來實現zip，但我似乎沒有被任何進展。它甚至有可能嗎？
zip2 xs ys = foldr step done xs ys
where done ys = []
step x zipsfn [] = []
step x zipsfn (y:ys) = (x, y) : (zipsfn ys)
這是如何工作：（foldr相似步驟完成XS）返回消耗 YS的功能;所以我們沿着xs列表建立一個嵌套組合 函數，這些函數將分別應用於ys的相應部分。
如何拿出它：我開始的總體思路（從之前見過類似 的例子），寫
zip2 xs ys = foldr step done xs ys
然後填充在每個反過來以下行與它不得不 是爲了使類型和價值出來正確。 最容易考慮最簡單的情況之前，更難。
第一行可以更簡單地寫成
zip2 = foldr step done
爲mattiast顯示。
我發現使用非常相似的方法，你的道：
myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
where step a f (b:bs) = (a,b):(f bs)
step a f [] = []
對於這裏的非本地Haskellers，我寫了一個計劃版本的算法，使其更清晰所發生的情況：
> (define (zip lista listb)
((foldr (lambda (el func)
(lambda (a)
(if (empty? a)
empty
(cons (cons el (first a)) (func (rest a))))))
(lambda (a) empty)
lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))
的foldr導致功能，當應用到列表，將返回列表中給出的函數返回的列表的zip。由於懶惰評估，Haskell隱藏了內部lambda。
爲了進一步把它分解：
採取拉鍊上輸入：「（1 2 3） 的foldr相似FUNC被調用與
el->3, func->(lambda (a) empty)
此擴展爲：
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))
如果我們現在要返回這個，我們將有一個函數，其中包含一個元素列表 並返回對（3元素）：
> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))
繼續，FOLDR現在調用FUNC與
el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))
這是一個FUNC這需要兩個元件，現在的列表，以及與(list 2 3)拉鍊他們：
> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))
發生了什麼事？
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))
a，在這種情況下，爲(list 9 1)
(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))
而且，正如你還記得，f拉鍊與3說法。
，這樣下去等等
已經在這裏給出的答案，但不包括（舉例）推導。所以即使這麼多年過去了，也許值得添加它。
其實很簡單。首先，
foldr f z xs
= foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn])
= ... = f x1 (f x2 (f x3 (... (f xn z) ...)))
因此由ETA-擴大，
foldr f z xs ys
= foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
= ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys
由於這裏是顯而易見的，如果f在其第二個參數非逼着，它得到的x1和工作第一ys,f x1r1ys其中r1 =(f x2 (f x3 (... (f xn z) ...)))= foldr f z [x2,x3,...,xn]。
因此，使用
f x1 r1 [] = [] f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1
我們安排的信息通道由左到右沿着列表，通過調用r1與輸入列表ys1的其餘，foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1，作爲下一個步。就是這樣。
當ys短於xs（或相同的長度），則[]情況下f火災和處理停止。但是，如果ys長於xs然後f的[]情況下，將不會觸發，我們將進入決賽f xnz(yn:ysn)應用，
f xn z (yn:ysn) = (xn,yn) : z ysn
既然我們已經達到的xs，在結束zip處理必須停止：
z _ = []
這意味着定義z = const []應使用：
zip xs ys = foldr f (const []) xs ys
where
f x r [] = []
f x r (y:ys) = (x,y) : r ys
從f的觀點出發，r起着成功延續，其f呼叫時的處理將繼續，具有所發射的一對後(x,y)的作用。
所以r是「什麼是更ys做的時候有更多的x的」和z = const []，該nil - 案例在foldr，是「什麼是與ys時，有沒有更多的x完成s「。或f可以自行停止，當ys用完時返回[]。
注意如何ys作爲一種累積值，這是由左到沿列表xs權過去了，從f一個調用到下一個（「累計」的步驟是，在這裏，剝頭元素）。
Naturally這對應於左倍，其中一個累積步驟是「應用功能」，對z = id當「沒有更多x的」返回最終累積值：
foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a
類似地，對於有限名單，
foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a
而且，由於組合功能獲取到決定是否繼續與否，現在有可能已經離開倍，可提前停止：
foldlWhile t f a xs = foldr cons id xs a
where
cons x r a = if t x then r (f a x) else a
或跳躍離開倍，foldlWhen t ...，與
cons x r a = if t x then r (f a x) else r a
等
我試圖瞭解這個優雅的解決方案我自己，所以我試圖推導出類型和評價自己。所以，我們需要編寫一個函數：
zip xs ys = foldr step done xs ys
在這裏我們需要得到step和done，不管他們是。召回foldr的類型，實例化列表：
foldr :: (a -> state -> state) -> state -> [a] -> state
但是我們foldr調用必須被實例類似下面的，因爲我們必須接受不是一個，而是兩個列表參數：
foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]
因爲->爲right-associative，這相當於：
foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])
我們([b] -> [(a,b)])科爾esponds在原有foldr類型簽名state類型的變量，因此我們必須同時更換的state每次發生：
foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
-> ([b] -> [(a,b)])
-> [a]
-> ([b] -> [(a,b)])
這意味着，我們通過foldr參數必須有以下幾種類型：
step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]
回想一下，foldr (+) 0 [1,2,3]擴展爲：
1 + (2 + (3 + 0))
因此，如果xs = [1,2,3]和ys = [4,5,6,7]，我們foldr調用將擴展爲：
1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]
這意味着我們的1 `step` (2 `step` (3 `step` done))結構必須創建一個遞歸函數，將經過[4,5,6,7]並拉上的元素。 （請記住，如果其中一個原始列表更長，超出的值將被丟棄）。 IOW，我們的結構必須具有[b] -> [(a,b)]的類型。
3 `step` done是我們的基本情況，其中done是初始值，如0在foldr (+) 0 [1..3]中。我們不想在3之後壓縮任何東西，因爲3是xs的最終值，所以我們必須終止遞歸。如何在基本情況下終止列表中的遞歸？您返回空列表[]。回想起done類型簽名：
done :: [b] -> [(a,b)]
因此，我們不能只返回[]，我們必須返回會忽略任何它接收的功能。因此使用const：
done = const [] -- this is equivalent to done = \_ -> []
現在讓我們開始搞清楚step應該是什麼。它將a類型的值與[b] -> [(a,b)]類型的函數組合在一起，並返回[b] -> [(a,b)]類型的函數。
在3 `step` done，我們知道結果值，後來去我們的壓縮列表必須(3,6)（由原來的xs和ys知道）。因此3 `step` done必須評估爲：
\(y:ys) -> (3,y) : done ys
記住，我們必須返回一個功能，這裏面我們莫名其妙地拉上拉鍊元素，上面的代碼是情理之中的事情和typechecks。
現在我們假設step應該如何評估，讓我們繼續評估。下面是我們的foldr評估所有減少步驟看起來怎麼樣：
3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)
評價產生了這個實施步驟（注意，我們佔ys用完元素的早就被返回一個空列表）：
step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys
因此，全功能zip被實現如下：
zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
where done = const []
step x f [] = []
step x f (y:ys) = (x,y) : f ys
PS：我如果你受到褶皺優雅的啓發，請閱讀Writing foldl using foldr，然後閱讀Graham Hutton的文章A tutorial on the universality and expressiveness of fold。
zip所有這些解決方案的問題是，它們只是摺疊在一個列表或另一個列表上，如果它們都是「優秀的製作者」，按照列表融合的說法，這可能是一個問題。你實際需要的是一個摺疊在兩個列表上的解決方案。幸運的是，有一篇關於這個問題的文章，被稱爲"Coroutining Folds with Hyperfunctions"。
您需要一個輔助類型，一個函數，它基本上是一個函數，它將另一個函數作爲參數。
newtype H a b = H { invoke :: H b a -> b }
這裏使用的超函數基本上就像普通函數的「堆棧」一樣。
push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q
您還需要一種方法將兩個超函數端到端放在一起。
(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k
這是由法律有關push：
(push f x) .#. (push g y) = push (f . g) (x .#. y)
這原來是一個聯合運營商，這是身份：
self :: H a a
self = H $ \k -> invoke k self
你也需要的東西，無視「堆疊」上的所有其他內容並返回特定值：
base :: b -> H a b
base b = H $ const b
最後，你需要一種方式來獲得的值了功能亢進：
run :: H a a -> a
run q = invoke q self
run字符串的所有push編輯功能整合在一起，首尾相連，直到遇到一個base或無限循環。
所以，現在您可以將兩個列表摺疊成超函數，使用將信息從一個傳遞到另一個的函數，並組合最終值。
zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
first _ Nothing = []
first x (Just (y, xys)) = (x, y):xys
second y xys = Just (y, xys)
之所以摺疊兩份名單的問題是因事GHC並稱爲名單融合，這是在the GHC.Base module談過，但也許應該更加知名。作爲一個好的列表製作者，使用build和foldr可以防止大量無用的生產和即時消耗列表元素，並且可以進一步公開優化。
一個簡單的方法：
lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]
-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
where f (zs, (y:ys)) x = ((x,y):zs, ys)
-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
where f x (zs, (y:ys)) = ((x,y):zs, ys)
這是如何工作的？不折疊只需要3個參數？ – Claudiu 2008-10-24 20:51:46