LISP - Establecer

Common Lisp no proporciona un tipo de datos establecido. Sin embargo, proporciona una serie de funciones que permiten realizar operaciones de conjunto en una lista.

Puede agregar, eliminar y buscar elementos en una lista, según varios criterios. También puede realizar varias operaciones de conjuntos como: unión, intersección y diferencia de conjuntos.

Implementación de conjuntos en LISP

Los conjuntos, como las listas, se implementan generalmente en términos de celdas de cons. Sin embargo, por esta misma razón, las operaciones de conjuntos se vuelven cada vez menos eficientes cuanto más grandes se vuelven los conjuntos.

los adjoinLa función le permite crear un conjunto. Toma un elemento y una lista que representa un conjunto y devuelve una lista que representa el conjunto que contiene el elemento y todos los elementos del conjunto original.

los adjoinla función primero busca el elemento en la lista dada, si se encuentra, luego devuelve la lista original; de lo contrario, crea una nueva celda de contras con sucar como el artículo y cdr apunta a la lista original y devuelve esta nueva lista.

los adjoin la función también toma :key y :testargumentos de palabras clave. Estos argumentos se utilizan para comprobar si el elemento está presente en la lista original.

Dado que la función adjunta no modifica la lista original, para realizar un cambio en la lista misma, debe asignar el valor devuelto por adjunto a la lista original o puede utilizar la macro pushnew para agregar un artículo al conjunto.

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset* (adjoin 1 *myset*))
(setf *myset* (adjoin 2 *myset*))

;now the original set is changed
(write *myset*)
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
(write *myset*)
(terpri)

;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

Cuando ejecuta el código, devuelve el siguiente resultado:

NIL
(2 1)
(2 1)
(3 2 1)

Comprobación de membresía

El grupo de funciones de miembros le permite verificar si un elemento es miembro de un conjunto o no.

Las siguientes son las sintaxis de estas funciones:

member item list &key :test :test-not :key 
member-if predicate list &key :key 
member-if-not predicate list &key :key

Estas funciones buscan en la lista dada un elemento dado que satisfaga la prueba. Si no se encuentra tal elemento, las funciones devuelvennil. De lo contrario, se devuelve la cola de la lista con el elemento como primer elemento.

La búsqueda se realiza únicamente en el nivel superior.

Estas funciones podrían usarse como predicados.

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

Cuando ejecuta el código, devuelve el siguiente resultado:

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

Establecer unión

El grupo de funciones de unión le permite realizar una unión de conjuntos en dos listas proporcionadas como argumentos para estas funciones sobre la base de una prueba.

Las siguientes son las sintaxis de estas funciones:

union list1 list2 &key :test :test-not :key 
nunion list1 list2 &key :test :test-not :key

los unionLa función toma dos listas y devuelve una nueva lista que contiene todos los elementos presentes en cualquiera de las listas. Si hay duplicaciones, solo se conserva una copia del miembro en la lista devuelta.

los nunion La función realiza la misma operación pero puede destruir las listas de argumentos.

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Cuando ejecuta el código, devuelve el siguiente resultado:

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

Tenga en cuenta

La función de unión no funciona como se esperaba sin :test-not #'mismatchargumentos para una lista de tres vectores. Esto se debe a que las listas están hechas de celdas de contras y, aunque aparentemente los valores nos parecen los mismos, elcdrparte de las celdas no coincide, por lo que no son exactamente iguales al intérprete / compilador LISP. Esta es la razón; No se recomienda implementar grandes conjuntos usando listas. Sin embargo, funciona bien para juegos pequeños.

Establecer intersección

El grupo de funciones de intersección le permite realizar la intersección en dos listas proporcionadas como argumentos para estas funciones sobre la base de una prueba.

Las siguientes son las sintaxis de estas funciones:

intersection list1 list2 &key :test :test-not :key 
nintersection list1 list2 &key :test :test-not :key

Estas funciones toman dos listas y devuelven una nueva lista que contiene todos los elementos presentes en ambas listas de argumentos. Si alguna de las listas tiene entradas duplicadas, las entradas redundantes pueden aparecer o no en el resultado.

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Cuando ejecuta el código, devuelve el siguiente resultado:

(C)
(#(A B) #(5 6 7))
NIL

La función de intersección es la versión destructiva de la intersección, es decir, puede destruir las listas originales.

Establecer diferencia

El grupo de funciones de diferencia de conjuntos le permite realizar diferencias de conjuntos en dos listas proporcionadas como argumentos para estas funciones sobre la base de una prueba.

Las siguientes son las sintaxis de estas funciones:

set-difference list1 list2 &key :test :test-not :key 
nset-difference list1 list2 &key :test :test-not :key

La función de diferencia de conjuntos devuelve una lista de elementos de la primera lista que no aparecen en la segunda lista.

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Cuando ejecuta el código, devuelve el siguiente resultado:

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))