从列表创建无限流

Question

我正在尝试使用 racket 从列表创建无限流。我被告知不要使用 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)，我应该如何传入原始列表？

** 我不能使用 for 循环！

谢谢！如果有任何不清楚的地方，请告诉我。

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-helper.

定义infinite-stream

;; 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，另一个只是对 [= 的调用17=]:

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

定义stream-concat。

定义 list-stream。

完成。或者，如果您想提高效率，请将更高级别 cycle 中的两个定义融合在一起，形成更高效的定义。

从列表创建无限流

Create an infinite stream from a list

scheme

list

stream

infinite

racket