RE: streams

["Will Fitzgerald" <fitzgerald@inetmi.com>]

Here's an implementation of streams in MzScheme. It's a bit wierd because I
wanted it to run (a) in a Common Lisp compatibility package I wrote, and (b)
it was like some other code we'd originally written in CL (based on Peter
Novig's code). I *think* it implements a superset of the SICP stream
procedures. It it formats badly in email, I'll send a text file directly on
request.


(define the-empty-stream '())
(define stream-null? null?)

(define-macro stream-delay
  (lambda (computation)
    `(lambda () ,computation)))

;; we don't use DELAY for CL compatibility...
(define-macro cons-stream
  (lambda (the-car the-cdr)
    `(cons ,the-car (stream-delay ,the-cdr))))

(define (stream-car stream) (car stream))

;; unlike sicp, but like Norvig, we change the stream on stream-cdr
(define (stream-cdr stream)
  (let ((theCdr (cdr stream)))
    (when (procedure?  theCdr)
      (set-cdr! stream (theCdr)))
    (cdr stream)))

(define (stream-ref s n)
  (if (< n 0)
    (error "Invaid STREAM-REF index:" n)
    (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1)))))

(define (stream-enumerate-interval low high)
  (if (> low high)
    the-empty-stream
    (cons-stream low
                 (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(define (stream-filtering pred stream)
  "runs pred, keeps if non-#f"
  (if (stream-null? stream) the-empty-stream
      (let ((val (pred (stream-car stream))))
        (if val (cons-stream val (stream-filtering pred (stream-cdr
stream)))
        (stream-filtering pred (stream-cdr stream))))))


(define (stream-map proc stream)
  (cond ((stream-null? stream) the-empty-stream)
        (else (cons-stream (proc (stream-car stream))
                           (stream-map proc (stream-cdr stream))))))

(define (stream-append stream1 stream2)
  (if (stream-null? stream1) stream2
      (cons-stream (stream-car stream1)
                   (stream-append (stream-cdr stream1) stream2))))

(define (stream-append-filtering pred stream)
  "Map pred over stream, delaying all but the first pred call,
   appending results, filtering along the way"
  (if (stream-null? stream)
    the-empty-stream
    (let* ((head (stream-car stream))
           (tail (stream-cdr stream))
           (result (pred head)) )
      (if (not (stream-null? result))
        (cons-stream (stream-car result)
                   (stream-append (stream-cdr result)
                                 (stream-append-filtering pred tail)))
        (stream-append-filtering pred tail)))))

(define (stream-for-each proc stream)
  (cond ((stream-null? stream) (values))
        (else (proc (stream-car stream))
              (stream-for-each proc (stream-cdr stream)))))

(define (stream-force stream)
  (stream-for-each (lambda (i) i) stream)
  stream)

; take the first (upto) n items from stream.
(define (stream-take stream count)
  (if (or (<= count 0) (stream-null? stream))
    '()
      (cons (stream-car stream)
            (stream-take (stream-cdr stream) (- count 1)))))

;; some useful streams

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

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


> -----Original Message-----
> From: owner-plt-scheme@fast.cs.utah.edu
> [mailto:owner-plt-scheme@fast.cs.utah.edu]On Behalf Of ktpr
> Sent: Thursday, October 26, 2000 12:58 PM
> To: Shriram Krishnamurthi
> Cc: plt-scheme@fast.cs.utah.edu
> Subject: Re: streams
>
>
>
>
> Shriram Krishnamurthi wrote:
> >
> > You can easily add streams with a few instructions.  Maybe your
> > instuctor already has these handy?  (Are you taking a course at BU?
> > If so, can you send me your course home page URL?  Thanks!)
>
>
> Thank you both for you quick reply. I was afraid that the list was dead
> or something and I would get no support.
>
> 	My course's home page is at
> http://www.cs.bu.edu/faculty/kfoury/CS320-Fall00/home.html
> My teacher has not provided any implementation for Dr. Scheme and
> probably does not intend to. He uses MIT scheme, whose win32 package is
> pretty ugly.
>
> 	To implement streams I would need an implementation of head
> and tail. I
> understand that a thunk would be used in the implementation of tail. I
> would have to use "promise" in tail to allow for lazy evaluation. I am
> sure the implementation isn't has simple as
>
> [rough pseudo]
> 	(cond ((stream-car) (car lst))
> 	     ((stream-cdr) (display cadr lst "promise"))
> 	     (else display "error"))
>
> 	And i suspect it goes a little more low level than i have
> time for to
> do this assignment involving streams. Since this is not a homework
> problem in itself, this request for an implementation is not cheating
> (at least in my view). (Alternatively, I could just use the MIT win32
> version of Scheme.) So here it is: Could someone be so kind as to
> provide me with a stream implementation or direct me to a library that
> already has one.
>
> 	In any case, any help would be appreciated.
>
> thank you for your time,
> ktpr
>