被 foldr/foldl 中的 "Init/Base" 搞糊涂了（球拍）
Confused by "Init/Base" in foldr/foldl (Racket)
我接近理解 foldr 和 foldl 但还不完全理解。
我理解 foldr 基本上是对 "right to left" 中的列表执行某些功能的堆栈实现。
因此 foldr:
(define (fn-for-lon lon)
(cond [(empty? lon) 0]
[else
(+ (first lon)
(fn-for-lon (rest lon))]))
基本上等同于：
(foldr + 0 lon)
而且我知道 foldl 基本上是从 "left to right".
开始的尾递归累加器版本
因此 foldl:
(define (fn-for-lon lon0)
(local [(define (fn-for-lon lon acc)
(cond [(empty? lon) acc]
[else
(fn-for-lon (rest lon) (+ acc (first lon)))]
(fn-for-lon lon0)))
基本上等同于：
(foldl + 0 lon)
但是一旦引入两个变量会发生什么？我曾尝试阅读该主题，但我无法理解它，因为没有人谈论幕后发生的事情。
我真的很困惑第二个参数是 "base" 还是 "init" 或者它是否仅取决于函数中是否采用了一个或两个变量。在我给出的 foldl 示例中，它似乎是 init acc 值（我想最终是基本情况），但在 foldr 中它将是基本情况。难道只是因为我只对proc使用了operator吗？
(foldr (lambda (a b) (cons (add1 a) b)) empty (list 1 2 3 4))
像上面这样的事情，我真的完全失去了理解。我知道该怎么做，但不知道后台发生了什么。这导致我在更复杂的问题中迷失方向。
这和 b 只是 empty 是一回事吗？ b 是否暂时接替 (rest lon)？
(define (fn-for-lon lon)
(cond [(empty? lon) empty]
[else
(cons (add1 (first lon))
(fn-for-lon (rest lon)))]))
foldl 和 foldr 的第二个参数总是 init。如果您传入单个列表，则您提供的函数必须始终采用 2 个参数，并且该函数的第二个参数是累加值（最初是 init，然后是上一次调用的 return 值你的函数）。
（在您之前使用 + 的示例中，您可以将其视为与 (lambda (a b) (+ a b)) 相同。在这种情况下，a 是列表元素，并且 b是累加值。)
当您使用 N 个列表调用 foldl 或 foldr 时，您提供的函数必须采用 N+1 个参数；前 N 个参数对应于每个列表中的下一个元素，最后一个参数是累加值（最初是 init，然后是上一次调用函数的 return 值）。
如果我提供（我自己的）foldl 和 foldr 的实现是否有助于您的理解？他们在这里：
(define foldl
(case-lambda
;; one list
[(func init lst)
(let loop ([result init]
[rest lst])
(if (null? rest)
result
(loop (func (car rest) result) (cdr rest))))]
;; multiple lists
[(func init list1 . list2+)
(let loop ([result init]
[rests (cons list1 list2+)])
(if (ormap null? rests)
result
(loop (apply func (append (map car rests) (list result)))
(map cdr rests))))]))
(define foldr
(case-lambda
;; one list
[(func init lst)
(let recur ([rest lst])
(if (null? rest)
init
(func (car rest) (recur (cdr rest)))))]
;; multiple lists
[(func init list1 . list2+)
(let recur ([rests (cons list1 list2+)])
(if (ormap null? rests)
init
(apply func (append (map car rests)
(list (recur (map cdr rests)))))))]))
让我们来看看实际的foldl来自Racket：
(define foldl
(case-lambda
[(f init l)
(check-fold 'foldl f init l null)
(let loop ([init init] [l l])
(if (null? l) init (loop (f (car l) init) (cdr l))))]
[(f init l . ls)
(check-fold 'foldl f init l ls)
(let loop ([init init] [ls (cons l ls)])
(if (pair? (car ls)) ; `check-fold' ensures all lists have equal length
(loop (apply f (mapadd car ls init)) (map cdr ls))
init))]))
我们看到两种情况：第一种情况(f init l)是为了提高效率。如果只使用一个列表 l，那么我们会得到一个快速版本的 foldl.
第二种情况(f init l . ls)就是你要找的那种。在我们检查它之前，我们需要先看看辅助函数mapadd。
调用 (mapadd f l last) 会将 f 应用到列表 l 的所有元素，并将结果放在 `last.
上
示例：
> (mapadd sqr '(1 2 3 4) 42)
'(1 4 9 16 42)
mapadd的定义：
(define (mapadd f l last)
(let loop ([l l])
(if (null? l)
(list last)
(cons (f (car l)) (loop (cdr l))))))
回到 foldl 的 (f init l . ls) 案例。
删除错误检查归结为
(let loop ([init init]
[ls (cons l ls)])
(if (pair? (car ls))
(loop (apply f (mapadd car ls init))
(map cdr ls))
init))]))
初始值init绑定到一个变量（也称为）init，用于累积结果。变量 ls 是循环开始时绑定到所有列表 foldl 的列表的时间。请注意，这些列表都具有相同的长度。循环继续，直到 ls 中的所有列表都为空。测试 (pair? (car ls)) 检查第一个列表是否为空，但请记住列表的长度相同。
现在 init 被替换为 (apply f (mapadd car ls init))。此调用首先获取每个列表的第一个元素，然后转换为 init 的当前值。然后应用f。
考虑这个例子：(foldl + 0 '(1 2) '(10 11)) 计算结果为 24。
这里
f = +
init = 0
ls = ((1 2) (10 11))
和
> (mapadd car '((1 2) (10 11)) 0)
'(1 10 0)
所以
> (apply + (mapadd car '((1 2) (10 11)) 0))
11
下一轮我们会看到
f = +
init = 11
ls = ((2) (11))
并且 (apply + (mapadd car ls init) 将计算为 24。
另一种解释示例的方法(foldl + 0 '(1 2) '(10 11))。
(define init 0)
(for ([x (in-list '( 1 2))] ; x and y loop in parallel
[y (in-list '(10 11))])
(set! init (apply + (list x y init)))) ; accumulate result in init
init
实施 foldl 的复杂之处在于不知道使用了多少列表。
更新
在实践中使用 foldl 时，最好从规范而非实现的角度考虑 foldl。
以下是使用两个列表调用时如何指定 foldl。
来电：
(foldl f x0
(cons a0 (cons a1 (cons a2 '())))
(cons b0 (cons b1 (cons b2 '()))))
计算结果与
相同
(f a2 b2
(f a1 b1
(f a0 b0
x0)))
会。
我们可以试试看：
> (foldl (λ args (cons 'f args)) 'x0
(cons 'a0 (cons 'a1 (cons 'a2 '())))
(cons 'b0 (cons 'b1 (cons 'b2 '()))))
'(f a2 b2 (f a1 b1 (f a0 b0 x0)))
请注意，(λ args (cons 'f args)) 是将符号 f 添加到其参数列表前的函数。
折叠真的是为了帮助我们，而不是为了迷惑我们。它们捕获特定的递归模式以实现一致的重用。折叠是抽象定义的，也最容易抽象地理解。了解您的语言折叠实现细节的唯一原因是确保实现有效。
每当我们有特定的递归模式（写在等式伪代码中）时，
foo(xs) =
matches xs with
Empty -> zero
Cons(head,tail) -> comb(head,
foo(tail))
我们将列表的头部与列表尾部 foo 的 调用的递归结果结合起来 ，我们得到了一个（正确的）折叠，并且调用 foo(xs) 与调用 foldr(comb, zero, xs) 相同。 如何这在我们选择的语言中究竟是如何实现的是无关紧要的。
如您所见，组合函数（运算符或其他）必须接受列表的"current element"作为其第一个参数，以及递归结果，如它的最后。 只有当链表中没有更多元素时，才用zero值代替递归结果，启动链comb 在从递归的基本情况 Empty 返回的路上执行的计算。
所以在阅读折叠定义时，我们总是将组合函数的第一个参数视为 "current element"，最后一个是 "recursive result of processing the rest of the list"。
为什么关于 "current" 元素的措辞？因为，假设我们的列表是[a,b,c,...,n]，调用foldr(comb, z, [a,b,c,...,n])，按照上面的模式，和调用是一样的
comb(a,
foldr(comb, z, [b,c,d,...,n]))
==
comb(a,
comb(b,
comb(c,
......, comb(n, z)......)))
这个是，在某种意义上，是列表右折叠的定义，a.k.a。列表 变形。
Racket 增加了同时并行折叠多个列表的能力。自然地，组合函数的参数排列保持不变——除了最后一个参数之外的所有参数都对应于当前元素，每个参数都来自每个参数列表；最后一个参数是 递归结果 以将它们组合在一起。
一个相似但不同的模式是
bar(xs) =
matches xs with
Empty -> zero
Cons(head,tail) -> comb(head,
tail,
bar(tail))
这被称为 paramorphism（参见 Common Lisp 中的 maplist vs. mapcar）。
由于两者都是捕获递归，zero 对应于我们正在递归的归纳数据定义的基本情况：
List of 'a = Empty
or Cons('a, List of 'a)
从基本情况开始，我们得到一个双重模式，在递归调用之前建立一个值，a.o.t.在上面之后，用
baz(zero, xs) =
matches xs with
Empty -> zero
Cons(head,tail) -> baz( comb(head, zero),
tail)
您将识别为左折（并且 zero 不再是基本案例值，而是一个正在构建的值，- 或累积，- 并且 最终 当 Empty 大小写被命中时返回）。
所以这只是 (1+(2+(3+...(n+0)...))) 和 之间的区别(...(((0+1)+2)+3)...+n),左边(为了表示方便，把参数顺序倒过来显示) .当 (+) 是关联运算时，一个人的结果将与另一个人的结果相同。对于数字，它是。
另见 this answer。
我接近理解 foldr 和 foldl 但还不完全理解。
我理解 foldr 基本上是对 "right to left" 中的列表执行某些功能的堆栈实现。
因此 foldr:
(define (fn-for-lon lon)
(cond [(empty? lon) 0]
[else
(+ (first lon)
(fn-for-lon (rest lon))]))
基本上等同于：
(foldr + 0 lon)
而且我知道 foldl 基本上是从 "left to right".
因此 foldl:
(define (fn-for-lon lon0)
(local [(define (fn-for-lon lon acc)
(cond [(empty? lon) acc]
[else
(fn-for-lon (rest lon) (+ acc (first lon)))]
(fn-for-lon lon0)))
基本上等同于：
(foldl + 0 lon)
但是一旦引入两个变量会发生什么？我曾尝试阅读该主题，但我无法理解它，因为没有人谈论幕后发生的事情。
我真的很困惑第二个参数是 "base" 还是 "init" 或者它是否仅取决于函数中是否采用了一个或两个变量。在我给出的 foldl 示例中，它似乎是 init acc 值（我想最终是基本情况），但在 foldr 中它将是基本情况。难道只是因为我只对proc使用了operator吗？
(foldr (lambda (a b) (cons (add1 a) b)) empty (list 1 2 3 4))
像上面这样的事情，我真的完全失去了理解。我知道该怎么做，但不知道后台发生了什么。这导致我在更复杂的问题中迷失方向。
这和 b 只是 empty 是一回事吗？ b 是否暂时接替 (rest lon)？
(define (fn-for-lon lon)
(cond [(empty? lon) empty]
[else
(cons (add1 (first lon))
(fn-for-lon (rest lon)))]))
foldl 和 foldr 的第二个参数总是 init。如果您传入单个列表，则您提供的函数必须始终采用 2 个参数，并且该函数的第二个参数是累加值（最初是 init，然后是上一次调用的 return 值你的函数）。
（在您之前使用 + 的示例中，您可以将其视为与 (lambda (a b) (+ a b)) 相同。在这种情况下，a 是列表元素，并且 b是累加值。)
当您使用 N 个列表调用 foldl 或 foldr 时，您提供的函数必须采用 N+1 个参数；前 N 个参数对应于每个列表中的下一个元素，最后一个参数是累加值（最初是 init，然后是上一次调用函数的 return 值）。
如果我提供（我自己的）foldl 和 foldr 的实现是否有助于您的理解？他们在这里：
(define foldl
(case-lambda
;; one list
[(func init lst)
(let loop ([result init]
[rest lst])
(if (null? rest)
result
(loop (func (car rest) result) (cdr rest))))]
;; multiple lists
[(func init list1 . list2+)
(let loop ([result init]
[rests (cons list1 list2+)])
(if (ormap null? rests)
result
(loop (apply func (append (map car rests) (list result)))
(map cdr rests))))]))
(define foldr
(case-lambda
;; one list
[(func init lst)
(let recur ([rest lst])
(if (null? rest)
init
(func (car rest) (recur (cdr rest)))))]
;; multiple lists
[(func init list1 . list2+)
(let recur ([rests (cons list1 list2+)])
(if (ormap null? rests)
init
(apply func (append (map car rests)
(list (recur (map cdr rests)))))))]))
让我们来看看实际的foldl来自Racket：
(define foldl
(case-lambda
[(f init l)
(check-fold 'foldl f init l null)
(let loop ([init init] [l l])
(if (null? l) init (loop (f (car l) init) (cdr l))))]
[(f init l . ls)
(check-fold 'foldl f init l ls)
(let loop ([init init] [ls (cons l ls)])
(if (pair? (car ls)) ; `check-fold' ensures all lists have equal length
(loop (apply f (mapadd car ls init)) (map cdr ls))
init))]))
我们看到两种情况：第一种情况(f init l)是为了提高效率。如果只使用一个列表 l，那么我们会得到一个快速版本的 foldl.
第二种情况(f init l . ls)就是你要找的那种。在我们检查它之前，我们需要先看看辅助函数mapadd。
调用 (mapadd f l last) 会将 f 应用到列表 l 的所有元素，并将结果放在 `last.
示例：
> (mapadd sqr '(1 2 3 4) 42)
'(1 4 9 16 42)
mapadd的定义：
(define (mapadd f l last)
(let loop ([l l])
(if (null? l)
(list last)
(cons (f (car l)) (loop (cdr l))))))
回到 foldl 的 (f init l . ls) 案例。
删除错误检查归结为
(let loop ([init init]
[ls (cons l ls)])
(if (pair? (car ls))
(loop (apply f (mapadd car ls init))
(map cdr ls))
init))]))
初始值init绑定到一个变量（也称为）init，用于累积结果。变量 ls 是循环开始时绑定到所有列表 foldl 的列表的时间。请注意，这些列表都具有相同的长度。循环继续，直到 ls 中的所有列表都为空。测试 (pair? (car ls)) 检查第一个列表是否为空，但请记住列表的长度相同。
现在 init 被替换为 (apply f (mapadd car ls init))。此调用首先获取每个列表的第一个元素，然后转换为 init 的当前值。然后应用f。
考虑这个例子：(foldl + 0 '(1 2) '(10 11)) 计算结果为 24。
这里
f = +
init = 0
ls = ((1 2) (10 11))
和
> (mapadd car '((1 2) (10 11)) 0)
'(1 10 0)
所以
> (apply + (mapadd car '((1 2) (10 11)) 0))
11
下一轮我们会看到
f = +
init = 11
ls = ((2) (11))
并且 (apply + (mapadd car ls init) 将计算为 24。
另一种解释示例的方法(foldl + 0 '(1 2) '(10 11))。
(define init 0)
(for ([x (in-list '( 1 2))] ; x and y loop in parallel
[y (in-list '(10 11))])
(set! init (apply + (list x y init)))) ; accumulate result in init
init
实施 foldl 的复杂之处在于不知道使用了多少列表。
更新
在实践中使用 foldl 时，最好从规范而非实现的角度考虑 foldl。
以下是使用两个列表调用时如何指定 foldl。
来电：
(foldl f x0
(cons a0 (cons a1 (cons a2 '())))
(cons b0 (cons b1 (cons b2 '()))))
计算结果与
相同(f a2 b2
(f a1 b1
(f a0 b0
x0)))
会。
我们可以试试看：
> (foldl (λ args (cons 'f args)) 'x0
(cons 'a0 (cons 'a1 (cons 'a2 '())))
(cons 'b0 (cons 'b1 (cons 'b2 '()))))
'(f a2 b2 (f a1 b1 (f a0 b0 x0)))
请注意，(λ args (cons 'f args)) 是将符号 f 添加到其参数列表前的函数。
折叠真的是为了帮助我们，而不是为了迷惑我们。它们捕获特定的递归模式以实现一致的重用。折叠是抽象定义的，也最容易抽象地理解。了解您的语言折叠实现细节的唯一原因是确保实现有效。
每当我们有特定的递归模式（写在等式伪代码中）时，
foo(xs) =
matches xs with
Empty -> zero
Cons(head,tail) -> comb(head,
foo(tail))
我们将列表的头部与列表尾部 foo 的 调用的递归结果结合起来 ，我们得到了一个（正确的）折叠，并且调用 foo(xs) 与调用 foldr(comb, zero, xs) 相同。 如何这在我们选择的语言中究竟是如何实现的是无关紧要的。
如您所见，组合函数（运算符或其他）必须接受列表的"current element"作为其第一个参数，以及递归结果，如它的最后。 只有当链表中没有更多元素时，才用zero值代替递归结果，启动链comb 在从递归的基本情况 Empty 返回的路上执行的计算。
所以在阅读折叠定义时，我们总是将组合函数的第一个参数视为 "current element"，最后一个是 "recursive result of processing the rest of the list"。
为什么关于 "current" 元素的措辞？因为，假设我们的列表是[a,b,c,...,n]，调用foldr(comb, z, [a,b,c,...,n])，按照上面的模式，和调用是一样的
comb(a,
foldr(comb, z, [b,c,d,...,n]))
==
comb(a,
comb(b,
comb(c,
......, comb(n, z)......)))
这个是，在某种意义上，是列表右折叠的定义，a.k.a。列表 变形。
Racket 增加了同时并行折叠多个列表的能力。自然地，组合函数的参数排列保持不变——除了最后一个参数之外的所有参数都对应于当前元素，每个参数都来自每个参数列表；最后一个参数是 递归结果 以将它们组合在一起。
一个相似但不同的模式是
bar(xs) =
matches xs with
Empty -> zero
Cons(head,tail) -> comb(head,
tail,
bar(tail))
这被称为 paramorphism（参见 Common Lisp 中的 maplist vs. mapcar）。
由于两者都是捕获递归，zero 对应于我们正在递归的归纳数据定义的基本情况：
List of 'a = Empty
or Cons('a, List of 'a)
从基本情况开始，我们得到一个双重模式，在递归调用之前建立一个值，a.o.t.在上面之后，用
baz(zero, xs) =
matches xs with
Empty -> zero
Cons(head,tail) -> baz( comb(head, zero),
tail)
您将识别为左折（并且 zero 不再是基本案例值，而是一个正在构建的值，- 或累积，- 并且 最终 当 Empty 大小写被命中时返回）。
所以这只是 (1+(2+(3+...(n+0)...))) 和 之间的区别(...(((0+1)+2)+3)...+n),左边(为了表示方便，把参数顺序倒过来显示) .当 (+) 是关联运算时，一个人的结果将与另一个人的结果相同。对于数字，它是。
另见 this answer。