关于 mapcon 的问题及其假定的等同于(应用#'nconc(maplist ...))
Question regarding mapcon and its supposed equivalence to (apply #'nconc (maplist ...))
Hyperspec 声明 mapcon
(大致?)等同于 (apply #'nconc (maplist ...))
,即“应用函数的结果通过使用 nconc 而不是组合成一个列表列表”。
但是如果这样
(maplist #'identity '(1 2 3)) ; '((1 2 3) (2 3) (3))
(apply #'nconc '((1 2 3) (2 3) (3)))
有效,为什么这个
(apply #'nconc (maplist #'identity '(1 2 3)))
(mapcon #'identity '(1 2 3))
也工作?
刚刚偶然发现了一个解释:“如果 FN 结果是 新鲜列表(非共享),结果与 (APPLY #'APPEND (MAPLIST ...))。 (Simplified Common Lisp reference)
(apply #'nconc (maplist #'copy-list '(1 2 3)))
(mapcon #'copy-list '(1 2 3))
有趣的是,Hyperspec 中并未提及这一点。这能推导出来吗?
关系不是“大致”相同的,它的定义完全是:
(mapcon f x1 ... xn)
== (apply #'nconc (maplist f x1 ... xn))
此外,NCONC
is defined recursively in terms of LAST
and RPLACD
:
(nconc) => ()
(nconc nil . lists) == (nconc . lists)
(nconc list) => list
(nconc list-1 list-2) == (progn (rplacd (last list-1) list-2) list-1)
(nconc list-1 list-2 . lists) == (nconc (nconc list-1 list-2) . lists)
只要计算出相同的结果,一个实现就可以自由地拥有一个有效的实现。但是,由于它被定义为使用 rplacd
,它肯定会改变列表(它链接每个中间结果的最后一个 cons 单元格的 cdr 槽)。
第§3.7.1 Modification of Literal Objects节还说:
The consequences are undefined if literal objects are destructively modified.
在你的例子中,你正在调用 #'identity
并破坏性地连接来自引用列表的值,即。文字数据。行为未定义。
使用新分配的列表
如果您调用 copy-list
而不是 identity
,则每个中间结果都是一个新列表,结果定义为:
(equalp (apply #'nconc (maplist #'copy-list '(1 2 3)))
(mapcon #'copy-list '(1 2 3)))
=> T
意外循环列表
如果你使用像 (list 1 2 3)
这样的非文字数据,行为仍然是未定义的,但这更微妙。例如,让我们在处理循环性的同时打印 (maplist #'identity (list 1 2 3))
的结果:
(write (maplist #'identity (list 1 2 3)) :circle t)
这将打印以下内容,#n=
being labels (reader variables) and #n#
向后引用与之前标记的列表相同的列表:
((1 . #1=(2 . #2=(3))) #1# #2#)
也就是说,结果是三个列表(L1 L2 L3)
的列表,其中L2
是L1
的其余部分,L3
是[=34的其余部分=].这意味着如果您这样做:
(apply #'nconc (maplist #'identity (list 1 2 3)))
就好像你这样做了:
(let* ((L1 (list 1 2 3))
(L2 (rest L1))
(L3 (rest L2)))
(nconc L1 L2 L3))
给定上述递归定义,等价于:
(nconc (nconc L1 L2) L3)
^ ^
| |
| \-- inner nconc (N1)
|
\-- outer nconc (N0)
内项N1本身被计算为:
(progn (rplacd (last L1) L2) L1)
在这里,L1
的末尾链接到 L2
(L1
的其余部分),这形成了一个循环。您可以直接尝试,您的环境应该会打印出来;例如在 SBCL 中:
* (setf *print-length* 10)
10
* (let ((L1 (list 1 2 3)))
(nconc L1 (rest L1)))
(1 2 3 2 3 2 3 2 3 2 ...)
您还可以通过将 *print-circle*
设置为 T 将其打印到 REPL。
这本身就很好,但是这个无限列表用于上面名为 N0 的 nconc
的外部调用。假设评估 N1 的中间结果是 R1
:
(nconc R1 L3)
以上评价为:
(progn (rplacd (last R1) L3) R1)
这里程序卡住了,因为last
永远不会终止。
至少,大多数实现都是这种情况,但请注意,LAST
仅在列表不是循环时定义:
list---a list, which might be a dotted list but must not be a circular list.
这就是为什么这里的行为实际上是未定义的。
Hyperspec 声明 mapcon
(大致?)等同于 (apply #'nconc (maplist ...))
,即“应用函数的结果通过使用 nconc 而不是组合成一个列表列表”。
但是如果这样
(maplist #'identity '(1 2 3)) ; '((1 2 3) (2 3) (3))
(apply #'nconc '((1 2 3) (2 3) (3)))
有效,为什么这个
(apply #'nconc (maplist #'identity '(1 2 3)))
(mapcon #'identity '(1 2 3))
也工作?
刚刚偶然发现了一个解释:“如果 FN 结果是 新鲜列表(非共享),结果与 (APPLY #'APPEND (MAPLIST ...))。 (Simplified Common Lisp reference)
(apply #'nconc (maplist #'copy-list '(1 2 3)))
(mapcon #'copy-list '(1 2 3))
有趣的是,Hyperspec 中并未提及这一点。这能推导出来吗?
关系不是“大致”相同的,它的定义完全是:
(mapcon f x1 ... xn)
== (apply #'nconc (maplist f x1 ... xn))
此外,NCONC
is defined recursively in terms of LAST
and RPLACD
:
(nconc) => ()
(nconc nil . lists) == (nconc . lists)
(nconc list) => list
(nconc list-1 list-2) == (progn (rplacd (last list-1) list-2) list-1)
(nconc list-1 list-2 . lists) == (nconc (nconc list-1 list-2) . lists)
只要计算出相同的结果,一个实现就可以自由地拥有一个有效的实现。但是,由于它被定义为使用 rplacd
,它肯定会改变列表(它链接每个中间结果的最后一个 cons 单元格的 cdr 槽)。
第§3.7.1 Modification of Literal Objects节还说:
The consequences are undefined if literal objects are destructively modified.
在你的例子中,你正在调用 #'identity
并破坏性地连接来自引用列表的值,即。文字数据。行为未定义。
使用新分配的列表
如果您调用 copy-list
而不是 identity
,则每个中间结果都是一个新列表,结果定义为:
(equalp (apply #'nconc (maplist #'copy-list '(1 2 3)))
(mapcon #'copy-list '(1 2 3)))
=> T
意外循环列表
如果你使用像 (list 1 2 3)
这样的非文字数据,行为仍然是未定义的,但这更微妙。例如,让我们在处理循环性的同时打印 (maplist #'identity (list 1 2 3))
的结果:
(write (maplist #'identity (list 1 2 3)) :circle t)
这将打印以下内容,#n=
being labels (reader variables) and #n#
向后引用与之前标记的列表相同的列表:
((1 . #1=(2 . #2=(3))) #1# #2#)
也就是说,结果是三个列表(L1 L2 L3)
的列表,其中L2
是L1
的其余部分,L3
是[=34的其余部分=].这意味着如果您这样做:
(apply #'nconc (maplist #'identity (list 1 2 3)))
就好像你这样做了:
(let* ((L1 (list 1 2 3))
(L2 (rest L1))
(L3 (rest L2)))
(nconc L1 L2 L3))
给定上述递归定义,等价于:
(nconc (nconc L1 L2) L3)
^ ^
| |
| \-- inner nconc (N1)
|
\-- outer nconc (N0)
内项N1本身被计算为:
(progn (rplacd (last L1) L2) L1)
在这里,L1
的末尾链接到 L2
(L1
的其余部分),这形成了一个循环。您可以直接尝试,您的环境应该会打印出来;例如在 SBCL 中:
* (setf *print-length* 10)
10
* (let ((L1 (list 1 2 3)))
(nconc L1 (rest L1)))
(1 2 3 2 3 2 3 2 3 2 ...)
您还可以通过将 *print-circle*
设置为 T 将其打印到 REPL。
这本身就很好,但是这个无限列表用于上面名为 N0 的 nconc
的外部调用。假设评估 N1 的中间结果是 R1
:
(nconc R1 L3)
以上评价为:
(progn (rplacd (last R1) L3) R1)
这里程序卡住了,因为last
永远不会终止。
至少,大多数实现都是这种情况,但请注意,LAST
仅在列表不是循环时定义:
list---a list, which might be a dotted list but must not be a circular list.
这就是为什么这里的行为实际上是未定义的。