Cartesian product of 2 lists which is NOT dependent

[westbaker]

Hi there everyone.

I am using a function which calculates the cartesian product of 2 lists.

(defun cartesian-product (list1 list2)
"Return a list of the Cartesian product of two lists."
(mapcan (lambda (x) (mapcar (lambda (y) (list x y)) list2)) list1))

This works great if all i wanted was a "printed representation". However i use the result in future functions which alter the list. When i alter parts of the list, other parts automatically change , which leads me to believe when using the above function a list is created with dependencies.

I was wondering if anyone knew how to change this code so that, there are no dependencies within the list. (i.e the "printed representation" is exactly what it is, no hidden dependencies).
(i believe it might be because of the destructive nature of mapcan, (using nconc))

Any help would be great,
Cheers

[Warren Wilkinson]

Are list1 and list2 just lists of atoms? If so, then the result is fresh, there should be no shared structure.

When you alter a part of the results, only that part of the result should change. Some destructive alterations can be a bit tricky to use for example:

Code: Select all

(setf *a* '((a b c)  (3 2 1)   (four five six)))
(sort (second *a*) #'<)  ;; The proper way would be to use: (setf (second *a*) (sort (second *a*) #'<))
(princ *a*)                   ;; You _won't_ get  ((a b c) (1 2 3) (four five six))

Can you tell us (or show us) the destructive operations you are using?

[westbaker]

Ok, so here is a typical command id be using. (sorry for the ridiculous length, its just the only example i know the error happens).

Im using GNU CLISP 2.49

>(setf u (mapcan (lambda (x) (mapcar (lambda (y) (list x y)) '((1 (X 1)) (1 (Y 1))) )) '((1 (X 1)) (1 (Y 1)))))

answer: (((1 (X 1)) (1 (X 1))) ((1 (X 1)) (1 (Y 1))) ((1 (Y 1)) (1 (X 1))) ((1 (Y 1)) (1 (Y 1))))


>(setf (car (cdr (car (cdr (car (cdr (car (cdr (cdr (cdr u)))))))))) 4) ;;(here im just trying to change the very last (Y 1) to (Y 4)

>u
answer: (((1 (X 1)) (1 (X 1))) ((1 (X 1)) (1 (Y 4))) ((1 (Y )) (1 (X 1))) ((1 (Y 1)) (1 (Y 4))))

;;However as we can see, if not only changes the last (Y 1) to 4, but also one in the middle somewhere.
I have no idea why it does this.

Cheers

[vanekl]

As Warren said, this would only work if the lists were composed of atoms. You are using lists of lists, which works differently -- the lists aren't copied.

Maybe you can better see what's going on if you run this:

Code: Select all

(let ((ss '((1 (XX 1)) (1 (YY 1))))
      (tt '((1 (ZX 1)) (1 (ZY 1))))
      u)
  (flet ((pr ()
	   (format t "~%u: ~s~%ss: ~s~%tt: ~s~%" u ss tt)))
	   
    (setf u (mapcan (lambda (x)
		      (mapcar (lambda (y) (list x y))
			      ss))
		    tt))
    (pr)
    (setf (car (cdr (car (cdr (car (cdr (car (cdr (cdr (cdr u)))))))))) 4)
    (setf (caaar u) 7)
    (pr)))

Output:

Code: Select all

u: (((1 (ZX 1)) (1 (XX 1))) ((1 (ZX 1)) (1 (YY 1))) ((1 (ZY 1)) (1 (XX 1))) ((1 (ZY 1)) (1 (YY 1))))
ss: ((1 (XX 1)) (1 (YY 1)))
tt: ((1 (ZX 1)) (1 (ZY 1)))

u: (((7 (ZX 1)) (1 (XX 1))) ((7 (ZX 1)) (1 (YY 4))) ((1 (ZY 1)) (1 (XX 1))) ((1 (ZY 1)) (1 (YY 4))))
ss: ((1 (XX 1)) (1 (YY 4)))
tt: ((7 (ZX 1)) (1 (ZY 1)))

[westbaker]

Oh ok, i see why thats messing up now.
Is there another way i can still create a cartesian product of 2 lists, like this , but have no dependencies? So that when i change certain items it only changes that particular item.

Thanks again

[vanekl]

I think copy-tree is what you want.

Code: Select all

(let ((ss '((1 (XX 1)) (1 (YY 1))))
      (tt '((1 (ZX 1)) (1 (ZY 1))))
      u)
  (flet ((pr ()
	   (format t "~%u: ~s~%ss: ~s~%tt: ~s~%" u ss tt)))
	   
    (setf u (mapcan (lambda (x)
		      (mapcar (lambda (y) (list
					   (copy-tree x)(copy-tree y)))
			      ss))
		    tt))
    (pr)
    (setf (car (cdr (car (cdr (car (cdr (car (cdr (cdr (cdr u)))))))))) 4)
    (setf (caaar u) 7)
    (pr)))

Output:

Code: Select all

u: (((1 (ZX 1)) (1 (XX 1))) ((1 (ZX 1)) (1 (YY 1))) ((1 (ZY 1)) (1 (XX 1))) ((1 (ZY 1)) (1 (YY 1))))
ss: ((1 (XX 1)) (1 (YY 1)))
tt: ((1 (ZX 1)) (1 (ZY 1)))

u: (((7 (ZX 1)) (1 (XX 1))) ((1 (ZX 1)) (1 (YY 1))) ((1 (ZY 1)) (1 (XX 1))) ((1 (ZY 1)) (1 (YY 4))))
ss: ((1 (XX 1)) (1 (YY 1)))
tt: ((1 (ZX 1)) (1 (ZY 1)))

[trillioneyes]

It is also pretty easy to define a non-destructive version of mapcan that uses append instead of nconc (though I suppose it isn't really worth it unless you're using it repeatedly). If I remember correctly, Paul Graham defines it in On Lisp as:

Code: Select all

(defun mappend (&rest lists)
  (apply #'append lists))

Edit: How embarrassing. Of course I meant

Code: Select all

(defun mappend (fn &rest lists)
  (apply #'append (apply #'mapcar fn lists)))

[Warren Wilkinson]

@trillioneyes -- The problem isn't in how the list is built, but due to the reuse of (y 1) in many parts of it.

Take a look at this:

Code: Select all

(in-package :cl-user)

(defun product (fn a b)
  (mapcan #'(lambda (x) (mapcar #'(lambda (y) (funcall fn x y)) b)) a))

(defvar *first* '((1 (X 1)) (1 (Y 1))))
(defvar *second* '((1 (X 1)) (1 (Y 1))))

(let ((result (product #'list *first* *second*)))
  (format t "~%Result: ~a" result)
  (setf (second (second (second (car (last result))))) 'new))

;; prints
;;Result: (((1 (X 1)) (1 (X 1))) ((1 (X 1)) (1 (Y NEW)))
;;              ((1 (Y 1)) (1 (X 1))) ((1 (Y 1)) (1 (Y NEW))))
;;
;; afterwards
;;
;; *first* remains the same
;; *second* is now: ((1 (X 1)) (1 (Y NEW)))

The easy solution is to use copy tree on the result of the cross product.

Code: Select all

(let ((result (copy-tree (product #'list *first* *second*))))
  (setf (second (second (second (car (last result))))) 'new)
  (format t "~%Result: ~a" result))

;; prints
;; Result: (((1 (X 1)) (1 (X 1))) ((1 (X 1)) (1 (Y 1)))
;;              ((1 (Y 1)) (1 (X 1))) ((1 (Y 1)) (1 (Y NEW))))

;; *second* remains the same

[westbaker]

Thanks everyone for the posts, the copy-tree version of the program works perfectly.


Thanks very much