有没有一种方法可以在 Common Lisp 中仅使用应用程序编程并避免递归或迭代作为编程风格来实现 mapcar？

Question

我正在尝试通过 Common Lisp：对符号计算的简单介绍 来学习 Common Lisp。此外，我正在使用 SBCL、Emacs 和 Slime。

在第 7 章中，作者建议本书将涵盖三种 编程风格 ：递归、迭代和应用程序编程。

我对最后一个感兴趣。这种风格以 applicative operator funcall 而闻名，它是负责其他应用运算符的原语，例如 mapcar.

因此，出于教育目的，我决定使用 funcall:

实现我自己的 mapcar 版本

(defun my-mapcar (fn xs)
  (if (null xs)
      nil
      (cons (funcall fn (car xs))
            (my-mapcar fn (cdr xs)))))

如您所见，我使用递归作为一种编程风格来构建一个标志性的应用程序编程函数。

似乎有效：

CL-USER> (my-mapcar (lambda (n) (+ n 1)) (list 1 2 3 4))
(2 3 4 5)

CL-USER> (my-mapcar (lambda (n) (+ n 1)) (list ))
NIL

;; comparing the results with the official one

CL-USER> (mapcar (lambda (n) (+ n 1)) (list ))
NIL

CL-USER> (mapcar (lambda (n) (+ n 1)) (list 1 2 3 4))
(2 3 4 5)

有没有使用递归或迭代实现 mapcar 而不的方法？仅使用 applicative 编程风格？

谢谢。

Obs.：我试着看看它是如何实现的。但是不可能

CL-USER> (function-lambda-expression #'mapcar)
NIL
T
MAPCAR

我还使用 Emacs M-. 来查找文档。但是，以下几点对我没有帮助。我使用 this 找到以下文件：

/usr/share/sbcl-source/src/code/list.lisp
  (DEFUN MAPCAR)
/usr/share/sbcl-source/src/compiler/seqtran.lisp
  (:DEFINE-SOURCE-TRANSFORM MAPCAR)
/usr/share/sbcl-source/src/compiler/fndb.lisp
  (DECLAIM MAPCAR SB-C:DEFKNOWN)

Answer 1

mapcar 本身就是一个基本的应用运算符（Common Lisp第220页：对符号的温和介绍计算）。所以，如果你想以应用的方式重写它，你应该使用一些其他原始的应用运算符，例如 map or map-into。例如，map-into:

CL-USER> (defun my-mapcar (fn list &rest lists)
           (apply #'map-into (make-list (length list)) fn list lists))
MY-MAPCAR
CL-USER> (my-mapcar #'1+ '(1 2 3))
(2 3 4)
CL-USER> (my-mapcar #'+ '(1 2 3) '(10 20 30) '(100 200 300))
(111 222 333)

Answer 2

从技术上讲，递归可以按如下方式实现：

(defun fix (f)
   (funcall (lambda (x) (funcall x x))
            (lambda (x) (funcall f (lambda (&rest y) (apply (funcall x x) y))))))

请注意 fix 不以任何方式使用递归。事实上，我们可以只在 f 的定义中使用 lambda，如下所示：

(defconstant fix-combinator 
             (lambda (g) (funcall 
                          (lambda (x) (funcall x x))
                          (lambda (x) (funcall 
                                       g 
                                       (lambda (&rest y) (apply (funcall x x) 
                                                                 y)))))))

(defun fix-2 (f)
  (funcall fix-combinator f))

fix-combinator 常量通常称为 y 组合子。

原来fix有如下属性：

计算 (apply (fix f) list) 等同于计算 (apply (funcall f (fix f)) list)。非正式地，我们有 (fix f) = (funcall f (fix f)).

因此，我们可以通过

定义map-car（我使用不同的名称来避免包锁定）

(defun map-car (func lst)
  (funcall (fix (lambda (map-func) (lambda (lst) ; We want mapfunc to be (lambda (lst) (mapcar func lst))
    (if (endp lst) 
        nil 
        (cons (funcall func (car lst)) 
              (funcall map-func (cdr lst)))))))
    lst))

注意缺少递归或迭代。

也就是说，通常 mapcar 在使用“应用”编程风格时只是作为一个原始概念。

Answer 3

另一种实现 mapcar 的方法是使用更通用的 reduce 函数 (a.k.a.fold)。让我们将用户提供的函数命名为 f 并定义 my-mapcar.

reduce 函数带有一个累加器值，该值构建结果列表，这里它将取一个值 v，一个子列表 rest，并调用 cons 与 (funcall f v) 和 rest，以构建列表。

更准确地说，这里 reduce 将实现右折叠，因为 cons 是右结合的（例如，递归列表是“右”手边，即第二个cons 的参数，例如 (cons a (cons b (cons nil)))).

为了用reduce定义一个右折叠，你传递:from-end t，这表明它从最后一个元素和初始累加器建立一个值来获得一个新的累加器值，然后倒数第二个元素与新的累加器构建一个新的累加器，等等。这就是你如何确保结果元素与输入列表的顺序相同。

在这种情况下，reducing 函数将其当前元素作为第一个参数，将累加器作为第二个参数。

由于元素的类型和累加器的类型不同，你需要为累加器传递一个:initial-value（从列表中获取初始值的默认行为是函数像 + 或 *，其中累加器与列表元素位于同一域中）。

考虑到这一点，你可以这样写：

(defun my-map (f list)
  (reduce (lambda (v rest) (cons (funcall f v) rest))
          list
          :from-end t
          :initial-value nil))

例如：

(my-map #'prin1-to-string '(0 1 2 3))
; => ("0" "1" "2" "3")

有没有一种方法可以在 Common Lisp 中仅使用应用程序编程并避免递归或迭代作为编程风格来实现 mapcar？

Is there a way to implement mapcar in Common Lisp using only applicative programming and avoiding recursion or iteration as programming styles?

iteration

recursion

common-lisp

map-function