Haskell中的foldl和foldr的聯繫？

01-28

有同學看書，提到Haskell中foldl和foldr如何互相實現，思考了良久，得到了一個答案，但總覺得似懂非懂（第一題還可以一步步推導出來，但第二題基本是靠猜的）。
foldLeft f x ys = xx x where h y s = x -&> s (f x y) xx = foldr h id ys
foldRight f x ys = xx x where h s y = x -&> s (f y x) xx = foldl h id ys
這兩個答案如此相似是源於某種巧合么...抑或是有某種內在的統一的規律？像這樣用fold來構造高階函數的方法，是不是和Combinator或者Continuation Passing Style有聯繫？
由於解題過程比較艱難苦悶，總覺得自己對一些基礎的東西理解不太透徹。若想提高自己思考和解決這類問題方面的效率，不知有哪些資料可以參考。希望各位菊苣們指點一二~

謝邀！

15年12月18日更新：

fold這個函數背後其實能牽扯出很多很本質的東西。fold函數從List這個遞歸數據類型reduce得到一個值，和F-alg的不動點有關係，因此具有泛性質（universal property），如下所示：

g [] = v &<===&> g = fold f v g (x:xs) = f x (g xs)

由此可以得到fold函數的變換關係，這就是fold函數的fusion定律，也即在函數h的作用下兩個fold函數的參數f z和參數g w具有如下的變換關係：

h . fold g w = fold f z

h w = z h (g x y) = f x (h y)

根據fold的泛性質（universal property），我們可以推導出fold到foldl的變換，具體步驟如下：

-- Definition of foldl foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs


-- Since parameter f stay constant during recursion, so define a local

-- function g that performs the recursion.

foldl f z xs = g xs z

  where

    g [] z = z

    g (x:xs) z = g xs (f z x)
-- Rewrite g by partial apply

foldl f z xs = g xs z

  where

    g [] = z -&> z

    g (x:xs) = z -&> g xs (f z x)
-- So function g return the function that has one parameter.

foldl f z xs = g xs z

  where

    g [] = id

    g (x:xs) = z -&> g xs (f z x)
-- According by universal property of fold, we have two equation

g [] = id

g (x:xs) = k x (g xs)
-- By definition of function g, we get

z -&> g xs (f z x) = k x (g xs)

-- By apply the argument z, we get

g xs (f z x) = k x (g xs) z

-- By replace with g = g xs, we get

g (f z x) = k x g z

-- By expand k, and recursion capture in g, we get

k = x g -&> z -&> g (f z x)

k = x g -&> v -&> g (f v x)

-- According universal property of fold, we have follow equation foldl f z xs = fold (x g -&> v -&> g (f v x)) id xs z foldl f z xs = fold step id xs z where step x g = v -&> g (f v x)

上面右邊式子中的函數v -&> g (f v x)是fold函數的累加值，通過遍歷List將多個函數組合起來（通過函數的apply）得到一個大的函數，其初始值是id函數。這是一個高階函數的概念，xs這個List被變換為函數z -&> g (f v x)組成的List。

更具體的可以參考論文A tutorial on the universality and expressiveness of fold -- http://www.cs.nott.ac.uk/~pszgmh/fold.pdf。

另外，Jeremy Gibbons在2014年寫了一篇使用fold來演算DSL的論文，非常精彩，具體參考Folding Domain-Specific Languages:
Deep and Shallow Embeddings -- http://www.cs.ox.ac.uk/jeremy.gibbons/publications/embedding.pdf。

------ 我是分割線 ---------

一圖勝千言。

上面兩張圖形象的揭示了foldr和foldl的意義，這兩個函數之間的聯繫也就很清晰了。正如 @祖與占提到的，fold函數在範疇論中對應的就是catamorphism，其作用就是將遞歸的數據結構reduce為一個值。

我們將foldr稍作變形，可以看的更清楚些。

type ListAlgebra a b = (b, a -&> b -&> b)

fold :: ListAlgebra a b -&> [a] -&> b fold (fzero, fcons) [] = fzero fold (fzero, fcons) (x:xs) = x `fcons` fold (fzero, fcons) xs

在ghci中測試一下

Prelude&> fold (0, (+)) [1..3] 6

和foldr的功能一樣，這個實現和上面圖的描述就更接近了。

再扯遠一點，foldr和unfoldr是一對具有相反作用的函數，unfoldr在範疇論中對應的是anamorphism，其作用是通過給定的seed和遞推關係構造出一個遞歸的數據結構。

unfoldr :: (b -&> Maybe (a, b)) -&> b -&> [a]

再追究的深入一點，就會和free object有聯繫了，比如free monad這些東西。

參考鏈接：

Catamorphism

Anamorphism

http://www.cs.nott.ac.uk/~pszgmh/fold.pdf

http://www.cs.ox.ac.uk/jeremy.gibbons/publications/embedding.pdf

謝邀, 具體的答案應該是xxmorphism 之類的東西, 但是我不會, 我來吹下牛逼就完.

數學家能找到定理之間的相似之處，優秀的數學家能看到證明之間的相似之處，卓越的數學家能察覺到數學分支之間的相似之處。最後，究級的數學家能俯瞰這些相似之處之間的相似之處。

以下為本菜雞的&心路&腦洞大開歷程:

作為一隻菜雞曾經幻想過成為一名大神, 所以把很久前買來的聖經 -- SICP 一道道習題開始做, 然後碰到這麼一道習題(Exercise 2.38):

... Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

Cool, 這比玩OJ等AC有意思多了, 當時學了一點抽象代數的皮毛, 馬上意識到這貨要滿足結合律, 它是一個monoid ! 再之後用fold實現了一遍map, filter之後覺得這種遍曆數據結構的方式有共通之處.

在各種Google, 翻論文之後知道研究這些遍歷模式的領域叫Recursion Schemes, 還有涉及Program Calculation的一些東西, 貌似這領域已經沒多少人研究

之後發現牽涉貓論, 智商不夠放棄研究, 完.

ref:

foldl.com

foldr.com

可以關注這些人的工作(時間序):

Lambert Meertens, Erik Meijer, Graham Hutton, Jeremy Gibbons, Nicolas Wu(這哥們略像彥祖)

Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire 奠基之作

A tutorial on the universality and expressiveness of fold 寫實際代碼推一下這篇就好

Bird–Meertens formalism xxmorphism

Sorting Morphisms

Patterns in Functional Programming

近來也有不少關於Recursion Schemes的教程, 不一一列舉

在列表有限的情況下，可以簡單的有如下關係

```haskell

foldr f z xs = foldl (flip f) z (reverse xs)

```

時隔許久，參考了菊苣們推薦的兩份資料：

A tutorial on the universality and expressiveness of fold 【1】
Introduction to Functional Programming, 1ed 【2】

然後自己來補充一下。

對於用foldr表示foldl，文獻【1】中主要解釋了foldr的universal性質和fusion法則：即List的遞歸本質，常見的基於List的遞歸函數包括foldl都可以用foldr表達。具體內容parker liu已經作答，不再贅述。

反之，對於用foldl表示foldr，文獻【2】中第3.5.1部分介紹了foldl和foldr的對偶定則，其中第三條藉助reverse表述為：

foldr p b as = foldl q b (reverse as) where q b a = p a b

此定則可以當作用foldl表示foldr的基礎。這裡簡單的證明一下：

首先利用foldl的定義證明關於foldl的一個lemma：
q (foldl q b as) a == foldl q b (as ++ [a])

用歸納法：

BASE -- let as = [] LHS == q (foldl q b []) a0 == q b a0 RHS == foldl q b ([] ++ [a0]) == foldl q b (a0:[]) == foldl q (q b a0) [] == q b a0 == LHS OK


SUPP -- let as = as

LHS == q (fold q b as) a0

RHS == foldl q b (as ++ [a0])

    == LHS

INDU -- let as = (a:as) LHS == q (foldl q b (a:as)) a0 == q (foldl q (q b a) as) a0 -- use SUPPOSE with b = (q b a) == foldl q (q b a) (as ++ [a0]) RHS == foldl q b ((a:as) ++ [a0]) == foldl q (q b a) (as ++ [a0]) == LHS OK

利用上述定理，證明對偶定則三即

foldr p b as = foldl q b (reverse as) where q b a = p a b

同樣使用歸納法：

BASE -- let as = [] LHS == foldr p b [] == [] RHS == foldl q b (reverse []) == foldl q b [] == [] == LHS OK


SUPP -- let as = as

LHS == foldr p b as

RHS == foldl q b (reverse as)

    == LHS
INDU -- let as = (a:as)

LHS == foldr p b (a:as)

    == p a (foldr p b as)

    -- use SUPP

    == p a (foldl q b (reverse as))

    -- use p a b = q b a

    == q (foldl q b (reverse as)) a

RHS == foldl q b (reverse (a:as)) == foldl q b (reverse as ++ [a]) -- use lemma == q (foldl q b (reverse as)) a == LHS OK

由於reverse本身可以用foldl表示，即

reverse xs = foldl (xs x -&> (x:xs)) xs

就當作解決了吧（霧

值得注意的是，【1】中提及了用foldl表示foldr嚴格意義上是不可行的，這種表達無法保留laziness，個中深意仍待領悟…

一個是左遞歸，一個是右遞歸