Common lisp：如何实现 reduce

Question

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

这是我的代码

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

顺便说一句，它甚至无法正常工作，因为它 "backward" 例如：

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

应该return

(((1 2) 3) 4)

但我得到

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

有什么想法吗？

Answer 1

我认为您已经实施了正确的右折叠，因为这通常被称为，但想要左折叠。注意特征尾递归，并使用 "default" 值作为累加器：

(defun my-left-reduce (f i xs)
  (if (null xs)
       i
    (my-left-reduce f (funcall f i (car xs)) (cdr xs))

（而且我没用过Common Lisp，不过概念应该很清楚。）

旁白：通常认为左侧折叠 "backwards"。比较 (my-reduce cons NIL '(1 2 3)) 和 (my-left-reduce cons NIL '(1 2 3))。后者应该反转列表的原始 cons 结构。

Answer 2

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

(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 对左右折叠有很好的 high-level 解释。

Common lisp：如何实现 reduce

Common lisp: How to implement reduce

lisp

reduce

functional-programming

list

common-lisp