Формирование списка 2-списков в схеме

Question

(define cart-product
  (lambda (sos1 sos2)
    (if (null? sos1) '()
      (cons
       (cart-prod-sexpr (car sos1) sos2)
       (cart-product (cdr sos1) sos2)))))

(define cart-prod-sexpr
  (lambda (s sos)
    (if (null? sos) '()
        (cons
         (list s (car sos))
         (cart-prod-sexpr s (cdr sos))))))

Вызов (cart-product '(q w) '(x y)) производит (((q x) (q y)) ((w x) (w y))).

Как я могу произвести ((q x) (q y) (w x) (w y)) вместо?

Answer 1

Функции высшего порядка для выигрыша. Перечень списков в Haskell переведен на схему для лучшего решения:

; cart xs ys = [ [x,y] | x <- xs, y <- ys ]
(define (cart xs ys)
  (let ((f (lambda (x) (map (lambda (y) (list x y)) ys))))
    (concatenate (map f xs))))

(cart '(a b c) '(x y)) => ((a x) (a y) (b x) (b y) (c x) (c y))

Это выполняется в m * n (m = | xs |, n = | ys |). конкатенация от SRFI-1.

Answer 2

С макушки головы:

(define cart-product
  (lambda (sos1 sos2)
    (if (null? sos1) 
        '()
        (append
         (cart-prod-sexpr (car sos1) sos2)
         (cart-product (cdr sos1) sos2)))))

Answer 3

непроверенная. Обратите внимание, что процедура append-list, которую я определил, на самом деле возвращает список, заканчивающийся sos2. Это уместно (и правильно делать) здесь, но не в целом.

(define cart-product
  (lambda (sos1 sos2)
    (if (null? sos1) '()
      (append-list
       (cart-prod-sexpr (car sos1) sos2)
       (cart-product (cdr sos1) sos2)))))

(define cart-prod-sexpr
  (lambda (s sos)
    (if (null? sos) '()
        (cons
         (list s (car sos))
         (cart-prod-sexpr s (cdr sos))))))

(define append-list
  (lambda (sos1 sos2)
    (if (null? sos1) sos2
      (cons
        (car sos1)
        (append-list (cdr sos1) sos2)))))

Обратите внимание, что если списки имеют размер n, то потребуется время O (n ³ ) для создания списка размера O (n ² ). Использование обычного append взяло бы O (n ⁴ ). Я просто реализовал обычный append, не осознавая этого. Если вы хотите взять O (n ² ) ты должен быть умнее. Как в этом непроверенном коде.

(define cart-product
  (lambda (sos1 sos2)
    (let cart-product-finish
      (lambda (list1-current list2-current answer-current)
        (if (null? list2-current)
          (if (null? list1-current)
             answer-current
             (cart-product-finish (car list1-current) sos2 answer-current))
          (cart-product-finish list1-current (car sos2)
            (cons (cons (cdr list1-current) (cdr list2-current)) answer-current))))
    (cart-product-finish list1 '() '())))

В случае, если у меня есть ошибка, идея состоит в том, чтобы рекурсивно перебрать все комбинации элементов в первой и второй, при этом каждая из них заменяет answer-current на cons еще одной комбинацией, а затем все остальное уже нашли. Благодаря оптимизации хвостового вызова это должно быть эффективным.

Answer 4

Вот только другое решение для одной и той же проблемы. Я думаю, что это легко понять и, возможно, будет полезно для кого-то.

(define (cart-product l1 l2)
  (define (cart-product-helper l1 l2 org_l2)
    (cond
      ((and (null? l1)) `())
      ((null? l2) (cart-product-helper (cdr l1) org_l2 org_l2))
      (else (cons (cons (car l1) (car l2)) (cart-product-helper l1 (cdr l2) org_l2)))
    )
  )
  (cart-product-helper l1 l2 l2)
)

Answer 5

(reduce #'append 
           (mapcar #'(lambda(x)
                         (mapcar #'(lambda(y) 
                                       (list x y))
                          '(a b c))) 
           '(1 2 3)))

=> ((1 A) (1 B) (1 C) (2 A) (2 B) (2 C) (3 A) (3 B) (3 C))

[Примечание: решение для Common Lisp (CLisp), а не для Scheme, но я полагаю, что оно должно быть очень похоже на Scheme]

TheВнешний (уменьшить # 'добавление) предназначен для замены (объединить (отобразить), как указано в решении, knivil

Однако я не уверен, как мое решение складывается в параметрах производительности по сравнению с другими решениями. Кто-то может прокомментироватьна что?