Create an infinite stream from a list

Question

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.

Answer 1

The existing answers are good, but they require writing auxiliary functions.

If we take this answer's sketch of a higher-order approach, we can write our function using only what is available to us in the standard library:

(define (cycle xs)
  (stream-append (in-list xs)
                 (stream* (cycle xs))))

Breaking this down:

• stream-append lets us treat arbitrarily many streams as one unified stream in-sequence.
• in-list converts a list to a stream, frequently used in for clauses.
• stream* lets us delay the evaluation of something that we promise will return a stream when it is needed. Note that the argument is not evaluated immediately, or else our function would not terminate.
• cycle is, of course, a recursive call to our own function.

And we can see it in action in the REPL:

> (stream->list (stream-take (cycle '(1 2 3)) 10))
'(1 2 3 1 2 3 1 2 3 1)

Answer 2

(define (list->infstream lst)
    (define (list->stream l)
      (cond ((null? l) (list->infstream lst))
            (else (stream-cons (car l) (list->stream (cdr l))))))
    (list->stream lst))

Instead of returning empty-stream when at end of the list, return a new inifinite stream!

For testing, you need

(define (stream-take stream n)
  "Take first n elements of stream lazily"
  (if (zero? n)
      empty-stream
      (stream-cons (stream-first stream)
                   (stream-take (stream-rest stream) (- n 1)))))

To first make out of the infinite stream first a finite stream.

(stream->list (stream-take (list->infstream '(a b c)) 10))
;;=> '(a b c a b c a b c a)

Answer 3

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

Answer 4

What you describe is (in pseudocode; being bold about it)

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

where xs is the input list, and , is intended as a sequence-concatenation operator.

It's the same xs all over, infinite number of times, which is understandably a bit daunting and confusing.

But if we look closer we can see that this is the same as

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

thus the problem is reduced to implementing the concatenation operator where we now have just two streams to use it with -- one equivalent to the input list xs, and the other is just a call to cycle:

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

Define stream-concat.

Define list-stream.

Done. Or if you want to be extra efficient about it, fuse the two definitions inside the higher-level cycle together into a more efficient definition.