Загадочная схема процедуры зацикливания по спискам

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 #} и т. Д.

Так что, очевидно, это для циклического перемещения по спискам путем возврата пары из списка и другой процедуры.Но как это работает?Я только вижу, что он заменяет final '() параметром lst, но не любой неясной лямбда-функцией ... Что в любом случае означают # 0 и # 0 #?

Answer 1

В выражении #0={1 2 3 . #0#} представьте #0= как привязку и #0# как ссылку на эту привязку - то есть в списке первые три элемента 1 2 3, а четвертый элемент - указательк началу списка, следовательно, формируя круговой список из трех элементов.Если вы продолжите продвигаться по этому списку (последовательно mcdr с), вы увидите список из трех элементов в циклическом шаблоне 1 2 3 1 2 3 ..., всегда показывающий, что четвертый элемент возвращается к первому.

Изучение вышеуказанной функции дает понять, почему это происходит.Процедура pro просто вызывает inner для параметра lst (правильный список, список с 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 в конце потенциально мутировал, так что он отличается от того, который был при первоначальной передаче функции. (Вы используете термин «езда на велосипеде», который в точности соответствует функции этой функции, но не совсем в том смысле, в котором вы применили ее в своем вопросе.)