非二进制折叠和文件夹如何在球拍中工作？

Question

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

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

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

Racket的foldl和foldr的实现如何精确地处理多个列表？ GitHub foldl上提供了here的Racket源代码，但我对Chez Scheme的了解不甚了解。

Answer 1

我认为您真正要问的是如何在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仅是使代码更有效地使用fold（即仅包含一个列表的fold）的一种方法。

Answer 2

在多个列表上操作的fold仅将其lambda逐个元素地应用于所有列表。比较一下foldr的标准实现，也许它的简化实现（没有错误检查等）会让事情变得更清楚。

(define (foldr proc init lst)
  (if (null? lst)
      init
      (proc (car lst)
            (foldr proc init (cdr lst)))))
[带有接受多个列表的实现：

(define (foldr proc init . lst)
  (if (null? (car lst))
      init
      (apply proc
             ; append, list are required for building the parameter list
             (append (map car lst)
                     (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))