javascript - 理解 scheme 中的 fold 和 reduce 函数

Question

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

在使用 (use-modules (srfi srfi-1)) 的 guile 方案中，你可以使用这个:

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 创建一个函数(该函数将返回其中一个函数)。

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

这是我的归约函数:

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>

fold 函数在 JavaScript 中应该如何工作？ scheme 中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 …
方案流程: fold-right proc init lst1 lst2 …

将 proc 应用于 lst1 lst2 的元素……以构建结果，并返回该结果。

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

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，支持多个列表非常容易 -

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
    // ...
}