Streams questions

Hi,

I need to work with streams, I'm reading the racket reference and I have some questions.

  1. Why stream-map doesn't accept more than one stream? I read that the one in SRFI-41 does.
  2. Why the function f is sometimes procedure? and sometimes (-> any/c any/c ... any/c)

  3. Why there are dots ... in (-> any/c any/c ... any/c)?

Matteo

Hi, @matteo-daddio.

Your questions (2/3) tickled me somewhat.

I think it is more explicit in the second signature, because the function takes a variable number of arguments, of which the first is always the accumulator, and the rest are the values produced by the stream, e.g.

Folds f over each element of s with i as the initial accumulator. If s is infinite, this function does not terminate. The f function takes the accumulator as its first argument and the next stream element as its second.

(stream-fold
 (lambda (x y z) x)
 3
 (for/stream ([i (in-range 10)])
   (values i (* i i))))

I might be wrong, though. Thanks for asking.

Edit:
To be clear, the dots mean "zero or more" in this case. So, "one argument, then zero or more arguments, and then a final argument."

Thanks for your help.

Lists can’t contain multiple values:

(list (values 1 2 3) (values 5 6 7))

It’s not correct, so I thought that was the same for streams.

I think stream-map takes only one stream for performance reasons.

Matteo

I agree that it seems very weird that the stream-map and stream-fold functions spread arguments like that.

Side note: stream-map does the same thing:

(stream-map
 (λ (x y) (list x y))
 (for/stream ([i (in-range 10)])
   (values i (* i i))))

yields '((9 81) (8 64) (7 49) (6 36) (5 25) (4 16) (3 9) (2 4) (1 1) (0 0))

It does have a kind of internal logic to it, I suppose, but at a minimum I would suggest that the documentation of the two functions is inconsistent, and that if there are ellipses (...) in the documentation for the function passed to stream-fold, that there should also be ellipses in the documentation for the function passed to stream-map. Also, it seems to me that the documentation for these functions should definitely make clear that streams returning multiple values will have those values spread across the mapped function.

I'd really be curious to hear what others have to say? Is there history here?

1 Like

So a possible workaround can be:

 (define (two-val-stream s1 s2)
   (stream-cons (values (stream-first s1)
                        (stream-first s2))
                (two-val-stream (stream-rest s1)
                                (stream-rest s2))))

(define str1 (stream 1 2 3))
(define str2 (stream 1 10 100))
(define str3 (two-val-stream str1 str2))

(stream-map * str3)
=> ‘(1 20 300)

But how can this be modified to handle any number of streams?

Matteo

Perhaps something like?

(define (n-val-stream . ss)
  (stream-cons (apply values (map stream-first ss))
               (apply n-val-stream (map stream-rest ss))))

Edit: tsk, tsk.

(define (n-val-stream . ss)
  (cond
    [(stream-empty? (stream-rest (car ss)))
     (stream-cons (apply values (map stream-first ss))
                  (apply values (map stream-rest  ss)))]
    [else
     (stream-cons (apply values       (map stream-first ss))
                  (apply n-val-stream (map stream-rest ss)))]))

Hmm, is this even necessary; I know too little about streams.

Are you sure you can apply values?

I'm pretty sure, yes. But it does seem odd, right?

(define strx (stream 1  2   3))
(define stry (stream 1 10 100))
(define strz (stream 1 10 100))
(define stru (n-val-stream strx stry strz))

> (stream-first (stream-map * stru))
1
> (stream-first (stream-rest (stream-map * stru)))
200
> (stream-first (stream-rest (stream-rest (stream-map * stru))))
30000
> 

Hello.

Python's map and reduce(Racket's foldl) only take one argument either, but there is no problem, because Python heavily relies on zip. Python does not rely on variadic arguments.
In other words, if you had stream-zip, you could handle any number of streams.
To be honest, you had better use SRFI-41, but if you had some reason not to use it, you should implement it yourself.
Fortunately, SRFI-41 shows a referential implementation of stream-zip; thus you do not have to think nor be confused. You can just copy and paste the code, and fix that.
Consequently you would get something like this:

(define (stream-zip . strms)
  (let-syntax ((stream-lambda
                (syntax-rules ()
                  ((_ formals body0 body1 ...)
                   (lambda formals
                     (stream-lazy (let () body0 body1 ...)))))))
    (define (exists? pred strm)
      (and (not (stream-empty? strm))
           (let loop ((head (stream-first strm)) (tail (stream-rest strm)))
             (if (stream-empty? tail)
                 (pred head)
                 (or (pred head)
                     (loop (stream-first tail) (stream-rest tail)))))))
    (define stream-zip
      (stream-lambda (strms)
                     (if (exists? stream-empty? strms)
                         empty-stream
                         (stream-cons (map stream-first strms)
                                      (stream-zip (map stream-rest strms))))))
    (cond ((null? strms) (error 'stream-zip "no stream arguments"))
          ((exists? (lambda (x) (not (stream? x))) strms)
           (error 'stream-zip "non-stream argument"))
          (else (stream-zip strms)))))

Racket does not have stream-lambda, but it is also stated in the SRFI-41's referential implementation. Here it becomes a local macro, or syntax.
There is no explanation for exists in the referential implementation, but it is the stream version of SRFI-1's any. There is its referential implementation, and here it becomes a local function, the modified version of any for streams, too.
You may add this one to your personal utility library.
Anyway, I think you can now handle any number of streams with stream-zip.

> (define strx (stream 1 2 3))
> (define stry (stream 1 10 100))
> (define strz (stream 1 10 100))
> (define stru (stream-zip strx stry strz))
> (stream-first (stream-map (lambda (x) (apply * x)) stru))
1
> (stream-first (stream-rest (stream-map (lambda (x) (apply * x)) stru)))
200
> (stream-first (stream-rest (stream-rest (stream-map (lambda (x) (apply * x)) stru))))
30000
> 
2 Likes

I'd just use SRFI-41functions (It comes with Racket) instead of racket/stream. They're generally compatible with the built in streams, and the library has a lot more functionality.

(require srfi/41)
(println (stream->list (stream-map + (stream 1 2 3) (stream 4 5 6))))
;;; etc.
1 Like

I would really like to know why stream-map in racket accepts only one stream. Why this decision?

It's exactly what @bakgatviooldoos and @jbclements demonstrated: an element in a stream could have multiple values in Racket, and these values are passed as arguments to the function provided to stream-map. If you allow multiple streams, then it risks ambiguity. E.g., the first stream might be a stream of 2 or 3 values. The second stream might be a stream of 4 or 5 values. Now, how many arguments should the function accept? One possibility is to simply concatenate argument lists together, so the answer is either 6, 7, or 8 through case-lambda, but the 7 case could come from either 2 + 5 or 3 + 4, but you would not know which one it is. Etc, etc.

If there's a fixed number of streams that you are working with, you can either use for/stream to create a stream with each input stream as a clause. If it's not fixed, then you can use @bakgatviooldoos's approach (which is exactly what I would do). Or if you don't care about multiple-valued streams at all, then you can use SRFI-41. Choices are yours.

6 Likes

Thank you Sorawee, it’s illuminating.

Why there isn’t a function like n-val-stream?

I apologize if sometimes my words can sound rude or impolite, I don't have much experience with English.

My next question is:
Why there isn’t a stream-foldr procedure?

Matteo

Do not worry, I am a non-native, either. 濃配すんăȘ(笑)。

Simply, a stream can be infinite. You cannot fold something from the end of universe!

There is nothing wrong with foldr on an infinite stream. The only caveat is that it must be lazy on the accumulator, so that the folding function can decide whether to evaluate that at all (think of Haskell fold). Racket is a strict language, but we can use mechanisms like promises to accomplish that. For example, consider the following definition (ignore multiple values, for now)

#lang racket/base
(require racket/stream
         racket/promise)

(define (stream-foldr fn init strm)
  (cond
    [(stream-empty? strm)
     init]
    [else
     (define fst (stream-first strm))
     (define rst (stream-rest strm))
     (define acc (delay (stream-foldr fn init rst)))
     (fn fst acc)]))

We delay the accumulator, so fn can decide whether to force that. Let’s try to define an all to get a feel how to use it.

(define (stream-all pred strm)
  (stream-foldr
   (lambda (fst acc)
     (cond
       [(pred fst) (force acc)]
       [else #f]))
   #t
   strm))

This function terminates if

  • the stream is finite; or
(stream-all positive? (stream 1 2 3 4 5))
  • any element in the stream doesn’t satisfy pred.
(define stream-of-negative-integers
  (stream* -1 (stream-map sub1 stream-of-negative-integers)))
(stream-all positive? stream-of-negative-integers)

In fact, stream-fold just uses sequence-fold under the hood. A definition for sequence-foldr, generalized to multiple values, is left as an exercise :stuck_out_tongue_winking_eye:

1 Like

Also stream-fold doesn’t terminate if the stream is infinite.

I like your example, but unless I'm missing something, it could be computed just as well using a left fold, making it unclear why you'd reach for the stream-foldr in this instance. Are there any compelling examples that are more natural with stream-foldr? My best is something a bit contrived like "return the product of all the numbers after the last zero, but give up completely if the stream contains any negative numbers".

The difference is that stream-fold (strict or not) only terminates if the stream is finite, while stream-foldr can terminate if the folding function decides to “discard” the accumulator thunk. It’s analogous to foldl' vs. foldr in Haskell: foldl' strictly reduces a finite structure to a strict result, while foldr “rebuilds” the structure and therefore can be as lazy as the structure is. (Also, foldl' can be defined in terms of foldr, but not vice versa.)

Oh! I'm wrong, my mistake, yes.

(BTW, not at all joking when I say that you would have saved me about 10 minutes just now if your response had included a phrase semantically equivalent to "actually, you're wrong". I think you were perhaps a bit too polite?) :slight_smile:

1 Like