scheme - 对 foldr/foldl 中的 "Init/Base"感到困惑( Racket )

Question

我接近了解 foldr和 foldl但还没有。

我了解 foldr基本上是在“从右到左”的列表上执行某些功能的堆栈实现。

所以对于 foldr :

(define (fn-for-lon lon)
    (cond [(empty? lon) 0]
          [else
             (+ (first lon)
                (fn-for-lon (rest lon))]))

基本上相当于:

(foldr + 0 lon)

我明白 foldl基本上是从“左到右”的尾递归累加器版本。

所以对于 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使用了一个运算符吗？

(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)))]))

Answer 1

来看看实际的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))))))

返回 (f init l . ls) foldl的案例.

删除错误检查归结为

       (let loop ([init init] 
                  [ls (cons l ls)])
         (if (pair? (car ls))
             (loop (apply f (mapadd car ls init)) 
                   (map cdr ls))
             init))]))

初始值init绑定(bind)到一个变量(也称为)init用于累积结果。变量 ls是当循环开始绑定(bind)到所有列表的列表 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 的函数到它的参数列表。