Home > Archive > Scheme > December 2006 > Stream problem
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
|
| I'm having some trouble wrapping my head around streams. I made this
problem for myself, which is probably pretty easy, though not being
used to this paradigm, I can't quite get it to work.
Stream Problem: Create an infinite stream with the following pattern:
1121123211234321123454321...that is, the first item is 1, the second
item is 1, the third item is 2, the fourth item is 1...etc.
The pattern is made more clear if I add some artibrary spaces as
follows:
1 121 12321 1234321 ...
I made some notes below. As you can see I'm kind of stuck. Can someone
give me a hint or suggest a better way to approach the problem?
; Notes:
; this is just theoretical, obviously infinite lists can't be appended
; but I'm trying to use it to model an infinite stream
(up-and-down-forever 1)
(define (up-and-down-forever n)
(append (up-and-down n)
(up-and-down-forever (+ n 1))))
(define (up-and-down n)
(let ((up (interval 1 (- n 1))))
(append up (list n) (reverse up))))
(define (interval n1 n2)
(if (> n2 n1)
'()
(cons n1 (interval (+ 1 n1) n2))))
; So then I was trying to leverage the above, just make minor
; changes and make it into a stream, but it isn't working:
(define (up-and-down-forever-stream n)
; stream-append can only be used on finite streams though,
; so can't use that here
; How about:?
(cons-stream 1 (up-and-down-forever 1))
; But that won't work because (up-and-down-forever 1) isn't
; returning just one item like I want it to, but rather an infinite
; list
; ? help ?
| |
| rickxu 2006-11-24, 7:02 pm |
| "H. =D0=B4=B5=C0=A3=BA
"
> I'm having some trouble wrapping my head around streams. I made this
> problem for myself, which is probably pretty easy, though not being
> used to this paradigm, I can't quite get it to work.
>
> Stream Problem: Create an infinite stream with the following pattern:
> 1121123211234321123454321...that is, the first item is 1, the second
> item is 1, the third item is 2, the fourth item is 1...etc.
> The pattern is made more clear if I add some artibrary spaces as
> follows:
> 1 121 12321 1234321 ...
>
Actually, we can make some trick with stream-append, just as follows:
(define (interval n1 n2)
(if (> n1 n2)
'()
(cons n1 (interval (+ 1 n1) n2))))
(define (up-and-down n)
(let ((up (interval 1 (- n 1)))
(streamize (lambda (alist) (apply stream alist))))
(stream-append (streamize up)
(stream n)
(streamize (reverse up)))))
(define (up-and-down-forever n)
(let ((first-part (up-and-down n)))
(cons-stream (stream-car first-part)
(stream-append (stream-cdr first-part)
(up-and-down-forever (+ n 1))))))
| |
| rickxu 2006-11-24, 7:02 pm |
|
"H. =D0=B4=B5=C0=A3=BA
"
> I'm having some trouble wrapping my head around streams. I made this
> problem for myself, which is probably pretty easy, though not being
> used to this paradigm, I can't quite get it to work.
>
> Stream Problem: Create an infinite stream with the following pattern:
> 1121123211234321123454321...that is, the first item is 1, the second
> item is 1, the third item is 2, the fourth item is 1...etc.
> The pattern is made more clear if I add some artibrary spaces as
> follows:
> 1 121 12321 1234321 ...
A more magic one is:
(define (get-needed-value i)
(let* ((index (inexact->exact (floor (sqrt i))))
(offset (- i (square index)))
(up (interval 1 index))
(up-and-down (append up
(list (+ index 1))
(reverse up))))
(list-ref up-and-down offset)))
| |
|
|
> A more magic one is:
> (define (get-needed-value i)
> (let* ((index (inexact->exact (floor (sqrt i))))
> (offset (- i (square index)))
> (up (interval 1 index))
> (up-and-down (append up
> (list (+ index 1))
> (reverse up))))
> (list-ref up-and-down offset)))
That is pretty magic.
I used:
(define magic (cons-stream 1 (stream-map get-needed-value integers)))
and it was beautiful.
| |
|
|
> Actually, we can make some trick with stream-append, just as follows:
> (define (interval n1 n2)
> (if (> n1 n2)
> '()
> (cons n1 (interval (+ 1 n1) n2))))
>
> (define (up-and-down n)
> (let ((up (interval 1 (- n 1)))
> (streamize (lambda (alist) (apply stream alist))))
> (stream-append (streamize up)
> (stream n)
> (streamize (reverse up)))))
>
> (define (up-and-down-forever n)
> (let ((first-part (up-and-down n)))
> (cons-stream (stream-car first-part)
> (stream-append (stream-cdr first-part)
> (up-and-down-forever (+ n 1))))))
Neither of the two implementations I use have "stream" as a defined
procedure. Do you have it predefined somewhere?
| |
| rickxu 2006-11-24, 7:02 pm |
|
"H. =D0=B4=B5=C0=A3=BA
"
>
> Neither of the two implementations I use have "stream" as a defined
> procedure. Do you have it predefined somewhere?
(define (stream . args)
(if (null? args)
the-empty-stream
(cons-stream (car args) (apply stream (cdr args)))))
| |
| olivercpierson@googlemail.com 2006-11-24, 7:02 pm |
| H. wrote:
> I'm having some trouble wrapping my head around streams. I made this
> problem for myself, which is probably pretty easy, though not being
> used to this paradigm, I can't quite get it to work.
>
> Stream Problem: Create an infinite stream with the following pattern:
> 1121123211234321123454321...that is, the first item is 1, the second
> item is 1, the third item is 2, the fourth item is 1...etc.
> The pattern is made more clear if I add some artibrary spaces as
> follows:
> 1 121 12321 1234321 ...
>
> I made some notes below. As you can see I'm kind of stuck. Can someone
> give me a hint or suggest a better way to approach the problem?
>
> ; Notes:
> ; this is just theoretical, obviously infinite lists can't be appended
> ; but I'm trying to use it to model an infinite stream
> (up-and-down-forever 1)
>
> (define (up-and-down-forever n)
> (append (up-and-down n)
> (up-and-down-forever (+ n 1))))
>
> (define (up-and-down n)
> (let ((up (interval 1 (- n 1))))
> (append up (list n) (reverse up))))
>
> (define (interval n1 n2)
> (if (> n2 n1)
> '()
> (cons n1 (interval (+ 1 n1) n2))))
>
> ; So then I was trying to leverage the above, just make minor
> ; changes and make it into a stream, but it isn't working:
> (define (up-and-down-forever-stream n)
> ; stream-append can only be used on finite streams though,
> ; so can't use that here
> ; How about :?
> (cons-stream 1 (up-and-down-forever 1))
> ; But that won't work because (up-and-down-forever 1) isn't
> ; returning just one item like I want it to, but rather an infinite
> ; list
> ; ? help ?
SICP has a great section on streams. After looking at your proposed
problem, I thought it might be interesting to solve it using implicitly
defined streams. So I borrowed some code from the book and went at it.
Here's what I got:
;;code form section 3.5 in sicp
(define (stream-map proc . argstreams)
(if (stream-null? (car argstreams))
the-empty-stream
(cons-stream
(apply proc (map stream-car argstreams))
(apply stream-map
(cons proc (map stream-cdr argstreams))))))
(define (add-streams s1 s2)
(stream-map + s1 s2))
(define ones (cons-stream 1 ones))
(define integers (cons-stream 1 (add-streams ones integers)))
(define (enumerate-interval a b)
(if (> a b)
'()
(cons a
(enumerate-interval (+ a 1) b))))
;; end code from sicp
;;your code slightly altered
(define (up-and-down n)
(let ((up (enumerate-interval 1 (- n 1))))
(append up (list n) (reverse up))))
(define pattern (stream-map up-and-down integers))
(define (stream-accum n s) ;;accumulate to nth of s
(if (< n 0)
'()
(append (stream-car s)
(stream-accum (- n 1)
(stream-cdr s)))))
Load into scheme and run
>(stream-accum 5 pattern)
'(1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1)
Thanks for problem. Later.
| |
|
|
> '(1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1)
Can you make it infinite? That's where it gets difficult for me.
| |
| olivercpierson@googlemail.com 2006-11-25, 8:02 am |
| On Nov 25, 7:24 am, "H." <hbe...@gmail.com> wrote:[color=darkred]
It is infinte. Try (stream-accum 10 pattern) or (stream-accum 1000
pattern). It'll go as far as you need it too, as long as you've got
the time. I only defined stream-accum to accumulate a finite portion
of the stream. If you really want a program that will just print this
increasing pattern forever, just drop all the stream operations and use
the normal operations in their place, e.g. map instead of stream-map
and so on. Hope this was the answer your were looking for.
| |
|
|
> It is infinte. Try (stream-accum 10 pattern) or (stream-accum 1000
> pattern). It'll go as far as you need it too, as long as you've got
> the time. I only defined stream-accum to accumulate a finite portion
> of the stream. If you really want a program that will just print this
> increasing pattern forever, just drop all the stream operations and use
> the normal operations in their place, e.g. map instead of stream-map
> and so on. Hope this was the answer your were looking for.
I see. I've examined this more closely now. pattern is the infinite
stream. "pattern" isn't quite what I'm looking for, in the sense that
each item is a list.
Here is a procedure called show-stream which is built in to my scheme
implementation (UCB Stk):
(lambda (strm . args)
(if (null? args) (ss1 strm 10 10) (ss1 strm (car args) (car args))))
I used it to examine the pattern stream:
STk> (ss pattern)
((1) (1 2 1) (1 2 3 2 1) (1 2 3 4 3 2 1) (1 2 3 4 5 4 3 2 1) (1 2 3 4 5
6 5 4 3 2 1) (1 2 3 4 5 6 7 6 5 4 3 2 1) (1 2 3 4 5 6 7 8 7 6 5 4 3 2
1) (1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1) (1 2 3 4 5 6 7 8 9 10 9 8 7 6 5
4 3 2 1) ...)
So what you have here is very close to the problem spec. The problem
I'm trying to solve is slightly different. (ss pattern) should return:
(1 1 2 1 1 2 3 2 1 1...)
(1 1 2 1 1 2 3 2 1
| |
|
|
> Actually, we can make some trick with stream-append, just as follows:
> (define (interval n1 n2)
> (if (> n1 n2)
> '()
> (cons n1 (interval (+ 1 n1) n2))))
>
> (define (up-and-down n)
> (let ((up (interval 1 (- n 1)))
> (streamize (lambda (alist) (apply stream alist))))
> (stream-append (streamize up)
> (stream n)
> (streamize (reverse up)))))
>
> (define (up-and-down-forever n)
> (let ((first-part (up-and-down n)))
> (cons-stream (stream-car first-part)
> (stream-append (stream-cdr first-part)
> (up-and-down-forever (+ n 1))))))
Unfortunately, I still can't quite get this version to work :-(.
I'm using SICP's version of string-append, and it only takes two
arguments, so I'm getting an error: "*** Error:
too many arguments to: (stream-append (streamize up) (stream n)
(streamize (reverse up)))"
For reference, that version is:
(define (stream-append s1 s2)
(if (stream-null? s1)
s2
(cons-stream (stream-car s1)
(stream-append (stream-cdr s1) s2))))
Did you write your version differently?
| |
| rickxu 2006-11-28, 8:04 am |
|
H. wrote:
>
> Unfortunately, I still can't quite get this version to work :-(.
>
> I'm using SICP's version of string-append, and it only takes two
> arguments, so I'm getting an error: "*** Error:
> too many arguments to: (stream-append (streamize up) (stream n)
> (streamize (reverse up)))"
>
> For reference, that version is:
> (define (stream-append s1 s2)
> (if (stream-null? s1)
> s2
> (cons-stream (stream-car s1)
> (stream-append (stream-cdr s1) s2))))
>
> Did you write your version differently?
mit-scheme implementation has stream-append, I used that procedure. If
u want to use SICP's two-parameters version, there is another modified
solution:
(define (interval n1 n2)
(if (> n1 n2)
'()
(cons n1 (interval (+ 1 n1) n2))))
(define (up-and-down n)
(let ((up (interval 1 (- n 1))))
(append up
(list n)
(reverse up))))
(define (up-and-down-forever n)
(let* ((streamize (lambda (alist) (apply stream alist)))
(first-part (streamize (up-and-down n))))
(cons-stream (stream-car first-part)
(stream-append (stream-cdr first-part)
(up-and-down-forever (+ n 1))))))
And three or more parameters STREAM-APPEND version is for u to
implement for your exercise :-)
---
rickxu
| |
|
|
H. wrote:
> I'm having some trouble wrapping my head around streams. I made this
> problem for myself, which is probably pretty easy, though not being
> used to this paradigm, I can't quite get it to work.
>
> Stream Problem: Create an infinite stream with the following pattern:
> 1121123211234321123454321...that is, the first item is 1, the second
> item is 1, the third item is 2, the fourth item is 1...etc.
> The pattern is made more clear if I add some artibrary spaces as
> follows:
> 1 121 12321 1234321 ...
I figured this out. It uses a starred let though, which I guess is a
no-no in the Scheme world. On the plus side, it worked the first time I
tested it, which doesn't usually happen.
(define up-and-down
(infinite-state-machine 0 (list 1 'a)))
(define (infinite-state-machine last-number state)
(let* ((up-to (car state))
(ltr (cadr state))
(going-up? (eq? ltr 'a))
(next-number (max 1 ((if going-up? + -) last-number 1)))
(at-top? (= next-number up-to))
(start-over? (and (= last-number 1) (not going-up?)))
(next-up-to (if at-top? (+ up-to 1) up-to))
(next-letter (if (or start-over? at-top?) (switch ltr) ltr)))
(cons-stream next-number
(infinite-state-machine next-number (list
next-up-to next-letter)))))
(define (switch ltr)
(if (eq? ltr 'a) 'b 'a))
| |
| Andru Luvisi 2006-12-05, 7:03 pm |
|
Several of the answers that have been posted involve using reverse,
which has the di vantage that the later you go in the stream, the
more of it you will need to hold in ram if you are processing and
discarding elements as you go.
(define (going-up x lim)
(cond ((= x lim) (s-cons x (going-down (- x 1) (+ lim 1))))
(else (s-cons x (going-up (+ x 1) lim)))))
(define (going-down x lim)
(cond ((= x 0) (going-up 1 lim))
(else (s-cons x (going-down (- x 1) lim)))))
(define s (going-up 1 1))
Andru
--
Andru Luvisi
Quote Of The Moment:
Quidquid latine dictum sit, altum viditur.
( Whatever is said in Latin sounds profound. )
| |
| Kjetil S. Matheussen 2006-12-06, 4:23 am |
|
On Tue, 5 Dec 2006, H. wrote:
>
> I figured this out. It uses a starred let though, which I guess is a
> no-no in the Scheme world.
Nah, using starred lets is okey. And especially in your case, where there
are variables dependent on previous ones. :-)
|
|
|
|
|