CODEWITHSUNDEEP
schemelispracket
Ron Marchant
Ron Marchant

Reputation: 61

Accumulator for infinite streams

I'm trying to implement an accumulator for an infinite stream. I've written the following code but it's running into an infinite loop and failing to terminate

(define (stream-first stream) (car stream))
(define (stream-second stream) (car ((cdr stream))))
(define (stream-third stream) (car ((cdr ((cdr stream))))))
(define (stream-next stream) ((cdr stream)))


(define (stream-foldl func accum stream)
    (cond
         [(empty? stream) accum]
         [else (stream-foldl func (func (stream-first stream) accum) (stream-next stream))] ))

I've written up a few tests to demonstrate what I'm trying to implement 

(define (natural-nums)
   (define (natural-nums-iter n)
   (thunk
   (cons n (natural-nums-iter (+ n 1)))))
   ((natural-nums-iter 0)))

(define x (stream-foldl cons empty (natural-nums)))
(check-equal? (stream-first x) empty)
(check-equal? (stream-second x) (list 0))
(check-equal? (stream-third x) (list 1 0))

(define y (stream-foldl (curry + 1) 10 (naturals)))
(check-equal? (stream-first y)  10)
(check-equal?  (stream-second y) 11)
(check-equal?  (stream-third y)  13)

Here's a trace of my stream-foldl function 

>(stream-foldl
  #<procedure:cons>
  '()
  '(0 . #<procedure:...9/saccum.rkt:25:0>))
()>(stream-foldl
  #<procedure:cons>
  '(0)
  '(1 . #<procedure:...9/saccum.rkt:25:0>))
(0)>(stream-foldl
  #<procedure:cons>
  '(1 0)
  '(2 . #<procedure:...9/saccum.rkt:25:0>))
(1 0)>....

I believe I'm failing to properly set a base case, thus never terminating from the recursion call

Upvotes: 3

Views: 582

Answers (1)

Flux
Flux

Reputation: 10950

Fold is supposed to look at every element in the stream, then produce a result based on those elements. With an infinite stream, it is no surprise that the fold does not terminate (how would you be able to look at every single element in an infinite stream?).

What you can do:

Produce a finite stream out of the infinite stream. stream-take can be used for that. Example implementation of stream-take:

;; Returns a stream containing the first n elements of stream s.
(define (stream-take n s)
  (cond ((zero? n) empty-stream)
        ((empty? s) (error "Stream is shorter than n")
        (else
          (delay (stream-first s)
                 (stream-take (- n 1) (stream-rest s)))))))
          ; Note: 'delay' is the same as the 'thunk' in your code.

Then, fold the finite stream either using your implementation of fold, or stream-fold.

Upvotes: 3

Related Questions