foldl和foldr如何工作，在一個示例中分解？

Question

好的，我是新的計劃/ racket/lisp。我正在練習創建自己的函數，語法和遞歸，所以我想使自己的foldl和foldr函數完全符合預定義的版本。我不能這樣做，因爲我只是不明白這些功能是如何工作的。我在這裏看到過類似的問題，但我仍然不明白。一些分解的例子會有所幫助！這裏是我的（不正確）的過程：

(foldl - 0 '(1 2 3 4))我做0 -(4-3-2-1)，並獲得2這是正確的答案

(foldl - 0 '(4 3 2 1))我做0-(1-2-3-4)，並得到8，但它應該是-2。

(foldr - 0 '(1 2 3 4))我做0-(1-2-3-4)並再次獲得8，但它應該是-2。

(foldr - 0 '(4 3 2 1))我做0-(4-3-2-1)並得到2這是正確的答案。

我在做什麼錯？

Answer 1

讓我們看看：(foldr - 0 '(1 2 3 4))。

這裏字面'(1 2 3 4)構造，其元素是數字1，2，3清單，並讓我們去榜上無名明確的建設：

(cons 1 (cons 2 (cons 3 (cons 4 empty)))) 

人能想到foldr作爲函數用函數f替換cons，並用值v清空。

因此

(foldr f 0 (cons 1 (cons 2 (cons 3 (cons 4 empty))))) 

成爲

  (f 1 (f 2 (f 3 (f 4 v))))) 

如果函數f是-和價值v是0，你將得到：

(- 1 (- 2 (- 3 (- 4 0))))) 

，我們可以計算出結果：

(- 1 (- 2 (- 3 (- 4 0)))) 
= (- 1 (- 2 (- 3 4))) 
= (- 1 (- 2 -1)) 
= (- 1 3) 
= -2 

請注意，(foldr cons empty a-list)生成a-list的副本。

在另一方面功能foldl使用這些值從另一面：

> (foldl cons empty '(1 2 3 4)) 
'(4 3 2 1) 

換句話說：

(foldl f v '(1 2 3 4)) 

變得

(f 4 (f 3 (f 2 (f 1 v)))). 

如果f是函數-且值爲0，則我們得到：

(- 4 (- 3 (- 2 (- 1 0)))) 
= (- 4 (- 3 (- 2 1))) 
= (- 4 (- 3 1)) 
= (- 4 2) 
= 2 

請注意(foldl cons empty a-list)產生的反向a-list。