非二进制 foldl 和 foldr 如何在 Racket 中工作？

Question

我熟悉 foldl 和 foldr 在单个列表中的基本工作原理和差异。但是，在 Racket 中，您可以在多个列表上使用折叠。例如，您可以通过写

来查找两个列表中元素的差异

; (mapMinus '(3 4) '(1 2)) => '(2 2)
(define (mapMinus lst0 lst1)
  (foldl (λ (hd0 hd1 acc) (cons (- hd0 hd1) acc)) '() lst0 lst1))

Racket 的 foldl 和 foldr 实现如何处理多个列表？ foldl 的 Racket 源代码在 GitHub here 上可用，但我对 Chez Scheme 的了解还不够深入。

Answer 1

对多个列表进行操作的 fold 只是同时将其 lambda 按元素应用于所有列表。也许它的简化实现（没有错误检查等）会使事情变得更清楚；让我们比较一下 foldr 的标准实现（恕我直言，它比 foldl 更容易理解）：

(define (foldr proc init lst)
  (if (null? lst)
      init
      (proc (car lst)
            (foldr proc init (cdr lst)))))

使用接受多个列表的实现：

(define (foldr proc init . lst) ; lst is a list of lists
  (if (null? (car lst)) ; all lists assumed to be of same length
      init
      ; use apply because proc can have any number of args
      (apply proc
             ; append, list are required for building the parameter list
             ; in the right way so it can be passed to (apply proc ...)
             (append (map car lst)
                     ; use apply again because it's a variadic procedure
                     (list (apply foldr proc init (map cdr lst)))))))

多列表版本中的所有额外代码都是为了同时将proc应用于多个元素，获取每个列表的当前元素(map car lst)并遍历所有列表(map cdr lst).

此外，实施还需要考虑到该过程对 variable number 个列表进行操作，假设所提供的 lambda 接收到正确数量的参数（输入列表的数量 + 1） .它按预期工作：

(foldr (lambda (e1 e2 acc)
         (cons (list e1 e2) acc))
       '()
       '(1 2 3)
       '(4 5 6))

=> '((1 4) (2 5) (3 6))

Answer 2

我认为您真正要问的是如何在 Scheme/Racket 中创建可变参数函数。 https://docs.racket-lang.org/guide/define.html 给出了答案，但让我举个简单的例子：

(define (foo a b . xs)
  (+ a b (length xs)))

等同于

def foo(a, b, *xs):
  return a + b + len(xs)

在 Python 中。 xs 这是一个包含其余参数的列表值。

第二个难题是，如何应用具有列表值的可变参数函数。为此，您可以使用 apply。在 https://docs.racket-lang.org/guide/application.html#%28part._apply%29 阅读更多内容。同样，这里有一个简单的例子：

(define (foo a b c) (+ a b c))
(apply foo 1 '(2 3))
;; equivalent to (foo 1 2 3)

相当于

def foo(a, b, c): return a + b + c
foo(1, *[2, 3]) ;; equivalent to foo(1, 2, 3)

有了这些，创建一个接受多个参数的折叠只是一个编程练习：

(define (my-fold proc accum required-first-list . list-of-optional-lists)
  ... IMPLEMENT FOLD HERE ...)

请注意，如果您阅读 Racket 的源代码（使用 Chez Scheme），您会看到它使用 case-lambda 而不是直接定义函数。 case-lambda 只是一种使代码更有效地使用折叠（即只有一个列表的折叠）的方法。

非二进制 foldl 和 foldr 如何在 Racket 中工作？

How do non-binary foldl and foldr work in Racket?

scheme

fold

racket