关于mapcon及其假定等价的问题(apply#'ncconc(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))

也工作?

回答

这种关系并不“大致”相同,它的定义完全相同:

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

此外,NCONC根据LAST和递归定义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节文字对象的修改也说:

如果文字对象被破坏性地修改,后果是不确定的。

在您的情况下,您正在调用#'identity和连接来自引用列表的破坏性值,即。字面数据。行为未定义。

使用新分配的列表

如果,而不是identity调用copy-list,则每个中间结果都是一个新列表,并且结果已定义:

(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=标签(读取器变量)和#n#对与先前标记的相同列表的反向引用:

((1 . #1=(2 . #2=(3))) #1# #2#)

换句话说,结果是一个包含三个列表的列表(L1 L2 L3),其中L2是 的其余部分L1L3的其余部分L2。这意味着如果你这样做:

(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)

在这里, of 的结尾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 。

这本身很好,但是这个无限列表用于上面nconc命名N0的外部调用。假设评估N1的中间结果是R1

(nconc R1 L3)

以上评价为:

(progn (rplacd (last R1) L3) R1)

在这里程序卡住了,因为last永远不会终止。

至少,在大多数实现中都是这种情况,但请注意,LAST仅当列表不是循环时才定义它:

list---列表,可以是点列表,但不能是循环列表。

这就是为什么这里的行为实际上是未定义的。


以上是关于mapcon及其假定等价的问题(apply#'ncconc(maplist…))的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>