Более общий код lisp для генерации комбинаций пар

Question

Учитывая эту печальную вещь ниже, которая генерирует все пары только двух диапазонов -

[53]> (setq thingie '())

NIL
[54]> (loop for i in (generate-range 0 3) do 
(loop for j in (generate-range 4 6) do 
(push (list i j) thingie)))

NIL
[55]> thingie

((3 6) (3 5) (3 4) (2 6) (2 5) (2 4) (1 6) (1 5) (1 4) (0 6) (0 5) (0 4))
[56]>  

Или, другими словами, это генерирует вид двумерного дискретного макета.

Как бы я пошел для создания своего рода кода, генерирующего пары, который взял бы произвольное число диапазонов?(Или создание n-мерного дискретного макета).

Очевидно, что одним из решений было бы иметь defmacro, который бы брал список списков и построил циклы n для выполнения, ноэто не кажется простым путем.

Answer 1

(defun map-cartesian (fn bags)
  (labels ((gn (x y)
             (if y (mapc (lambda (i) (gn (cons i x) (cdr y))) (car y))
                 (funcall fn x))))
    (gn nil (reverse bags))))

CL-USER> (map-cartesian #'print '((1 2) (a b c) (x y)))

(1 A X) 
(2 A X) 
(1 B X) 
(2 B X) 
(1 C X) 
(2 C X) 
(1 A Y) 
(2 A Y) 
(1 B Y) 
(2 B Y) 
(1 C Y) 
(2 C Y) 

Если вы предпочитаете синтаксис sugar,

(defmacro do-cartesian ((item bags) &body body)
  `(map-cartesian (lambda (,item) ,@body) ,bags))

CL-USER> (do-cartesian (x '((1 2) (a b c) (x y)))
           (print x))

Редактировать: (краткое объяснение)

Первый параметр gn, x, это частичный кортеж, созданный до сих пор;у - оставшиеся мешки элементов.Функция gn расширяет частичный кортеж путем итерации по каждому элементу i одного из оставшихся пакетов (car y) для формирования (cons ix).Когда оставшихся пакетов нет (ветвь else оператора if), кортеж завершается, поэтому мы вызываем предоставленную функцию fn для кортежа.

Answer 2

Вам не нужна явная рекурсия (или даже макрос), это также можно сделать с помощью функции высшего порядка:

(defun tuples-from-ranges (range &rest ranges)
  (reduce (lambda (acc range)
            (mapcan (lambda (sublist)
                      (mapcar (lambda (elt)
                                (append sublist (list elt)))
                              (apply #'generate-range range)))
                    acc))
          ranges
          :initial-value (mapcar #'list (apply #'generate-range range))))

Две вложенные внутренние функции высшего порядка (mapcanи mapcar) выполняют ту же функцию, что и два вложенных цикла в вашем примере.Внешняя функция высшего порядка reduce затем сначала объединит значения первых двух диапазонов в пары, а после этого при каждом вызове своей функции аргумента снова применяет некоторый процесс к промежуточным результатам предыдущего вызова и следующего диапазона.

Answer 3

Если вы думаете об этом как о структуре управления, макро-маршрут - это путь. Если вы думаете об этом как о способе генерации данных, рекурсивная функция - это путь.

Answer 4

Для меня очевидной будет рекурсивная функция.