list - 普通口齿不清 : How to implement reduce

Question

我已经找了好几天了，基本上我需要实现一个与系统函数reduce 做同样事情的函数。这是我到目前为止所想到的，但是如果没有初始值i，我无法让它工作。

这是我的代码

(defun my-reduce (p i lista)
  (if (null lista)
       i
    (funcall p (car lista) (my-reduce p i (cdr lista)))))

顺便说一下，它甚至无法正常工作，因为它“倒退”了 例如:

(my-reduce #'list NIL '(1 2 3 4))

应该返回

(((1 2) 3) 4)

但我明白了

(1 (2 (3 (4 NIL))))

有什么想法吗？

Answer 1

左折叠可以通过简单的迭代来实现:

(defun my-fold-left (reducer initial list)
  (loop for fold = initial then (funcall reducer fold element)
        for element in list
        finally (return fold)))

例如:

(my-fold-left #'cons 0 '(1 2 3 4))
((((0 . 1) . 2) . 3) . 4)

(my-fold-left #'cons 0 '())
0

如果您使用map，您也可以概括和折叠向量:

(defun my-fold-left (reducer fold sequence)
  (map nil
       (lambda (e) (setf fold (funcall reducer fold e)))
       sequence)
  fold)

以防万一您没有阅读它，this answer对左右折叠有很好的高级解释。