使用 Scheme 从给定流生成所有可能元组的流

Question

我正在尝试编写一个过程 stream-weighted-tuples，它采用权重过程和任意数量的流来生成元组流。例如，

(stream-weighted-tuples
  (lambda (t) (+ (car t) (cadr t) (caddr t))
  integers
  integers
  integers)

应该生成 (1 1 1) (1 1 2) (1 2 1) (2 1 1) (1 1 3) (1 2 2) (1 3 1) (2 1 2) (2 2 1) (3 1 1) (1 1 4) (1 2 3) ....

的流

我受到 SICP 中 exercise 3.70 的启发，它是关于编写一个过程 weighted-pairs，它采用两个流和一个权重过程来根据权重按顺序生成对流。所以基本上，这是对 weighted-pairs 过程的概括，以获取两个以上的流。

我写了以下版本：

    (define (stream-weighted-tuples weight . streams)
      (cond ((null? streams)
             (error "No streams given -- STREM-WEIGHTED-TUPLES"))
            ((null? (cdr streams))
             (stream-map list (car streams)))
            (else
              (let ((s (car streams))
                    (rest (cdr streams)))
                (if (stream-null? s)
                    the-empty-stream  ; {} x S = {}
                    (stream-merge-weighted
                      weight
                      (stream-map (lambda (tuple)
                                    (cons (stream-car s) tuple))
                                  (apply stream-weighted-tuples
                                         (lambda (tuple)  ; partial weight
                                           (weight (cons (stream-car s)
                                                         tuple)))
                                         rest))
                      (apply stream-weighted-tuples
                             weight
                             (stream-cdr s)
                             rest)))))))

（这显然不起作用）。想法是合并 1. 由 consing 第一个流 的第一个元素产生的流 与由 [=44 组成的（递归构造的）流的每个元素=]来自给定流的其余部分的元组，以及 2. 由第一个流的stream-cdr的元组组成的流和给定流的其余部分。

这不起作用，因为在无限流的情况下生成流 2 不会停止（由于相同的原因，来自 exercise 3.68 的 pairs 过程不起作用）。

这是stream-merge-weighted我实现的：

    (define (stream-merge-weighted weight s1 s2)
      (cond ((stream-null? s1) s2)
            ((stream-null? s2) s1)
            (else
              (let* ((s1car (stream-car s1))
                     (s2car (stream-car s2))
                     (s1car-weight (weight s1car))
                     (s2car-weight (weight s2car)))
                (cond ((<= s1car-weight s2car-weight)
                       (cons-stream
                         s1car
                         (stream-merge-weighted weight
                                                (stream-cdr s1)
                                                s2)))
                      ((> s1car-weight s2car-weight)
                       (cons-stream
                         s2car
                         (stream-merge-weighted weight
                                                s1
                                                (stream-cdr s2)))))))))

有没有办法递归构造这个问题？

编辑：我在这个问题中所说的“元组”实际上是一个在语义上表示元组的 Scheme 列表。

作为参考，我留下了流原语的实现（与 SICP 中的原语相同）：

    (define-syntax cons-stream
      (syntax-rules ()
        ((_ a b)
         (cons a (delay b)))))

    (define (stream-car stream)
      (car stream))
    (define (stream-cdr stream)
      (force (cdr stream)))

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

    (define (stream-map proc s)
      (if (stream-null? s)
          the-empty-stream
          (cons-stream
            (proc (stream-car s))
            (stream-map proc (stream-cdr s)))))

Answer 1

我设法使用类似于 the pairs procedure shown in SICP 的递归结构来解决它。

下面的stream-weighted-tuples对cdr流（rest-tuples）的元组递归构造流，然后使用相同的递归策略“配对”（不像原始 pair 过程，另一个流已经是一个元组流）它与流的 car (combine-with-rest).

    (define (stream-weighted-tuples weight . streams)
      (if (null? streams)
          (cons-stream '() the-empty-stream)
          (let* ((stream (car streams))
                 (rest (cdr streams))
                 (rest-tuples
                   (apply stream-weighted-tuples
                          (lambda (tuple)  ; partial weight
                            (weight (cons (stream-car stream) tuple)))
                          rest)))
            (let combine-with-rest ((stream stream)
                                    (rest-tuples rest-tuples))
              (if (or (stream-null? stream)
                      (stream-null? rest-tuples))
                  the-empty-stream  ; {} x S = {}
                  (let ((s-car (stream-car stream))
                        (s-cdr (stream-cdr stream))
                        (r-car (stream-car rest-tuples))
                        (r-cdr (stream-cdr rest-tuples)))
                    (cons-stream (cons s-car r-car)
                                 (stream-merge-weighted
                                   weight
                                   (stream-map (lambda (t) (cons s-car t))
                                               r-cdr)
                                   (stream-merge-weighted
                                     weight
                                     (stream-map (lambda (x) (cons x r-car))
                                                 s-cdr)
                                     (combine-with-rest s-cdr r-cdr))))))))))

注意，weight 过程要求元组的 cdr 独立于 car 排序，即 W(a, b, c) >= W (x, y, z) 仅当 W(b, c) >= W(y, z).

使用 Scheme 从给定流生成所有可能元组的流

Generating a stream of all possible tuples from given streams using Scheme

recursion

scheme

stream

sicp

lazy-sequences