Cartesian product of 2 lists which is NOT dependent
Cartesian product of 2 lists which is NOT dependent
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
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
-
- Posts: 117
- Joined: Tue Aug 10, 2010 11:24 pm
- Location: Calgary, Alberta
- Contact:
Re: Cartesian product of 2 lists which is NOT dependent
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:
Can you tell us (or show us) the destructive operations you are using?
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))
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.
Re: Cartesian product of 2 lists which is NOT dependent
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
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
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:
Output:
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)))
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
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
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
I think copy-tree is what you want.
Output:
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)))
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)))
-
- Posts: 8
- Joined: Sat Nov 20, 2010 10:00 pm
Re: Cartesian product of 2 lists which is NOT dependent
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:
Edit: How embarrassing. Of course I meant
Code: Select all
(defun mappend (&rest lists)
(apply #'append lists))
Code: Select all
(defun mappend (fn &rest lists)
(apply #'append (apply #'mapcar fn lists)))
-
- Posts: 117
- Joined: Tue Aug 10, 2010 11:24 pm
- Location: Calgary, Alberta
- Contact:
Re: Cartesian product of 2 lists which is NOT dependent
@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:
The easy solution is to use copy tree on the result of the cross product.
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)))
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
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.
Re: Cartesian product of 2 lists which is NOT dependent
Thanks everyone for the posts, the copy-tree version of the program works perfectly.
Thanks very much
Thanks very much