foldlとfoldrはどのように機能しますか？

Question

さて、私はscheme/racket/lispで新しいです。私は独自の関数、構文、再帰を作成して練習していますので、あらかじめ定義されたバージョンとまったく同じように自分自身のfoldlとfoldr関数を作りたいと思います。私はこれらの機能がどのように機能するのか分かりませんので、できません。私はここで似たような質問を見ましたが、私はまだそれを得ていません。分解されたいくつかの例が役に立ちます！ここに私の（間違った）プロセスである：

(foldl - 0 '(1 2 3 4))私は0 -(4-3-2-1)を行うと、私は0-(1-2-3-4)を行うと、8を得るが、それがあるべき-2

(foldl - 0 '(4 3 2 1))正しい答えである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であるリストを構築し、そして、4。のは、明示的なリストの構築してみましょう：

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

一つは関数としてfoldrと考えることができますがconsを機能fで置き換え、値vで空にします。

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

を我々は結果を計算することができます。

したがって

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

は、関数fは-であり、値vが0である場合は、あなたが得る

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

なり：

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

(foldr cons empty a-list)は、a-listのコピーを生成することに注意してください。すなわち

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

：一方

機能foldlは反対側からの値を使用しfが関数である場合

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

は

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

なります-であり、値が0の場合、次のようになります。

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

(foldl cons empty a-list)は、a-listの逆を生成することに注意してください。