list - 从列表创建无限流

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 循环！

谢谢！让我知道是否有任何不清楚的地方。

标签： liststreamschemeracketinfinite

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 call (infinite-stream (list 3))which then call (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是：构造一个无限的重复元素流 fromorig-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 ...)