CODEWITHSUNDEEP
listlispcommon-lisp
Megan..
Megan..

Reputation: 25

Combining list of list

Hello i have to programm this fucntion in lisp:

(defun combine-list-of-lsts (lst)...)

So when executing the function i should get 

(combine-list-of-lsts '((a b c) (+-) (1 2 3 4)))

((A + 1) (A + 2) (A + 3) (A + 4) (A-1) (A-2) (A-3) (A-4) (B + 1) (B + 2) (B + 3) (B + 4) (B-1) (B-2) (B-3) (B-4)(C + 1) (C + 2) (C + 3) (C + 4) (C-1) (C-2) (C-3) (C-4))

What i have now is:

(defun combine-list-of-lsts (lst)
(if (null (cdr lst))
    (car lst)
(if (null (cddr lst))
        (combine-lst-lst (car lst) (cadr lst))
(combine-lst-lst (car lst) (combine-list-of-lsts (cdr lst))))))

Using this auxiliar functions:

(defun combine-lst-lst (lst1 lst2)
        (mapcan #'(lambda (x) (combine-elt-lst x lst2)) lst1))

(defun combine-elt-lst (elt lst)
            (mapcar #'(lambda (x) (list elt x)) lst))

But what i get with this:

((A (+ 1)) (A (+ 2)) (A (+ 3)) (A (+ 4)) (A(-1)) (A(-2)) (A(-3)) (A(-4))...)

I dont know how to make this but without the parenthesis

Upvotes: 0

Views: 961

Answers (3)

Pankaj Sejwal
Pankaj Sejwal

Reputation: 1595

There is one more way you can try,

(defun mingle (x y)
 (let ((temp nil))
  (loop for item in x do
   (loop for it in y do
    (cond ((listp it) (setf temp (cons (append (cons item 'nil) it) temp)))
     (t (setf temp (cons (append (cons item 'nil) (cons it 'nil)) temp))))))
  temp))

Usage:(mingle '(c d f) (mingle '(1 2 3) '(+ -))) =>

((F 1 +) (F 1 -) (F 2 +) (F 2 -) (F 3 +) (F 3 -) (D 1 +) (D 1 -) (D 2 +) (D 2 -) (D 3 +) (D 3 -) (C 1 +) (C 1 -) (C 2 +) (C 2 -) (C 3 +) (C 3 -))

Upvotes: 0

Daniel Kochmański
Daniel Kochmański

Reputation: 339

Usually, when you want to reduce mutliple arguments into single result, you need function #'reduce. Your combination of lists has name cartesian n-ary product.

Following function:

(defun cartesian (lst1 lst2)
  (let (acc)
    (dolist (v1 lst1 acc)
      (dolist (v2 lst2)
        (push (cons v1 v2) acc)))))

creates cartesian product of two supplied lists as list of conses, where #'car is an element of lst1, and #'cdr is an element of lst2. 

(cartesian '(1 2 3) '(- +))

==> ((3 . -) (3 . +) (2 . -) (2 . +) (1 . -) (1 . +))

Note, however, that calling #'cartesian on such product will return malformed result - cons of cons and element:

(cartesian (cartesian '(1 2) '(+ -)) '(a))

==> (((1 . +) . A) ((1 . -) . A) ((2 . +) . A) ((2 . -) . A))

This happens, because members of the first set are conses, not atoms. On the other hand, lists are composed of conses, and if we reverse order of creating products, we could get closer to flat list, what is our goal:

(cartesian '(1 2)
           (cartesian '(+ -) '(a)))

==> ((2 + . A) (2 - . A) (1 + . A) (1 - . A))

To create proper list, we only need to cons each product with nil - in other words to create another product.

(cartesian '(1 2)
           (cartesian '(+ -)  
                      (cartesian '(a) '(nil))))

==> ((2 + A) (2 - A) (1 + A) (1 - A))

Wrapping everything up: you need to create cartesian product of successive lists in reversed order, having last being '(nil), what can be achieved with reduce expression. Final code will look something like this:

(defun cartesian (lst1 lst2)
  (let (acc)
    (dolist (v1 lst1 acc)
      (dolist (v2 lst2)
        (push (cons v1 v2) acc)))))

(defun combine-lsts (lsts)
  (reduce
   #'cartesian
   lsts
   :from-end t
   :initial-value '(nil)))

Upvotes: 1

Rainer Joswig
Rainer Joswig

Reputation: 139261

  1. The first thing is to look at this case:

    (combine-list-of-lsts '((a b c)))

    What should that be? Maybe not what your function returns...

  2. Then I would look at the function combine-list-of-lsts. Do you need two IF statements?

  3. Then look at combine-elt-lst. Do you really want to use LIST? It creates a new list. Wouldn't it make more sense to just add the element to the front?

Upvotes: 2

Related Questions