Схема Составьте список всех парных перестановок элементов в двух списках одинаковой длины

Question

Я пытаюсь объединить два списка координат x и y в пары в схеме, и я близок, но не могу получить список возвращенных пар. Следующее может сопоставить все пары, используя вложенные циклы, но я не уверен, что лучший способ их вывести, сейчас я просто отображаю их на консоли.

(define X (list 1 2 3 4 5))
(define Y (list 6 7 8 9 10))
(define (map2d X Y)
    (do ((a  0 (+ a 1)))               ; Count a upwards from 0
        ((= a (length X) ) )           ; Stop when a = length of list
      (do ((b 0 (+ b 1)))              ; Count b upwards from 0
          ((= b (length Y) ) )         ; Stop when  b = length of second list
          (display (cons (list-ref X a) (list-ref Y b))) (newline)
        ))
)
(map2d X Y)

Я хочу получить эту функцию вывода

((1 . 6) (1 . 7) (1 . 8) ... (2 . 6) (2 . 7) ... (5 . 10))

Затем я буду использовать map для подачи этого списка в другую функцию, которая принимает пары.

Бонусные баллы, если вы можете помочь мне сделать это более рекурсивным (разве это не "чистый" функционал, верно?), Я впервые использую функциональное программирование, и рекурсию было нелегко понять. Спасибо!

Answer 1

Решения Оскара Лопеса являются правильными и элегантными и обращаются к "правильному" способу программирования на функциональном языке. Однако, поскольку вы начинаете изучать рекурсию, я предложу простое рекурсивное решение без функций высокого уровня:

(define (prepend-to-all value y)
  (if (null? y)
      '()
      (cons (cons value (car y)) (prepend-to-all value (cdr y)))))

(define (map2d x y)
  (if (null? x)
      '()
      (append (prepend-to-all (car x) y) (map2d (cdr x) y))))

Функция map2d повторяется в первом списке: если он пуст, то декартово произведение будет пустым; в противном случае будут собраны все пары, полученные путем добавления первого элемента x ко всем элементам yсо всеми парами, полученными путем применения себя к остальным x и все элементы y,

Функция prepend-to-all, произведет все пары, построенные из одного значения, value и все элементы списка y, Повторяется по второму параметру, списку. когда y пусто, результатом является пустой список пар, в противном случае он создает пару с value и первый элемент yи "умалчивает" его на результате предвари value ко всем остальным элементам y,

Когда вы освоите рекурсию, вы можете перейти к следующему шагу, изучив хвостовую рекурсию, в которой вызов функции не содержится в какой-либо другой форме "построения", но является первым рекурсивным вызовом. Преимущество такой формы в том, что компилятор может преобразовать ее в (гораздо) более эффективную итеративную программу. Вот пример этой техники, примененной к вашей проблеме:

(define (map2d x y)
  (define (prepend-to-all value y pairs)
    (if (null? y)
        pairs
        (prepend-to-all value (cdr y) (cons (cons value (car y)) pairs)))) 
  (define (cross-product x y all-pairs)
    (if (null? x)
        (reverse all-pairs)
        (cross-product (cdr x) y (prepend-to-all (car x) y all-pairs))))
  (cross-product x y '()))

Основная идея состоит в том, чтобы определить вспомогательную функцию с новым параметром, который "накапливает" результат во время его построения. Этот "аккумулятор", который инициализируется с помощью () при вызове вспомогательной функции, будет возвращен как результат в терминальном случае рекурсии. В этом случае ситуация более сложная, так как есть две функции, но вы можете изучить новую версию prepend-to-all чтобы увидеть, как это работает. Обратите внимание, что для возврата всех пар в естественном порядке, в конце cross-product Функция результат обратный. Если вам не нужен этот заказ, вы можете опустить reverse чтобы сделать функцию более эффективной.

Answer 2

С помощью do не очень идиоматичный. Вы можете попробовать вложение maps вместо этого, это больше в духе Схемы - использование встроенных процедур высшего порядка - путь!

; this is required to flatten the list
(define (flatmap proc seq)
  (fold-right append '() (map proc seq)))

(define (map2d X Y)
  (flatmap
   (lambda (i)
     (map (lambda (j)
            (cons i j))
          Y))
   X))

Обидно, что вы не используете Racket, это было бы лучше:

(define (map2d X Y)
  (for*/list ([i X] [j Y])
    (cons i j)))