TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: Jeremy on July 29, 2015, 11:23:00 PM

Title: ---{Challenge}--- Compare two expressions
Post by: Jeremy on July 29, 2015, 11:23:00 PM

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!

Title: Re: ---{Challenge}--- Compare two expressions
Post by: Kerry on July 29, 2015, 11:53:16 PM

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.  

Title: Re: ---{Challenge}--- Compare two expressions
Post by: bruno_vdh on July 30, 2015, 03:19:50 AM

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,

Title: Re: ---{Challenge}--- Compare two expressions
Post by: roy_043 on July 30, 2015, 03:31:54 AM

Quote from: bruno_vdh on July 30, 2015, 03:19:50 AM

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!

Title: Re: ---{Challenge}--- Compare two expressions
Post by: Lee Mac on July 30, 2015, 04:28:08 AM

Quote from: bruno_vdh on July 30, 2015, 03:19:50 AM

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.

Title: Re: ---{Challenge}--- Compare two expressions
Post by: bruno_vdh on July 30, 2015, 05:34:58 AM

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

Quote from: Lee Mac on July 30, 2015, 04:28:08 AM

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

Yes, dotted pairs with difficult to work differently

Quote from: Kerry on July 29, 2015, 11:53:16 PM

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,

Title: Re: ---{Challenge}--- Compare two expressions
Post by: Lee Mac on July 30, 2015, 05:49:59 AM

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. )

Title: Re: ---{Challenge}--- Compare two expressions
Post by: Jeremy on July 30, 2015, 03:39:14 PM

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!

Title: Re: ---{Challenge}--- Compare two expressions
Post by: bruno_vdh on July 30, 2015, 04:41:04 PM

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,

Title: Re: ---{Challenge}--- Compare two expressions
Post by: Lee Mac on July 30, 2015, 04:54:33 PM

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))

Title: Re: ---{Challenge}--- Compare two expressions
Post by: Lee Mac on July 30, 2015, 05:52:32 PM

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))

Title: Re: ---{Challenge}--- Compare two expressions
Post by: bruno_vdh on July 30, 2015, 06:00:38 PM

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,

Title: Re: ---{Challenge}--- Compare two expressions
Post by: Lee Mac on July 30, 2015, 06:19:11 PM

Quote from: bruno_vdh on July 30, 2015, 06:00:38 PM

Nice Lee, especially the second,

Thanks bruno  :-)

Quote from: bruno_vdh on July 30, 2015, 06:00:38 PM

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))

Title: Re: ---{Challenge}--- Compare two expressions
Post by: bruno_vdh on July 31, 2015, 06:38:27 AM

Quote from: Lee Mac on July 30, 2015, 05:52:32 PM

Or, since mapcar accepts multiple list arguments:
 

For the game, and not have to rewrite the function  :wink:
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,