Dealing with multiple values

Show & Tell
1

Hello,

some months ago, when I started working with streams, I developed a procedure that takes some single valued streams and return a multi valued stream. Then I thought if the opposite was possible: create a procedure that takes a multi valued stream and return a list of single valued streams. Probably such a procedure isn't very useful, but the solution is interesting.

I developed some macros to deal with multiple values:

(define-syntax values->list ;I didn't use this, but is a good starting point
  (syntax-rules ()
    [(_ (values lst ...))
     (call-with-values
      (lambda () (values lst ...))
      (lambda v v))]))

(values->list (values 1 2 3))
=> '(1 2 3)

(define-syntax num-of-values
  (syntax-rules ()
    [(_ (values lst ...))
     (call-with-values
      (lambda () (values lst ...))
      (lambda v (length v)))]))

(num-of-values (values 1 2 3))
=> 3

(define-syntax values-ref
  (syntax-rules ()
    [(_ (values lst ...) n)
     (call-with-values
      (lambda () (values lst ...))
      (lambda v (list-ref v n)))]))

(values-ref (values 1 2 3) 1)
=> 2

With these procedures the solution is simple:

(define (stream-select the-stream n)
  (if (stream-empty? the-stream)
      empty-stream
      (stream-cons (values-ref (stream-first the-stream) n)
                   (stream-select (stream-rest the-stream) n))))

(define (mv-stream->list-of-streams the-stream)
  (define num-of-vals (num-of-values (stream-first the-stream)))
  (let next-streams ([n 0])
    (if (= n num-of-vals)
        '()
        (cons (stream-select the-stream n)
              (next-streams (+ n 1))))))


(define mv-stream (stream (values 1 10 100)
                          (values 2 20 200)
                          (values 3 30 300)
                          (values 4 40 400)))

(define los (mv-stream->list-of-streams mv-stream))

(stream->list (first los))
(stream->list (second los))
(stream->list (third los))

'(1 2 3 4)
'(10 20 30 40)
'(100 200 300 400)

Matteo

1 Like
2

Here are some possible improvements:

First, macros operate on compile-time syntax objects, not run-time values. Consider:

(define-syntax num-of-values
  (syntax-rules ()
    [(_ (values lst ...))
     (call-with-values
      (lambda () (values lst ...))
      (lambda v (length v)))]))

With the above macro, when we do (num-of-values (stream-first the-stream)), we would have values = stream-first and lst ... = the-stream. I don’t think that’s what you intend.

It would suffice to write:

(define-syntax num-of-values
  (syntax-rules ()
    [(_ vals)
     (call-with-values
      (lambda () vals)
      (lambda v (length v)))]))

With the revised macro, when we do (num-of-values (stream-first the-stream)), we would have vals = (stream-first the-stream).

1 Like
3

Thank you Sorawee, my version didn't convince me from the beginning, I was surprised it worked. Now it’s clear.

Matteo

4

Ughh, Discourse cuts content in my email again :confused: Here's the missing part:

Second, doing list-ref in a loop takes quadratic time. Here’s a test to demonstrate the problem:

(define my-stream
  (stream (apply values (range 0 20000))
          (apply values (range 20000 40000))))

(define los (mv-stream->list-of-streams my-stream))
(time (void (map stream->list los))) 
;=> cpu time: 3134 real time: 3396 gc time: 272

Here’s a revision that fixes the quadratic time issue:

;; the-stream must be a non-empty stream
(define (mv-stream->list-of-streams the-stream)
  (define st
    (for/stream ([e (in-values-sequence (in-stream the-stream))])
      e))
  (define num-of-vals (length (stream-first st)))
  (let loop ([n 0] [st st])
    (cond
      [(= n num-of-vals) '()]
      [else
       (define fst
         (for/stream ([xs (in-stream st)])
            (first xs)))
       (define rst
         (for/stream ([xs (in-stream st)])
            (rest xs)))
       (cons fst (loop (add1 n) rst))])))

(define my-stream
  (stream (apply values (range 0 20000))
          (apply values (range 20000 40000))))

(define los (mv-stream->list-of-streams my-stream))
(time (void (map stream->list los))) 
;=> cpu time: 30 real time: 31 gc time: 6
2 Likes