从列表创建无限流

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)，我应该如何传入原始列表？

** 我不能使用 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)

参数是一个 list 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))which 调用(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是：构造一个无限的重复元素 from 流，orig-xs但在第一个“回合”中，使用元素 fromxs代替。

这里有些例子：

(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 ...)