理解 scheme 中的 fold 和 reduce 函数

Question

我有关于 scheme 和 lisp 的一般性问题。 fold 和 reduce 函数应该如何工作？

在使用 (use-modules (srfi srfi-1)) 的诡计中，你可以使用这个：

guile> (fold cons '() '(1 2 3 4))
> (4 3 2 1)
guile> (fold cons '(1 2 3 4) '())
> (1 2 3 4)

我正在 JavaScript 的 lisp 中处理 fold 函数，我想为 reduce 和 fold 创建一个函数（该函数将 return 这些函数之一）。

但是它们应该如何工作？在我的代码中，我正在检查第一个列表是否不为空或者它是否没有结束但是在这里你传递了空列表（第一个代码）。 fold 是否在第二个列表上工作，并检查它是否没有结束或在两个列表上都工作，因为 reverse 也可以工作？当以 '() 作为初始值调用时，fold 执行了多少次，或者它处理整个第一个参数？

这是我的 reduce 函数：

function reduce(fn, list, init = nil) {
    if (isEmptyList(list) || isNull(list)) {
        return list;
    }
    let result = init;
    let node = list;
    if (init === null) {
        result = list.car;
        node = list.cdr;
    }
    return (function loop() {
        function next(value) {
            result = value;
            node = node.cdr;
            return loop();
        }
        if (node === nil || !(node instanceof Pair)) {
            if (typeof result === 'number') {
                return LNumber(result);
            }
            return result;
        }
        const item = node.car;
        const value = fn(result, item);
        if (isPromise(value)) {
            return value.then(next);
        } else {
            return next(value);
        }
    })();
}

下面的结果对 reduce 正确吗？

lips> (reduce cons '(1 2 3 4) nil)
((((nil . 1) . 2) . 3) . 4)
lips> (reduce list '(1 2 3 4) nil)
((((nil 1) 2) 3) 4)
lips>

折叠功能在 JavaScript 中应该如何工作？方案中 fold 和 reduce 的确切逻辑是什么？

这是另一个诡计的例子：

guile> (fold-right append '(1 2 3 4) '())
(1 2 3 4)
lips> (reduce append '(1 2 3 4) '())
(1 2 3 4)

它在我的 lisp 中工作相同，这是否意味着我的 reduce 是正确的？如何测试我的功能是否正确？

我有一个问题，在 Guile 中：

guile> (fold-right list '(1 2 3 4) '())
> (1 2 3 4)
guile> (fold list '(1 2 3 4) '())
> (1 2 3 4)

但我口齿不清：

lips> (reduce list '(1 2 3 4) '())
((((() 1) 2) 3) 4)

fold-right实际上是reduce吗？因为这个 guile 代码给出了与我的 reduce 相同的结果：

guile> (list (list (list (list '() 1) 2) 3) 4)
> ((((() 1) 2) 3) 4)

Answer 1

https://www.gnu.org/software/guile/manual/html_node/SRFI_002d1-Fold-and-Map.html

方案流程： fold proc init lst1 lst2 …
Scheme Procedure: fold-right proc init lst1 lst2 …

将proc应用到lst1lst2的元素……来构建一个结果，并且return 结果。

每个 proc 调用是 (proc elem1 elem2 … previous)，其中 elem1 来自 lst1，elem2 来自 lst2，依此类推。 previous 是上一次调用 proc 的 return 或第一次调用的给定 init。 如果任何列表为空，则 init 被 returned。

fold 从头到尾遍历列表元素。下面显示了一个列表反转及其调用，

(fold cons '() '(1 2 3))

(cons 1 '())
(cons 2 '(1))
(cons 3 '(2 1)
⇒ (3 2 1)

fold-right 从最后到第一个遍历列表元素，即。从右边。因此，例如以下找到最长的字符串，最后一个字符串中最长的，

(fold-right (lambda (str prev)
              (if (> (string-length str) (string-length prev))
                  str
                  prev))
            ""
            '("x" "abc" "xyz" "jk"))
⇒ "xyz"

scheme folds 支持多个列表，但我将向您展示如何调整 JavaScript 实现，使其适用于一个列表 -

function reduce (fn, init, list) {
  if (isNull(list))
    return init
  else
    return reduce(fn, fn(list.car, init), list.cdr)
}

function reduceRight (fn, init, list) {
  if (isNull(list))
    return init
  else
    return fn(list.car, reduceRight(fn, init, list.cdr))
}

由于 JavaScript 支持 rest 参数 和 spread arguments -[=，支持多个列表非常简单17=]

function some (fn, list) {
  if (isNull(list))
    return false
  else
    return fn(list.car) || some(fn, list.cdr)
}

function reduce (fn, init, ...lists) {
  if (some(isEmpty, lists))
    return init
  else
    return reduce
             ( fn
             , fn (...lists.map(l => l.car), init)
             , lists.map(l => l.cdr)
             )
}

function reduceRight (fn, init, ...lists) {
  if (some(isEmpty, lists))
    return init
  else
    // exercise left for reader
    // ...
}

理解 scheme 中的 fold 和 reduce 函数

Understanding fold and reduce functions in scheme

javascript

lisp

reduce

scheme

fold