[LISP] Uguaglianza fra due liste

[fbcyborg]

Ciao a tutti,

sto sbattendo la testa al muro da questa mattina su una funzione LISP che dovrebbe restituirmi T se due liste sono uguali.
Ho fatto una funzione ausiliaria che date due liste L1 e L2 restituisce T se gli elementi di L1 sono contenuti in L2.

(DEFUN AUX(L1 L2)(COND ((NULL L1) T)((MEMBER(CAR L1) L2)(AUX(CDR L1)L2))(T NIL)))

Questa funzione funziona correttamente.

Ora per testare che L1 = L2 devo verificare che gli elementi di L1 sono contenuti in L2 e che gli elementi di L2 sono contenuti in L1. Per questo ho fatto questa funzione:

(DEFUN UGUALI(L1 L2)(COND((AND(AUX(L1 L2))(AUX(L2 L1)))T)(T NIL)))

Il problema è che la seconda funzione non va... Perché????
Se faccio una prova ottengo un risultato che non riesco a capire:

> (UGUALI '(A B C) '(C B A))

*** - EVAL: undefined function L1
The following restarts are available:
USE-VALUE      :R1      You may input a value to be used instead of (FDEFINITION 'L1).
RETRY          :R2      Retry
STORE-VALUE    :R3      You may input a new value for (FDEFINITION 'L1).

Dov'è il problema?


EDIT: Risolto, sbagliavo a mettere le parentesi nei parametri dell'AND:

(DEFUN UGUALI(L1 L2)(COND((AND (AUX L1 L2) (AUX L2 L1))T)(T NIL)))

[shinya]

Il mio lisp è molto rozzo eh... in scheme farei una roba tipo

(define (eq-list? a b)
  (cond
    ((and (null? a)(null? b)) #t)
    ((or (null? a)(null? b)) #f)
    ((eq? (car a)(car b)) (eq-list? (cdr a)(cdr b)))
    (else #f)))

edit: giusto per correttezza, adesso questo funziona anche per liste con lunghezza diversa...

[fbcyborg]

Ti ringrazio, anche se in realtà ho risolto. Inoltre il mio codice non presuppone che le liste siano di pari lunghezza, funziona comunque. In realtà si suppone però che non ci siano elementi duplicati.

[marco.r]

Originariamente inviato da fbcyborg

Ciao a tutti,

sto sbattendo la testa al muro da questa mattina su una funzione LISP che dovrebbe restituirmi T se due liste sono uguali.
Ho fatto una funzione ausiliaria che date due liste L1 e L2 restituisce T se gli elementi di L1 sono contenuti in L2.

(DEFUN AUX(L1 L2)(COND ((NULL L1) T)((MEMBER(CAR L1) L2)(AUX(CDR L1)L2))(T NIL)))

Questa funzione funziona correttamente.

Ora per testare che L1 = L2 devo verificare che gli elementi di L1 sono contenuti in L2 e che gli elementi di L2 sono contenuti in L1. Per questo ho fatto questa funzione:

(DEFUN UGUALI(L1 L2)(COND((AND(AUX(L1 L2))(AUX(L2 L1)))T)(T NIL)))

Il problema è che la seconda funzione non va... Perché????
Se faccio una prova ottengo un risultato che non riesco a capire:

> (UGUALI '(A B C) '(C B A))

*** - EVAL: undefined function L1
The following restarts are available:
USE-VALUE      :R1      You may input a value to be used instead of (FDEFINITION 'L1).
RETRY          :R2      Retry
STORE-VALUE    :R3      You may input a new value for (FDEFINITION 'L1).

Dov'è il problema?


EDIT: Risolto, sbagliavo a mettere le parentesi nei parametri dell'AND:

(DEFUN UGUALI(L1 L2)(COND((AND (AUX L1 L2) (AUX L2 L1))T)(T NIL)))

Con "uguali" intendi dire che contengono gli stessi argomenti (ma in ordine diverso?). Non e' proprio la stessa cosa.

[fbcyborg]

Con uguali, intendo dire che gli elementi della prima lista sono contenuti nella seconda e quelli della seconda sono contenuti nella prima.
Lo so che non è perfetta, ma per ora è tutto ciò che sono riuscito a fare.
L'ordine degli elementi non conta.

[shinya]

Originariamente inviato da fbcyborg

Con uguali, intendo dire che gli elementi della prima lista sono contenuti nella seconda e quelli della seconda sono contenuti nella prima.
Lo so che non è perfetta, ma per ora è tutto ciò che sono riuscito a fare.
L'ordine degli elementi non conta.

Allora la mia versione non va bene :P

[fbcyborg]

Va bene, vi ringrazio tutti,

ho risolto il mio problema con le informazioni che mi avete dato.

[marco.r]

se vuoi andare sul sicuro anche quando hai elementi ripetuti, ti conviene "toglierti dalle scatole" quelli in cui sei gia' incorso.
Qualcosa del tipo

(defun uguali (l1 l2)
	   (if (null l1) 
	       (null l2)
	       (and (member (first l1) l2)
		    (uguali (cdr l1) (remove (first l1) l2 :count 1)))))

Ovvero, le due liste sono uguale se sono entrambe vuote oppure
se il primo elemento della prima lista appare nella seconda, e quel che resta delle due liste sono uguali
Ho usato le funzioni member e remove del common lisp, pero' dovresti trovare l'equivalente nel tuo linguaggio.