Topic: ---{Challenge}--- Compare two expressions

[Jeremy]

Alright gang, we are going to create a function that I will call SCOMPARE that is short for "Structure Compare". This function takes two arguments x and y that are any two valid expressions. The function must return T if both expressions have the same structure and nil otherwise, it is a higher order function. To clarify better here are some examples:

(scompare 3 (list a b)) -> nil
(scompare (list a b)(list c d)) -> T ;can have different atoms but nesting must be the same
(scompare (list a b)(c . d)) -> nil ;conses not the same as lists
(scompare (list a (list b c))(list d (list e f))) -> T

I hope I have defined the task adequately. Let the programs begin!

[Kerry]

Jeremy,
Can we assume you want to assert the TYPE of the content of lists ; not that they evaluate to the same thing.

added: Do you only care that the variable contains say a 2 element list.
I imagine you will want the differentiate between a 3 element list of reals and a 3 element list of lists ... ?
There will be some clarification of your rules required.

An edge case :

Code - Auto/Visual Lisp: [Select]

1. (setq a 42
2.       b 2.2
3. )
4.  
5. (setq v1 (list a b)
6.       v2 '(a b)
7. )
8.  
9.  
10. (type v1)       ;-> LIST
11. (type v2)       ;-> LIST
12.  
13. (type a)        ;=> INT
14. (type (car v1)) ;=> INT
15.  
16. (type (car v2))  ;=> SYM
17.  
18. (type (eval (car v1)) )  ;=> INT
19.  
20. (type (eval (car v2)) )  ;=> INT
21.  

[bruno_vdh]

Hello,

My proposal for a similar structure...

Code: [Select]

(defun bv:scompare (a b)
  (cond ((atom a) (atom b))
        ((atom b) nil)
        ((bv:scompare (car a) (car b)) (bv:scompare (cdr a) (cdr b)))
  )
)
Regards,

[roy_043]

Hello,

My proposal for a similar structure...

Code: [Select]

(defun bv:scompare (a b)
  (cond ((atom a) (atom b))
        ((atom b) nil)
        ((bv:scompare (car a) (car b)) (bv:scompare (cdr a) (cdr b)))
  )
)
Regards,

I think we may already have our winner... Very good bruno_vdh!

[Lee Mac]

My proposal for a similar structure...

Code: [Select]

(defun bv:scompare (a b)
  (cond ((atom a) (atom b))
        ((atom b) nil)
        ((bv:scompare (car a) (car b)) (bv:scompare (cdr a) (cdr b)))
  )
)


Excellent work bruno - I doubt there is a more elegant solution than that! 

Just for fun, here is another:

Code - Auto/Visual Lisp: [Select]

1. (defun scompare ( a b )
2.     (or (and (atom  a) (atom  b))
3.         (and (listp a) (listp b) (= (length a) (length b)) (vl-every 'scompare a b))
4.     )
5. )

Incompatible with dotted pairs however, as a 'car/cdr' iterator must be used.

[bruno_vdh]

Thank you to both of you, your forum is very good

Incompatible with dotted pairs however, as a 'car/cdr' iterator must be used.

Yes, dotted pairs with difficult to work differently

Can we assume you want to assert the TYPE of the content of lists ; not that they evaluate to the same thing.
 

My variant for this hypothθse

Code: [Select]

(defun bv:compareStrTyp (a b)
  (if (or (atom a) (atom b))
    (eq (type a) (type b))
    (and (bv:compareStrTyp (car a) (car b)) (bv:compareStrTyp (cdr a) (cdr b)))
  )
)
Regards,

[Lee Mac]

Rewriting mine for type comparison:

Code - Auto/Visual Lisp: [Select]

1. (defun scomparetyp ( a b )
2.     (if (and (listp a) (listp b))
3.         (and (= (length a) (length b)) (vl-every 'scomparetyp a b))
4.         (= (type a) (type b))
5.     )
6. )

[Jeremy]

When I originally conceived this problem I was thinking in terms of having a function that could MAPCAR lists of any nested structure rather than just vector lists. So for instance we could do something like (newmapcar '+ (list 1 (list 2 3))(list 4 (list 5 6))) -> (list 5 (list 7 9)). To do this however you need a function like SCOMPARE so that you can tell if your two input structures are compatible. So this is kind of where I was aiming for. With such a mapcar one could take any dyadic function and make it super general. In the case of addition one would not have to write extra addition operators for vector addition, matrix addition etc.

You guys are fast with the answers!

[bruno_vdh]

Quickly, on the same algorithm a simple version:

Code: [Select]

(defun maptree (f l m)
  (cond
    ((null l) nil)
    ((atom l) (apply f (list l m)))
    ((cons (maptree f (car l) (car m)) (maptree f (cdr l) (cdr m))))
  )
)


Code: [Select]

_$ (maptree '+ (list 1 (list 2 3))(list 4 (list 5 6)))
(5 (7 9))Regards,

[Lee Mac]

Another (since mapcar also cannot process dotted pairs):

Code - Auto/Visual Lisp: [Select]

1. (defun maptree ( f l m )
2.     (if (atom l) ((eval f) l m) (mapcar '(lambda ( a b ) (maptree f a b)) l m))
3. )

Code - Auto/Visual Lisp: [Select]

1. _$ (maptree '+ (list 1 (list 2 3))(list 4 (list 5 6)))
2. (5 (7 9))

[Lee Mac]

Or, since mapcar accepts multiple list arguments:

Code - Auto/Visual Lisp: [Select]

1. (defun maptree ( f l )
2.     (if (atom (car l))
3.         (apply f l)
4.         (mapcar '(lambda ( x ) (maptree f x)) (apply 'mapcar (cons 'list l)))
5.     )
6. )

Code - Auto/Visual Lisp: [Select]

1. _$ (maptree '+ (list (list 1 (list 2 3)) (list 4 (list 5 6)) (list 7 (list 8 9))))
2. (12 (15 18))

[bruno_vdh]

Nice Lee, especially the second,

In the first beware of ((eval f) l m), it does not support special form.
I prefer (apply f (list l m)) slower
Or (eval (list f  l m))  more general

Regard,

[Lee Mac]

Nice Lee, especially the second,

Thanks bruno 

In the first beware of ((eval f) l m), it does not support special form.
I prefer (apply f (list l m)) slower
Or (eval (list f  l m))  more general

Good catch & suggestions -

Code - Auto/Visual Lisp: [Select]

1. _$ (maptree 'and '(t (t nil)) '(t (t t)))
2. ; error: cannot apply special form: AND

Fixed -

Code - Auto/Visual Lisp: [Select]

1. (defun maptree ( f l m )
2.     (if (atom l)
3.         (apply f (list l m))
4.         (mapcar '(lambda ( a b ) (maptree f a b)) l m)
5.     )
6. )

Code - Auto/Visual Lisp: [Select]

1. _$ (maptree 'and '(t (t nil)) '(t (t t)))
2. (T (T nil))

[bruno_vdh]

Or, since mapcar accepts multiple list arguments:
 

For the game, and not have to rewrite the function 
http://www.theswamp.org/index.php?topic=49813.msg550282#msg550282

Code: [Select]

_$ (reduceKey 'maptree '+ '((1 (2 3)) (4 (5 6)) (7 (8 9))))
(12 (15 18))
Regards,