Common Lisp: Zip arbitrary number of lists

Question

Suppose you have a list of lists, e.g. '(("abc" "def" "ghi") ("012" "345" "678") ("jkl" "mno" "pqr")) or '(("ab" "cd" "ef") ("01" "23" "45")).

What would be the canonical way to zip the lists inside the given list? I.e. how would func be defined such that

(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")

where concat := (lambda (args) ...) is the function that combines the heads of the respective lists.

Presumably, this type of operation is known as rotation or zipMany (according to the answers for related questions for different languages).

I have something like this (double-apply)

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

where lst is '(("ab" "cd" "ef") ("01" "23" "45")) for example. The combiner would be concatenate. Note that no separator is given in this example implementation.

But this seems awfully convoluted.

So, what would be a canonical implementation for this kind of operation?

score 6 · Accepted Answer · answered Jun 03 '18 at 23:14

For an arbitray number of lists, you'd need to get rid of apply #'mapcar, because otherwise the number of lists would be limited by call-arguments-limit.

One typical way would be to use reduce instead, combining two lists at a time:

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

If you don't like the explicit lambda form, you might like curry, e. g. from alexandria:

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

Other looping constructs are loop, do, dolist, and there are also a few looping libraries, e. g. iterate, for.

Yes, using `reduce` is a nice solution. Well, if I used the looping constructs I would have to manage state myself, wouldn't I? So, `reduce` it is (of the solutions I tried it also used the least amount of memory, ~2Kb) — Aroob, Jun 04 '18 at 18:05

Rainer Joswig · Answer 2 · 2018-06-04T12:41:16.780

Join

(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))

Goal

don't use &rest args or apply - which would limit our list lengths.

Recursive MAPCARS

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

Iterative MAPCARS

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

Usage

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

nice solution with recursive `mapcar` :) – Gwang-Jin Kim Jun 04 '18 at 16:11 — Gwang-Jin Kim, Jun 04 '18 at 16:11

coredump · Answer 3 · 2018-06-16T13:45:28.133

Your function works, but relies on APPLY. The number of lists you can pass to apply is limited by CALL-ARGUMENTS-LIMIT, which may be large enough in a given implementation. Your function, however, is supposed to accept an arbitrary number of lists, and so, if you want to code portably, you shouldn't use apply in your case.

Zip

The zip function combines all first elements, then all second elements, etc. from a list of lists. If your input list of lists is the following:

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

Then zip will build the following list:

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

If you look closely, you can see that you can split the work being done as mapping of the combine function over the transpose of your initial list of lists (viewed as a matrix):

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

And so, zip can be defined as:

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

Alternatively, you could use MAP-INTO, if you care about reusing the memory that is allocated when calling transpose:

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

Transpose

There are different ways to transpose a list of lists. Here I am going to use REDUCE, which is known as fold in some other functional languages. At each step of reduction, the intermediate reducing function will take a partial result and a list, and produce a new result. Our result is also a list of lists. Below, I show the current list at each step of reduction, and the resulting list of lists.

First step

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

Second step

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

Third step

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

Note that elements are pushed in front of each lists, which explains why each resulting list is reversed w.r.t. the expect result. The transpose function should thus reverse each list after performing reduction:

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

Like previously, it might be preferable to avoid allocating too much memory.

(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)))

Example

(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")

Edit: the other answers already provide example definitions for join-string. You could also use the join function from cl-strings.

@MartinBuchmann I thought it was not necessary to give another example of join, but I edited the question to point to a library that was not yet referenced. Thanks. — coredump, Jun 16 '18 at 13:46

Gwang-Jin Kim · Answer 4 · 2018-06-04T19:22:13.417

Originally, I tried using backquote and splice ,@ and defining a macro to get rid of the applys. But as @coredump pointed out, that bears then other problems.

Anyhow, you need the Pythonic function join() as a combiner, if you want to add separators between the joined elements. concatenate will make the things more complicated if the function should behave in the way you want it to.

Since I use @Sylwester's very elegant join() definition, my answer will be very similar to his. Maybe my answer is the closest to your original example.

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

Using this, we can define your func to:

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

Or without apply - how @Rainer Joswig points out - and all previous answerers, too - because it has restriction in number of arguments which it can take (~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))

Or slightly shorter:

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

Testing:

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

Note that :sep "" makes join equivalent to the function concatenate.

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

Thanks to @Sylwester, @coredump and @Rainer Joswig!

Please do not use macros for computation. Trying to get rid of apply with a macro means you will eventually either need to call eval or have literal inputs. — coredump, Jun 03 '18 at 23:44
Yes, I see now the problem that one has literal input for the lists ... — Gwang-Jin Kim, Jun 04 '18 at 00:41
@coredump: so now changed to a function and using `apply` once. Thanks for the hint! — Gwang-Jin Kim, Jun 04 '18 at 09:18

score 3 · Answer 5 · answered Jun 03 '18 at 23:29

How about:

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

Then you should make join:

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

Then either make a wrapper or a lambda for your specific use:

(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")

anquegi · Answer 6 · 2018-06-04T12:16:10.770

Why do not use the &rest in params and return that on the lambda function.

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"))

then you can use apply like this:

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

until here, is what a normal zip would do, now you want to join that sublist into one string, with some custom separator.

for that the best answer is use format, and also like this answer from stackoverflow here 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))

Then you only need to use mapcar again on this functions and the result list from zip

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

That's nifty, using `&rest` like that. – Aroob Jun 04 '18 at 18:12 — Aroob, Jun 04 '18 at 18:12

Common Lisp: Zip arbitrary number of lists

6 Answers6

Zip

Transpose

Example