Создать бесконечный поток из списка

Question

Я пытаюсь создать бесконечный поток из списка, используя ракетку. Мне сказали не использовать set!. Инструкция состоит в том, чтобы создать локальную среду для хранения копии списка, чтобы я мог использовать копию, когда повторяющийся список пуст.

Например, если у меня есть список (a, b) (я знаю, что это не то, как ракетка представляет списки, а просто для облегчения чтения), я хочу получить бесконечный поток (a, b, a, b, a, b, ...)

Вот текущий код, который у меня есть.

(define (copy l) (stream l))

(define (infinite-stream l)
  (if (stream-empty? l)
      (infinite-stream (copy l))
      (stream-cons (stream-first l) (infinite-stream (stream-rest l)))))

и, очевидно, это не работает. после проверки (if (stream-empty? l), как мне перейти в исходный список?

** Я не могу использовать для l oop!

Спасибо! дайте мне знать, если что-то неясно.

Answer 1

Итак, мы хотим построить infinite-stream, который преобразует список элементов в поток элементов, который бесконечно повторяет список ввода.

;; infinite-stream :: list -> stream
(define (infinite-stream xs)
  ...)

Давайте также напишем несколько примеров, чтобы напомнить нам, как все должно происходить работа:

(stream->list (stream-take (infinite-stream (list 1 2 3)) 10))
;; expect (list 1 2 3 1 2 3 1 2 3 1)

Аргументом является список xs, поэтому, как обычно, есть две возможности: либо empty, либо cons. Следовательно, мы можем выполнить анализ случая.

;; infinite-stream :: list -> stream
(define (infinite-stream xs)
  (cond
    [(empty? xs) ...]
    [else ;; here we have (first xs) and (rest xs) available
          ...]))

Что мы должны делать в базовом случае, когда xs равно empty? Давайте посмотрим на наш пример. В какой-то момент (infinite-stream (list 1 2 3)) вызовет (infinite-stream (list 2 3)), что вызовет (infinite-stream (list 3)), а затем вызовет (infinite-stream (list)). Но сейчас мы застряли! На данный момент мы все еще хотим генерировать бесконечно больше элементов, но у нас нет никакой информации, которую мы могли бы использовать вообще, потому что аргумент просто empty. Данные 1, 2 и 3 нам недоступны, но мы нуждаемся в них для продолжения процесса.

Итак, давайте предположим, что мы волшебным образом имеем очень оригинальные данные orig-xs доступно для нас (и давайте переименуем функцию в infinite-stream-helper):

;; infinite-stream-helper :: list, list -> stream
(define (infinite-stream-helper xs orig-xs)
  (cond
    [(empty? xs) ...]
    [else ;; here we have (first xs) and (rest xs) available
          ...]))

Значение infinite-stream-helper заключается в следующем: создать бесконечный поток повторяющихся элементов из orig-xs, но в первом » round ", вместо этого используйте элементы из xs.

Вот несколько примеров:

(stream->list (stream-take (infinite-stream-helper (list) (list 1 2 3)) 10))
;; expect (list 1 2 3 1 2 3 1 2 3 1)

(stream->list (stream-take (infinite-stream-helper (list 3) (list 1 2 3)) 10))
;; expect (list 3 1 2 3 1 2 3 1 2 3)

(stream->list (stream-take (infinite-stream-helper (list 2 3) (list 1 2 3)) 10))
;; expect (list 2 3 1 2 3 1 2 3 1 2)

(stream->list (stream-take (infinite-stream-helper (list 1 2 3) (list 1 2 3)) 10))
;; expect (list 1 2 3 1 2 3 1 2 3 1)

Теперь можно написать базовый вариант! Я оставлю вас, чтобы заполнить его. Подсказка: каким должен быть результат (infinite-stream-helper (list) (list 1 2 3))? Как этот результат связан с результатом (infinite-stream-helper (list 1 2 3) (list 1 2 3))?

Теперь, что для рекурсивного случая, что мы должны делать? Давайте посмотрим на пример. Предположим теперь, что мы имеем дело с (infinite-stream-helper (list 2 3) (list 1 2 3)), что должно привести к потоку 2 3 1 2 3 1 2 3 ....

Это просто помещает 2 перед потоком 3 1 2 3 1 2 3 .... Мы знаем, как построить поток 3 1 2 3 1 2 3 ...? Да! Это просто (infinite-stream-helper (list 3) (list 1 2 3))!

;; infinite-stream-helper :: list, list -> stream
(define (infinite-stream-helper xs orig-xs)
  (cond
    [(empty? xs) ... FILL THIS IN ...]
    [else (stream-cons (first xs) (infinite-stream-helper (rest xs) orig-xs))]))

Но мы еще не закончили. То, что мы изначально хотим, это infinite-stream, а не infinite-stream-helper, но теперь должно быть легко определить infinite-stream из infinite-stream-helper.

;; infinite-stream :: list -> stream
(define (infinite-stream xs)
  ... FILL THIS IN ...)

Answer 2

Что вы описываете (в псевдокоде; быть жирным шрифтом об этом)

cycle xs  =  xs, xs, xs, xs, xs, xs .......

, где xs - это список ввода, а , - как последовательность оператор конкатенации.

Это один и тот же xs во всем, бесконечное число раз, что по понятным причинам немного пугающе и запутанно.

Но если мы посмотрим поближе, мы увидим, что это то же самое, что и

cycle xs  =  xs, (xs, xs, xs, xs, xs .......)
          =  xs, cycle xs

, поэтому проблема сводится к реализации оператора конкатенации, где у нас теперь есть только два потока, чтобы использовать его с - один эквивалент списка ввода xs, а другой - просто вызов cycle:

(define (cycle xs)
    (stream-concat (list-stream xs) (cycle xs)))

Define stream-concat.

Определить list-stream.

Готово. Или, если вы хотите быть более эффективным в этом, объедините два определения внутри cycle более высокого уровня вместе в более эффективное определение.