Streams in Scheme - define integers through stream map in scheme

Question

How can I define integers through stream-map in Scheme:

(define integers (stream-cons 1 (stream-map *something* *something*))

Tapis

Answer 1

(define integers
  (stream-cons 1
    (stream-map add1 integers)))

See SRFI-41 for more about streams.

Coulee

Answer 2

The answer by @user448810 is perfect and it will work in Racket (it uses Racket-specific procedures). But the question is also tagged with SICP, so here is my two cents.

Answering the question with only the subset of Scheme's procedures available in SICP yields an equivalent but slightly different solution, using only the following primitive stream operations defined in the book: stream-null? stream-cons stream-car stream-cdr. In particular, notice that stream-map is not a standard part of Scheme, and in the book it was implemented in terms of primitive operations, with an advantage over Racket's implementation - it can receive a variable number of streams as parameters:

(define (stream-map proc . args)
  (if (stream-null? (car args))
      the-empty-stream
      (stream-cons (apply proc (map stream-car args))
                   (apply stream-map (cons proc (map stream-cdr args))))))

(define (add-streams s1 s2)
  (stream-map + s1 s2))

With the above procedures in place, it's easy to define integers

(define ones (stream-cons 1
                          ones))

(define integers (stream-cons 1
                              (add-streams ones integers)))

---

In reality, the stream-map procedure above is affected by a bug, which becomes apperent if we feed to it two streams of which the second is shorter than the first, like this:

(stream-map + (cons-stream 1 the-empty-stream) the-empty-stream)

The proposed implementation of stream-map will take the else branch of the if, because (stream-null? (car args)) is (stream-null? (cons-stream 1 the-empty-stream)), which is false, hence it will try evaluate (map stream-car args) which will in turn try to evaluate (stream-car the-empty-stream), causing a runtime failure.

Here's a possible fix for the stream-map procedure:

(define (any . args) ; takes any numer of booleans and or-s them together
  (if (null? args)
    #f
    (or (car args) (apply any (cdr args)))))

(define (stream-map proc . args)
  (if (apply any (map stream-null? args))
    the-empty-stream
    (cons-stream (apply proc (map stream-car args))
                 (apply stream-map (cons proc (map stream-cdr args))))))

Tenuis

I think SICP's implementation of the "variadic" stream-map is bugged. It breaks if the first stream is not empty when another one become empty. In that case, (stream-null? (car args)) will return false, and the else branch of the if will try to to apply stream-car to all streams via (map stream-car args), thus resulting in a runtime error. – Luciferous

I fixed it, in case some reader could be confused. – Luciferous

Answer 3

You can also use the example from SICP:

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define nats (integers-starting-from 1))

Monolithic