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 视为一个用函数 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 的反向结果。

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

How do foldl and foldr work, broken down in an example?

lisp

scheme

fold

racket