`mapcan` 真的使用 `nconc` 吗？

Question

根据Common Lisp HyperSpec (CLHS)，mapcan用于nconc将其结果合并到一个列表中。CLHS 还表示

(mapcon f x1 ... xn)
   ==  (apply #'nconc (maplist f x1 ... xn))

所以我一直担心使用applywhere call-arguments-limitis low 的后果 - CLHS 说它可以低至 50，而在 LispWorks 上它是 2047。在 LispWorks 上，

(mapcan #'list (loop for i from 0 to call-arguments-limit collect i))

成功，同时

(apply #'nconc (mapcar #'list (loop for i from 0 to call-arguments-limit collect i)))

失败了。如果mapcan真的必须使用nconc，这两个不都应该失败吗？

Answer 1

该规范的一个重要点是1.4.3 不正式属于本标准的部分，其中特别指出提供的示例仅用于说明目的，而不是标准的一部分。

一般来说，在 HyperSpec 中，展示如何用另一种结构表达一种结构的示例旨在展示函数的意图，并且可以假设该示例适用于一些没有物理限制（如内存等）的抽象实现。

没有要求或MAPCAN以此处显示的确切方式MAPCON使用NCONC，事实上，我认为没有正式的定义==（从技术上讲，代码也使用省略号，因此它不是用 Common Lisp 编写的）。

一个更好的例子是使用REDUCE连续NCONC的结果，甚至是LOOP. 我认为在这个例子中使用APPLY是不幸的，但最终你可以假设既不MAPCON也MAPCAN不受 限制CALL-ARGUMENTS-LIMIT。

例如，您可以将其表达如下，但实际MAPCAN可能不需要像 那样分配中间列表MAPCAR，它可以只融合这两个操作：

(reduce #'nconc (mapcar f x1 .. xn))

Answer 2

引用自标准：

mapcan和分别mapcon类似于mapcar和maplist，不同之处在于应用函数的结果是通过使用nconc而不是组合成一个列表list。

那么，这是否意味着mapcar必须由 实施(apply #'list ...)？别傻了，当然没必要。这意味着将by 调用的函数的结果mapcar以相同的方式组合到一个列表中list：通过构建一系列 cons 单元，这些单元的 cars 指向返回值。

以完全相同的方式，从 by 调用的函数返回的结果以同样的方式mapcan组合nconc，即它们必须是列表，并且这些列表被破坏性地连接起来。

这就是标准中语言的含义。

作为一个例子，这里是一个简单版本（只有一个列表参数）的实现，它mapcan确实用于nconc构建列表，但只nconc使用两个参数进行调用。这不是您mapcan在现实生活中实现的方式，但它足够简单，您无需依赖即可看到发生了什么reduce。

(defun mc (f l)
  (labels ((mc-loop (tail head last)
             ;; tail is the rest of the list we're processing, head is
             ;; the thing we are building, last is the last non-null
             ;; return from f if there is one
             (if (null tail)            ;we're done
                 head
               (let ((r (funcall f (first tail))))
                 (mc-loop (rest tail)
                          (if (null head) r head) ;the first non-null return is the head
                          (if (null r)
                              ;; last non-null element is unchanged
                              last
                            (progn
                              ;; smash last and then r is the new last
                              (nconc last r)
                              r)))))))
    (mc-loop l '() '())))