Common Lisp: Zip произвольное количество списков

Question

Предположим, у вас есть список списков, например, '(("abc" "def" "ghi") ("012" "345" "678") ("jkl" "mno" "pqr")) или '(("ab" "cd" "ef") ("01" "23" "45")).

Каким был бы канонический способ сжать списки внутри данного списка?Т.е. как можно определить func так, чтобы

(func '(("ab" "cd" "ef") ("01" "23" "45")) :sep "|" :combiner #'concat) 
  ;; => ("ab|01" "cd|23" "ef|45")

(func '(("abc" "def" "ghi") ("012" "345" "678") ("jkl" "mno" "pqr")) ...)
  ;; => ("abc|012|jkl" "def|345|mno" "ghi|678|pqr")

, где concat := (lambda (args) ...) - функция, объединяющая заголовки соответствующих списков.

Предположительно, этот тип операции известен как вращение или zipMany (согласно ответам на связанные вопросы для разных языков).

У меня есть что-то вроде этого (double- apply)

(apply #'mapcar #'(lambda (&rest args) (apply #'concatenate 'string args)) lst)

, где lst - это, например, '(("ab" "cd" "ef") ("01" "23" "45")).combiner будет concatenate.Обратите внимание, что в этом примере реализации разделитель не указан.

Но это выглядит ужасно запутанным.

Итак, Какая каноническая реализация для операции такого типа ?

Answer 1

Регистрация

(defun %d (stream &rest args)
  "internal function, writing the dynamic value of the variable
DELIM to the output STREAM. To be called from inside JOIN."
  (declare (ignore args)
           (special delim))
  (princ delim stream))

(defun join (list delim)
  "creates a string, with the elements of list printed and each
element separated by DELIM"
  (declare (special delim))
  (format nil "~{~a~^~/%d/~:*~}" list))

Цель

не использовать &rest args или apply - что ограничит наш списокдлины.

Рекурсивные MAPCARS

(defun mapcars (f l)
  (if (null (car l))
      '()
    (cons (funcall f (mapcar #'car l))
          (mapcars f (mapcar #'cdr l)))))

Итерационные MAPCARS

(defun mapcars (f l)
  (loop for l1 = l then (mapcar #'cdr l1)
        while (car l1)
        collect (funcall f (mapcar #'car l1))))

Использование

CL-USER 10 > (mapcars (lambda (l) (join l "|")) l)
("abc|012|jkl" "def|345|mno" "ghi|678|pqr")

Answer 2

Почему бы не использовать & rest в параметрах и возвращать его в лямбда-функции.

CL-USER> (mapcar (lambda (&rest l) l) '(1 2 3) '(a b c) '("cat" "duck" "fish"))
((1 A "cat") (2 B "duck") (3 C "fish")) 

, тогда вы можете использовать apply следующим образом:

(apply #'mapcar (lambda (&rest l) l) '(("ab" "cd" "ef") ("01" "23" "45"))) 
; => (("ab" "01") ("cd" "23") ("ef" "45"))

до тех пор, пока вот чтонормальный zip-файл подойдет, теперь вы хотите объединить этот подсписок в одну строку с некоторым пользовательским разделителем.

, для этого лучшим ответом является использование формата, а также такой ответ из stackoverflowздесь https://stackoverflow.com/a/41091118/1900722

(defun %d (stream &rest args)
  "internal function, writing the dynamic value of the variable
DELIM to the output STREAM. To be called from inside JOIN."
  (declare (ignore args)
           (special delim))
  (princ delim stream))

(defun join (list delim)
  "creates a string, with the elements of list printed and each
element separated by DELIM"
  (declare (special delim))
  (format nil "~{~a~^~/%d/~:*~}" list))

Тогда вам нужно только снова использовать mapcar для этой функции и список результатов из zip

(mapcar (lambda (lst) (join lst "|")) '(("ab" "01") ("cd" "23") ("ef" "45")))
 ; => ("ab|01" "cd|23" "ef|45")

Answer 3

Ваша функция работает, но использует APPLY.Количество списков, которые вы можете передать apply, ограничено CALL-ARGUMENTS-LIMIT, что может быть достаточно большим в данной реализации.Однако ваша функция должна принимать произвольное количество списков, поэтому, если вы хотите кодировать переносимо, вам не следует использовать apply в вашем случае.

Zip

Функция zip объединяет все первые элементы, затем все вторые элементы и т. Д. Из списка списков.Если ваш входной список списков следующий:

'((a b c d)
  (0 1 2 3)
  (x y z t))

Тогда zip создаст следующий список:

(list (combine (list a 0 x))
      (combine (list b 1 y))
      (combine (list c 2 z))
      (combine (list d 3 t)))

Если вы присмотритесь, вы увидите, что можете разделить работувыполняется как отображение функции combine поверх транспонирования вашего первоначального списка списков (в виде матрицы):

 ((a b c d)            ((a 0 x) 
  (0 1 2 3)    ===>     (b 1 y) 
  (x y z t))            (c 2 z) 
                        (d 3 t))

И так,zip можно определить как:

(defun zip (combine lists)
  (mapcar #'combine (transpose lists)))

В качестве альтернативы, вы можете использовать MAP-INTO, если вам нужно повторно использовать память, выделенную при вызове transpose:

(defun zip (combiner lists &aux (transposed (transpose lists)))
  (map-into transposed combiner transposed))

Транспонирование

Существуют различные способы транспонировать список списков.Здесь я собираюсь использовать REDUCE, который известен как fold в некоторых других функциональных языках.На каждом шаге редукции промежуточная функция редукции будет принимать частичный результат и список, и создавать новый результат.Наш результат также список списков.Ниже я показываю текущий список на каждом шаге сокращения и результирующий список списков.

Первый шаг

(a b c d)  =>  ((a)
                (b)
                (c)
                (d))

Второй шаг

(0 1 2 3)  =>  ((0 a)
                (1 b)
                (2 c)
                (3 d))

Третий шаг

(x y z t)  =>  ((x 0 a)
                (y 1 b)
                (z 2 c)
                (t 3 d))

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

(defun transpose (lists)
  (mapcar #'reverse
          (reduce (lambda (result list)
                    (if result
                        (mapcar #'cons list result)
                        (mapcar #'list list)))
                  lists
                  :initial-value nil)))

Как и раньше, может быть предпочтительнее избежать выделения слишком большого объема памяти.

(defun transpose (lists)
  (let ((reduced (reduce (lambda (result list)
                           (if result
                               (mapcar #'cons list result)
                               (mapcar #'list list)))
                         lists
                         :initial-value nil)))
    (map-into reduced #'nreverse reduced)))

Пример

(transpose '(("ab" "cd" "ef") ("01" "23" "45")))
=> (("ab" "01") ("cd" "23") ("ef" "45"))

(import 'alexandria:curry)

(zip (curry #'join-string "|")
     '(("ab" "cd" "ef") ("01" "23" "45")))
=> ("ab|01" "cd|23" "ef|45")

---

Редактировать: в других ответах уже приведены примеры определений для join-string.Вы также можете использовать функцию join из cl-strings .

Answer 4

Как насчет:

(defun unzip (lists &key (combiner #'list))
  (apply #'mapcar combiner lists))

Тогда вы должны сделать join:

(defun join (l &key (sep ", "))
  (format nil (format nil "~a~a~a" "~{~a~^" sep "~}") l))

Затем либо создайте обертку или лямбду для вашего конкретного использования:

(unzip '(("abc" "def" "ghi") ("012" "345" "678") ("jkl" "mno" "pqr"))
       :combiner (lambda (&rest l) (join l :sep "|")))
; ==> ("abc|012|jkl" "def|345|mno" "ghi|678|pqr")

Answer 5

Для произвольного числа списков вам нужно избавиться от apply #'mapcar, потому что в противном случае количество списков будет ограничено call-arguments-limit.

Одним из типичных способов будет использование *Вместо 1005 *, объединяя два списка одновременно:

(defun zip (list-of-lists &key (combiner #'concat))
  (reduce (lambda (list-a list-b)
            (mapcar combiner list-a list-b))
          list-of-lists))

Если вам не нравится явная форма lambda, вам может понравиться curry, например, из alexandria:

(defun zip (list-of-lists &key (combiner #'concat))
  (reduce (curry #'mapcar combiner)
          list-of-lists))

Другими конструкциями циклов являются loop, do, dolist, и есть также несколько библиотек циклов, например, iterate, for.

Answer 6

Изначально я пытался использовать backquote и сращивать ,@ и определять макрос, чтобы избавиться от apply s.Но, как указал @coredump, это порождает и другие проблемы.

В любом случае вам нужна функция Pythonic join() в качестве объединителя, если вы хотите добавить разделители между объединенными элементами.concatenate усложнит ситуацию, если функция будет вести себя так, как вы хотите.

Поскольку я использую очень элегантное определение join() @ Sylwester, мой ответ будет очень похож на его.Возможно, мой ответ наиболее близок к вашему первоначальному примеру.

(defun join (l &key (sep ", "))
  (format nil (format nil "~a~a~a" "~{~a~^" sep "~}") l))

Используя это, мы можем определить вашу функцию следующим образом:

(defun func (lists &key (sep "|") (combiner #'join))
  (apply #'mapcar
         #'(lambda (&rest args) (funcall combiner args :sep sep))
         lists))

Или без apply - как @Rainer Joswig указываетout - и все предыдущие ответчики тоже - потому что он имеет ограничение в количестве аргументов, которые он может принять (~ 50):

(defun func (lists &key (sep "|") (combiner #'join))
  (reduce #'(lambda (l1 l2)
              (mapcar #'(lambda (e1 e2) 
                          (funcall combiner (list e1 e2) :sep sep)) l1 l2))
          lists))

или немного короче:

(defun func (lists &key (sep "|") (combiner #'join))
  (reduce #'(lambda (l1 l2)
              (mapcar #'(lambda (&rest l) (funcall combiner l :sep sep)) l1 l2))
          lists))

Тестирование:

(func '(("abc" "def" "ghi") ("012" "345" "678") ("jkl" "mno" "pqr"))) 
;; ("abc|012|jkl" "def|345|mno" "ghi|678|pqr")

Обратите внимание, что :sep "" делает join эквивалентом функции concatenate.

(func '(("abc" "def" "ghi") ("012" "345" "678") ("jkl" "mno" "pqr")) :sep "")
;; ("abc012jkl" "def345mno" "ghi678pqr")

Благодаря @Sylwester, @coredump и @Rainer Joswig!