Create an infinite stream from a list

I'm trying to create an infinite stream from a list using racket. I was told not to use set!. The instruction is to create a local environment to store a copy of the list so that I can use the copy when the list being iterated is empty.

For example, if I have a list (a, b) (I know this is not how racket represent lists, but just to make it easier to read), I want to get an infinite stream of (a, b, a, b, a, b, ...)

Here is the current code I have.

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

and obviously, it is not working. after checking (if (stream-empty? l), how should I pass in the original list?

** I cannot use for loop!

Thanks! let me know if anything is unclear.

Solution

So, we want to construct infinite-stream which transforms a list of elements into a stream of elements which repeats the input list infinitely.

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

Let's also write some examples to remind us how things should work:

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

The argument is a list xs, so as usual, there are two possibilities: either it's empty or cons. Therefore, we can perform a case-analysis on it.

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

What should we do in the base case, when xs is empty? Let's take a look at our example. At some point, (infinite-stream (list 1 2 3)) would call (infinite-stream (list 2 3)) which calls (infinite-stream (list 3)) which then calls (infinite-stream (list)). But now we are stuck! At this point, we still want to generate infinitely many elements more, but we don't have any information that we can use at all, because the argument is just empty. The data 1, 2, and 3 are not available to us, but we need them to continue the process.

So, instead, let's suppose that we magically have the very original data orig-xs available to us (and let's rename the function to 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
          ...]))

The meaning of infinite-stream-helper is: construct an infinite stream of repeating elements from orig-xs but in the first "round", use elements from xs instead.

Here are some examples:

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

It is now possible to write the base case! I will leave you to fill it up. Hint: what should be the result of (infinite-stream-helper (list) (list 1 2 3))? How is that result related to the result of (infinite-stream-helper (list 1 2 3) (list 1 2 3))?

Now, for the recursive case, what should we do? Let's take a look at the example. Suppose now we are dealing with (infinite-stream-helper (list 2 3) (list 1 2 3)) which should result in a stream of 2 3 1 2 3 1 2 3 ....

That's just putting 2 in front of a stream of 3 1 2 3 1 2 3 .... Do we know how to construct a stream of 3 1 2 3 1 2 3 ...? Yes! That's just (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))]))

But we are not quite done. What we originally want is infinite-stream, not infinite-stream-helper, but it should now be easy to define infinite-stream from infinite-stream-helper.

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