Nano Hash - криптовалюты, майнинг, программирование

SICP-упражнение 3.67 - создание всех пар целых чисел без ограничений

Из SICP:

Это бесконечный поток единиц:

 (define ones (cons-stream 1 ones))

Это бесконечный поток положительных целых чисел:

 ; add-streams takes two streams and produces a stream of their elementwise sum
 (define integers (cons-stream 1 (add-streams ones integers)))

interleave принимает элементы поочередно из двух потоков и возвращает результат

(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream 
       (stream-car s1)
       (interleave s2 (stream-cdr s1)))))

Следующая pairs процедура принимает два потока s и t и производит все пары (s_i, t_j), такие что i <= j.

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) 
                  (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

So

 (pairs integers integers)

производит все пары целых чисел i и j с i <= j.

Вот упражнение 3.67:

Упражнение 3.67. Измените процедуру pairs так, чтобы (pairs integers integers) создавал поток всех пар целых чисел (i, j) (без условия (i <= j)). Подсказка: вам нужно будет добавить дополнительный поток.

Мое решение:

(define (pairs2 s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) 
                  (list (stream-car s) x))
                (stream-cdr t))
    (pairs2 (stream-cdr s) t))))

Итак, я просто изменил (stream-cdr t) на t в последнем рекурсивном вызове. Похоже, это дает все пары целых чисел.

Чего я не понимаю, так это утверждения:

Подсказка: вам нужно будет добавить дополнительный поток.

Что это значит? Мое решение неверно? Что они имеют в виду, когда говорят о дополнительном потоке?

Используя мою модифицированную процедуру pairs2, это первые 20 результатов:

> (define p2 (pairs2 integers integers))
> (stream-ref p2 0)
(1 1)
> (stream-ref p2 1)
(1 2)
> (stream-ref p2 2)
(2 1)
> (stream-ref p2 3)
(1 3)
> (stream-ref p2 4)
(2 2)
> (stream-ref p2 5)
(1 4)
> (stream-ref p2 6)
(3 1)
> (stream-ref p2 7)
(1 5)
> (stream-ref p2 8)
(2 3)
> (stream-ref p2 9)
(1 6)
> (stream-ref p2 10)
(3 2)
> (stream-ref p2 11)
(1 7)
> (stream-ref p2 12)
(2 4)
> (stream-ref p2 13)
(1 8)
> (stream-ref p2 14)
(4 1)
> (stream-ref p2 15)
(1 9)
> (stream-ref p2 16)
(2 5)
> (stream-ref p2 17)
(1 10)
> (stream-ref p2 18)
(3 3)
> (stream-ref p2 19)
(1 11)
stream infinite lisp scheme sicp
19.03.2019

Ответы:


1

Похоже, что ваш ответ действительно правильный. Как бы то ни было, я смог решить эту проблему, используя один дополнительный поток, что и имели в виду авторы с подсказкой «Вам нужно будет добавить дополнительный поток»:

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave (stream-map (λ (x) (list (stream-car s) x))
                           (stream-cdr t))
               (interleave (stream-map (λ (x) (list x (stream-car t)))
                                       (stream-cdr s))
                           (pairs (stream-cdr s) (stream-cdr t))))))

Мои первые 20 результатов похожи, хотя в некоторых случаях в другом порядке или с другими элементами, которые, вероятно, появятся позже в вашем решении:

(1 1)
(1 2)
(2 1)
(1 3)
(2 2)
(1 4)
(3 1)
(1 5)
(2 3)
(1 6)
(4 1)
(1 7)
(3 2)
(1 8)
(5 1)
(1 9)
(2 4)
(1 10)
(6 1)
(1 11)
19.03.2019
  • есть, конечно, гораздо больше способов смешивать потоки, например чередовать верхнюю строку с левым столбцом first, а затем чередовать результат этого с чередованием остатка, то есть с ядром матрицы. затем идет полная диагонализация, проходящая по возрастающим диагоналям слева направо (или, в равной степени, по нисходящим диагоналям справа налево, то есть по тем же диагоналям, только в обратном порядке). эту матрицу мы получаем, помещая элементы s в левый столбец сверху вниз и элементы t в верхнюю строку слева направо, а затем заполняя квадраты. 19.03.2019
  • релевантные условия поиска: совмещение, чередование, диагонализация (например, здесь), монада Omega (в Haskell; есть также пакет Universe, который делает то же самое). Я думаю, что порядок, который вы используете в этом ответе, такой же, как и у Нормана Рэмси, в ответе, который я упоминаю в связанном ответе. Возможно, я добавлю здесь ответ с диагонализацией в схеме. 19.03.2019
  • @ Scar López, прежде чем прочитать ваш ответ, я также придумал решение, связанное с другим потоком. Мы почти такие же, за исключением второй карты потока. Моя вторая потоковая карта: (stream-map (λ (x) (list (stream-car s) x)) (stream-cdr t)). Мы просто поменяли местами s и t. Будут ли отличия? 19.03.2019
  • @morbidCode отличная работа! Я предполагаю, что порядок следования может быть другим, но это не имеет значения 19.03.2019
  • Я тоже попробовал это сделать, но застрял. Я не мог придумать, как это сделать с stream-interleave. Спасибо, что поделился. 20.03.2019
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..