通过列表循环的神秘方案程序

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#}等。

显然，这是通过返回一个列表和另一个过程的一对来循环遍历列表的。但这是如何工作的呢?我只看到它用参数列表替换了最后的'()，而不是用任何模糊的lambda函数…#0和#0到底是什么意思?

Answer 1

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

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

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

总而言之:pro过程获得一个适当的列表作为其输入，并返回相同的列表，但最后一个元素指向它的第一个元素——一个循环列表。

Answer 2

#0=表示对某些数据的共享标记，#0#表示对先前标记的数据的引用。请参阅http://docs.racket-lang.org/reference/shared.html底部的示例。函数不返回一对东西，只返回一个值——定义体中的最后一个表达式，即lst。但是正如您可能意识到的那样，最后的lst可能已经发生了突变，因此它与最初传递给函数时的情况不同。(您使用术语"循环"，这正是这个函数所做的，但不完全是在您的问题中应用它的意义。)