Gmail Calendar Documents Reader Web more »
Recently Visited Groups | Help | Sign in
Google Groups Home
Message from discussion Stream problem redux
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Joe Marshall  
View profile  
 More options Jun 28 2002, 8:11 pm
Newsgroups: comp.lang.scheme
From: "Joe Marshall" <prunesqual...@attbi.com>
Date: Sat, 29 Jun 2002 00:11:27 GMT
Local: Fri, Jun 28 2002 8:11 pm
Subject: Stream problem redux
Ok, this time I tested it more thoroughly and I am not
relying on the underlying implementation.

(define (integers-from n)
  (cons n (delay (integers-from (+ n 1)))))

(define jrm-stream-ref
  (letrec ((loop (lambda (stream index)
                   (cond ((not (pair? stream)) (error 'stream-ref 0))
                         ((zero? index) (car stream))
                         (else (loop (force (cdr stream)) (- index 1)))))))
    loop))

(define jrm-stream-filter
  (letrec ((loop (lambda (predicate stream)
                   (cond ((not (pair? stream))
                          (if (null? stream)
                              '()
                              (error stream 'stream-filter 1)))
                         ((predicate (car stream))
                          (cons (car stream)
                                (delay (loop predicate (force (cdr stream))))))
                         (else (loop predicate (force (cdr stream))))))))
    loop))

(define (demo-stream-problem n)
  (jrm-stream-ref
    (jrm-stream-filter
      (lambda (x) (zero? (modulo x n)))
      (integers-from 0))
    3))

(demo-stream-problem n) consumes O(n) memory rather than constant
memory.  I believe that it ought not do so (though I understand
the mechanism through which it does), but that `fixing' the problem
is very difficult (though I believe it *can* be done, albiet with
considerable work).  The reason that I believe that it ought not
run in O(n) time is because computing element n+1 of the integers
stream requires only the single prior element and filtering a
stream requires none of the prior elements.

I have actually run and tested this code on multiple scheme
implementations with the same results.  (The prior posting I
just tested on one implementation.  Mea culpa.)

--
~jrm
http://home.attbi.com/~prunesquallor/


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2009 Google