Stream of all pairs of elements of infinite stream

Question

How to define a procedure return all pairs of elements in an infinite stream s?

s = {1,2,3,4,5,6,...}
=> {(2,1), (3,2), (3,1), (4,3), (4,2), (4,1), ......}

Here is my code, however it didn't work like a stream, it keep running infinitely and ran out of memory.

(define (stream-pairs s)
    (define (iter s save)
            (stream-append (stream-map (lambda (x) (stream-cons (stream-first s) x))
                                       save)
                           (iter (stream-rest s) (stream-cons save (stream-first s)))))
    (iter s empty-stream))

(define A (stream-cons 1 (scale-stream 2 A)))

(define C (stream-pairs A))

A = {1,2,4,8,16,......}

https://stackoverflow.com/questions/20470010/collect-successive-pairs-from-a-stream is not a duplicate: it is Java-specific, and the answers are Java-specific. — Will Ness, Jun 05 '16 at 12:35
next time, do post all the relevant code and examples when you ask the question, not 14 hours later. — Will Ness, Jun 05 '16 at 13:05

Will Ness · Accepted Answer · 2016-06-09T13:33:38.253

Turns out, Racket's stream-append does not delay its last (at least) argument, so iter calls stream-append which calls iter ... thus the loop.

One way is to reimplement the stream-append fused with the stream-map as used here, as a simple recursive function. That way the tail will be properly under the guard of the delaying stream-cons.

Another is to take a stream-rest¹ of a fake stream-cons:

(require racket/stream)

(define (stream-pairs s)
    (define (iter s save)
            (stream-append (stream-map (lambda (x) (list (stream-first s) x))
                                       save)       ;^^^^
                           (stream-rest
                            (stream-cons 'fake  ;<<-----------------
                                 (iter (stream-rest s) 
                                       (stream-cons (stream-first s) save))))))
    (iter s empty-stream))

(define A (stream-cons 1 (stream-map add1 A))) ; easier to follow

(define C (stream-pairs A))

Also, there was another error in your code where stream-cons was used instead of plain list, to pair up the elements of save with a current element of the input stream. Now we have

> (for ((i (in-range 0 12))) (display (stream-ref C i)))
(2 1)(3 2)(3 1)(4 3)(4 2)(4 1)(5 4)(5 3)(5 2)(5 1)(6 5)(6 4)

¹ cf.,

> (stream-rest (stream-cons 1 (/ 1 0)))
#<stream>

(iter (stream-rest s) (stream-cons (stream-first s) save)) You mean this? It still ran infinitely. — AnhNg, Jun 05 '16 at 15:28

C. K. Young · Answer 2 · 2016-06-04T22:18:53.163

Since the question specified that the given stream is infinite:

(define (stream-pairs strm)
  (stream-cons (cons (stream-first strm)
                     (stream-first (stream-rest strm)))
               (stream-pairs (stream-rest (stream-rest strm)))))

(If the stream is not infinite, you need to add an emptiness guard to the front of the function.)

Note: If you're using SRFI 41 streams instead of Racket streams, change define to define-stream.

score 0 · Answer 3 · answered Jun 04 '16 at 22:47

I'm unclear as what you mean by 'pairs of a stream', but assuming you want something like this:

> (stream-subset-pairs (in-naturals) 5) 
'((0 . 1) (1 . 2) (2 . 3) (3 . 4))

With that as the expected output, here is a solution:

(define (stream-subset-pairs stream i)
  (define subset ; collect all elements up to i by iterating over the list and all #'s in sequence
    (for/list ([element stream]
               [position (in-naturals)]
               #:break (= position i)) ; break when we have reached the # of elements we want to collect
      element))
  (let-values ([(ignore result) ; wrapper because we want for/fold to produce one result (last-element is just a state variable)
                (for/fold ([last-element null]
                           [result empty])
                          ([element subset]) ; iterate through the subset
                  (values element (if (null? last-element) ; if we are on the first loop
                                      result ; ignore it
                                      (cons (last-element element) result))))]) ; else add a pair of the last result and this result
    result))

Stream of all pairs of elements of infinite stream

3 Answers3