1. ホーム
  2. scheme

[解決済み] foldlとfoldrはどのように機能するのか、例を挙げて説明します。

2022-02-08 01:35:01

質問内容

さて、私はscheme/racket/lispを使い始めたばかりです。私は自分自身の関数、構文、再帰を作成する練習をしているので、自分自身の foldlfoldr 関数で、定義済みバージョンと全く同じことを行うことができます。これらの関数がどのように動作するのか理解できないため、実行できません。ここで同じような質問を見ましたが、まだ理解できていません。いくつかの例を分解してくれると助かります。以下は私の(間違った)プロセスです。

(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が表示されます。

何が間違っているのでしょうか?

どうすればいいですか?

見てみましょう。 (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 .

したがって

(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 .