list - 循环列表的神秘方案程序

Question

这个过程给我带来了麻烦:

(define (pro lst)
  (define (inner l)
    (if (null? (mcdr l))
        (set-mcdr! l lst)
        (inner (mcdr l))))
  (inner lst)
  lst)

使用 (mlist 1 2 3) 作为参数，我得到 #0={1 2 3 。 #0#} 返回。 (mcdr (pro (mlist 1 2 3))) 返回 #0={2 3 1 。 #0#}, (mcdr (mcdr (pro (mlist 1 2 3)))) 返回 #0={3 1 2 。 #0#}等等。

很明显，这是通过返回一对列表和另一个过程来循环列表的。但这是如何运作的呢？我只看到它用参数 lst 替换了final'()，但没有用任何晦涩的 lambda 函数替换... #0 和 #0# 到底是什么意思？

Answer 1

在表达式#0={1 2 3 . #0#}，将 #0= 视为 anchor ，将 #0# 视为该 anchor 的链接 - 即列表中的第一个三个元素是1 2 3，但第四个元素是指向列表开头的指针，因此形成一个三元素循环列表。如果您继续前进该列表(通过连续的 mcdr)，您将看到一个循环模式 1 2 3 1 2 3 ... 的三元素列表，始终显示第四个元素跳回到第一个元素。

研究上面的函数可以清楚为什么会发生这种情况。 pro 过程只是在 lst 参数上调用 inner(一个正确的列表，一个以 null 作为最后一个的列表) element)，然后返回修改后的 lst，有趣的部分是 inner 中发生的事情:

• (if (null? (mcdr l)):如果我们位于列表的最后一个非空元素，则替换下一个元素(应该是 null 在正确的列表中)，通过对第一个元素的引用，我们知道它位于 lst 参数中:(set-mcdr! l lst)<
• 否则，继续浏览列表:(inner (mcdr l))

总结一下:pro 过程获取一个正确的列表作为其输入，并返回相同的列表，但最后一个元素指向其第一个元素 - 一个循环列表。