Генерация потока всех возможных кортежей из заданных потоков с использованием Scheme

Я пытаюсь написать процедуру 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) ....

Меня вдохновил упражнение 3.70 в SICP, которое посвящено написанию процедуры 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. поток, полученный в результате cons объединения первого элемента первого потока с каждым элементом (рекурсивно созданного) потока, который состоит из кортежей из остальной части данного потоки и 2. поток, состоящий из кортежей stream-cdr первого потока и остальных заданных потоков.

Это не работает, потому что создание потока 2 не остановится в случае бесконечного потока (по той же причине pairs процедура из упражнение 3.68 не работает).

Это 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)))))))))

Есть ли способ рекурсивно построить эту проблему?

РЕДАКТИРОВАТЬ: То, что я имел в виду под «кортежем» в этом вопросе, на самом деле является списком схемы, который семантически представляет кортеж.

Для справки я оставляю свою реализацию потоковых примитивов (которая идентична той, что есть в 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)))))

stream recursion lazy-sequences scheme sicp
person Jay Lee    schedule 13.11.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Мне удалось решить эту проблему, используя структуру рекурсии, аналогичную структуре pairs процедура, показанная в 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 кортежей были упорядочены независимо от cars, то есть W (a, b, c) ›= W (x, y, z), только если W (b, c)› = W (у, г).

person Jay Lee    schedule 14.11.2020