(Scheme) Рекурсивная функция для вычисления всех возможных комбинаций некоторых списков?

Ответ 1

Вот мое решение. Требуется наличие SRFI 1 и 26.

(define (cartesian-product first . rest)
  (define (iter l result)
    (define (prepend-all x)
      (map (cut cons <> x) l))
    (concatenate (map prepend-all result)))
  (map reverse (fold iter (map list first) rest)))

Ответ 2

Вот мой прием; Сначала я определяю хелпер concat/map, который принимает список и функцию. Как обычный map, он применяет эту функцию к каждому элементу в списке. В отличие от map, он использует append для объединения результатов, а не cons. Это полезно, потому что мы хотим вернуть один уровень списков в качестве ответа:

(define concat/map
  (lambda (ls f)
    (cond
      [(null? ls) '()]
      [else (append (f (car ls)) (concat/map (cdr ls) f))])))

Тогда запись combine для двух списков проста. Вы берете каждый элемент первого списка, затем составляете каждый список, объединяющий его, и элемент x из второго списка. Поскольку это возвращает список ответов для каждого элемента в первом списке, используйте concat/map, чтобы собрать его, как мы хотим:

(define combine
  (lambda (xs ys)
    (concat/map xs (lambda (x)
                     (map (lambda (y) (list x y)) ys)))))

Версия combine, которая работает в одном или нескольких списках, позволяет называть ее combine*, немного сложнее. Вместо того, чтобы все списки, объединяющие x с элементами из второго списка, просто рекурсивно запрашиваем произведение всех оставшихся ys, а затем cons x на каждый из этих результатов. Рекурсия останавливается при объединении только двух списков и использует исходный combine в этом случае.

(define combine*
  (lambda (xs . ys*)
    (cond
      [(null? ys*) (map list xs)]
      [(null? (cdr ys*)) (combine xs (car ys*))]
      [else (concat/map xs (lambda (x)
                             (map (lambda (y) (cons x y))
                                  (apply combine* ys*))))])))

В качестве бонуса этот шаблон использования concat/map для выполнения некоторой работы и объединения полученных ответов на самом деле представляет собой list monad. Здесь это упрощено, но структура на месте.