Page 1 of 1
Cartesian product of 2 lists which is NOT dependent
Posted: Wed Jan 05, 2011 12:13 pm
by 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
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Wed Jan 05, 2011 1:21 pm
by 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?
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Wed Jan 05, 2011 4:36 pm
by 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
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Thu Jan 06, 2011 2:41 am
by 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)))
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Thu Jan 06, 2011 12:48 pm
by 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
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Thu Jan 06, 2011 2:24 pm
by 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)))
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Thu Jan 06, 2011 10:29 pm
by 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))
: How embarrassing. Of course I meant
Code: Select all
(defun mappend (fn &rest lists)
(apply #'append (apply #'mapcar fn lists)))
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Sat Jan 08, 2011 1:46 pm
by 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
Re: Cartesian product of 2 lists which is NOT dependent
Posted: Sat Jan 08, 2011 3:20 pm
by westbaker
Thanks everyone for the posts, the copy-tree version of the program works perfectly.
Thanks very much