scheme - foldl 和 foldr 如何工作，在一个例子中分解？

Question

好的，我是 scheme/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 和 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 的反转.