Conjuntos en LISP

Un conjunto es una colección desordenada de elementos. Un conjunto es como otras estructuras de datos. En C++ tenemos una estructura de datos similar llamada mapa hash. Common Lisp no proporciona un tipo de datos de conjunto incorporado, pero proporciona una serie de funciones que permiten realizar operaciones de conjunto en una lista. Al usarlos, podemos agregar y eliminar elementos de la lista y también verificar si un elemento está presente en la lista. También podemos realizar operaciones de unión, intersección y diferencia en la lista.

Implementando conjuntos en Lisp:

Los conjuntos se implementan mediante la función adjunta . La función Adjoin nos permite construir un conjunto. La función adjunta puede tomar una lista como argumento y devuelve un conjunto. La función adjunta se define de la siguiente manera:

Sintaxis:

adjoin item list &key key test  => new-list

Aquí, el elemento es un objeto, la lista es una lista propiamente dicha, la prueba es un designador para una función de dos argumentos y devuelve un valor booleano, la clave es una función designadora para una función de un argumento.  

Estos argumentos clave y de prueba se utilizan para verificar si un elemento está presente en la lista o no. Si el elemento está presente en la lista, entonces el elemento no se agrega al conjunto. Si el elemento no está presente en la lista, se agrega al conjunto. Podemos usar la macro pushnew para agregar un elemento al conjunto, si el elemento no está presente en el conjunto, y ELIMINAR o ELIMINAR para eliminar o eliminar el elemento.

Ejemplo:

Cree un nuevo archivo lisp y guárdelo como set.lisp

;; Implementing the Sets in the Lisp
  
(defparameter *mynewset* ()) ;; empty set
(adjoin 1 *mynewset*) ;; *mynewset* is now (1)
(adjoin 2 *mynewset*) ;; *mynewset* is now (1 2)
  
; adjoin did not change the original set
; so it remains same
(write *mynewset*) ;; (1 2)
(terpri) ;; prints a new line
(setf *mynewset* (adjoin 1 *mynewset*)) ;; *mynewset* is now (1)
(setf *mynewset* (adjoin 2 *mynewset*)) ;; *mynewset* is now (1 2)
  
; adding an existing value
(pushnew 2 *mynewset*) ;; *mynewset* is now (1 2)
  
; no duplicate allowed
(write *mynewset*) ;; (1 2)
(terpri) ;; prints a new line
  
; pushing a new value
(pushnew 3 *mynewset*) ;; *mynewset* is now (1 2 3)
(write *mynewset*) ;; (1 2 3)
(terpri) ;; prints a new line

Producción:

Establecer implementación

Comprobación de pertenencia en un conjunto:

La Membresía es una función que comprueba si un elemento está presente en el conjunto o no. La función de pertenencia se define de la siguiente manera:

lista de elementos de miembros &key :test :test-not :key  

miembro-si lista de predicados &clave :clave  

miembro-si-no-lista de predicados &clave :clave

Estas funciones sondean la lista para el artículo. Si el elemento está presente en la lista, la función de pertenencia devuelve t. Si el elemento no está presente en la lista, la función de membresía devuelve nil. La búsqueda se realiza solo en el nivel superior. La búsqueda se realiza en el orden de la lista.

Sintaxis:

member item list test &key key &key => tail or nil

Aquí, el elemento es un elemento que se encuentra, la lista es la lista que se busca, la prueba es el elemento que se compara y &key es la tecla de función. Key es una función para extraer el valor antes de la prueba. La función miembro busca en la lista el elemento. Si el elemento está presente en la lista, la función de pertenencia devuelve t. Si el elemento no está presente en la lista, la función de membresía devuelve nil. La búsqueda se realiza solo en el nivel superior. La búsqueda se realiza en el orden de la lista.

Ejemplo:

Cree un nuevo archivo lisp y guárdelo como membresía.lisp.

;; Checking Membership in a Set
  
(write (member 0 (list 1 2 3)))  ;; returns nil
(terpri) ;; prints a new line
  
(write (member-if #'evenp '(5 7 9 8 4 ) ));; returns t
(terpri) ;; prints a new line
  
(write (member-if-not  #'numberp '(3 7 2 5/3 'not 'number ))) ;; returns nil

Producción:

Membresía en Conjunto

Establecer unión en Lisp:

La unión significa el conjunto de todos los elementos de la lista. Usando la función de grupo de unión, podemos encontrar la unión de dos conjuntos. La función de unión se define de la siguiente manera:

Sintaxis:

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

Aquí, la función de unión toma dos listas, list1 y list2, y devuelve una nueva lista que contiene todos los elementos de ambas listas. No se permiten elementos duplicados en la nueva lista.

Ejemplo:

Cree un nuevo archivo lisp y guárdelo como union.lisp.

;; Set union in Lisp
  
  
(setq set1 (union '(1 2 3) '(2 3 4))) ;; set1 is (1 2 3 4)
(terpri) ;; prints a new line
  
(setq set2 (union '(a b 5 6 7 f h) '(5 6 7 a b g h)))
  
(write set1) ;; (1 2 3 4)
(terpri)
(write set2) ;; (F 5 6 7 A B G H)
(terpri)

Producción:

Unión en conjunto

Establecer intersección en Lisp:

La intersección se puede considerar como el conjunto de elementos que son comunes a ambos conjuntos. Para hacer la intersección, podemos usar el grupo de funciones de intersección. Toma dos listas y devuelve una nueva lista que contiene todos los elementos que son comunes a ambas listas. La función de intersección se define de la siguiente manera:

Sintaxis:

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

Aquí, la función de intersección toma dos listas, list1 y list2, y devuelve una nueva lista que contiene todos los elementos que son comunes a ambas listas. La intersección es la misma que la función de intersección, excepto que destruye la lista1 usando sus celdas para construir la lista2 de resultados y devuelve la lista2 de resultados.  

Ejemplo:

Cree un nuevo archivo lisp y guárdelo como intersección.lisp.

;; Set intersection in Lisp
  
  
(setq set1 (intersection '(1 2 3) '(2 3 4))) ;; set1 is (2 3)
(terpri) ;; prints a new line
  
(setq set2 (intersection '(a b 5 6 7 f h) '(5 6 7 a b g h))) 
  
(write set1) ;; (2 3)
(terpri) ;; prints a new line
   
( write set2) ;; (A B 5 6 7 H)
(terpri)  ;; prints a new line

Producción:

Una intersección establecida en Lisp

Establecer diferencia en Lisp:

Una diferencia de conjunto es el conjunto de elementos que están en el primer conjunto pero no en el segundo conjunto. Usando la función de diferencia de conjuntos, podemos encontrar la diferencia de conjuntos de dos conjuntos. La función de diferencia de conjuntos se define de la siguiente manera:

Sintaxis:

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

Aquí, la función de diferencia de conjuntos toma dos listas, list1 y list2, y devuelve una nueva lista que contiene todos los elementos que están en la primera lista pero no en la segunda lista. La función nset-difference es la misma que la función de diferencia de conjuntos, excepto que destruye la lista1 usando sus celdas para construir la lista2 de resultados y devuelve la lista2 de resultados.

Set-difference devuelve una lista de elementos que están en la primera lista pero no en la segunda lista.

Nset es la versión destructiva de la diferencia de conjuntos, destruye la lista1 y devuelve el resultado lista2.

Ejemplo:

Cree un nuevo archivo lisp y guárdelo como set-difference.lisp.

;; Set Difference in Lisp
  
  
(write(setq lst1 (list "A" "b" "C" "d") lst2 (list "a" "B" "C" "d"))) 
;; lst1 is ("A" "b" "C" "d") lst2 is ("a" "b" "C" "d")
(write(set-difference lst1 lst2)) ;; returns ("A" "C")
(terpri) ;; prints a new line
  
(write(set-difference lst1 lst2 :test 'equal)) ;; returns ("A" "C")
(terpri) ;; prints a new line
  
(write(nset-difference lst1 lst2 :test #'string=));; returns ("A" "b" "C" "d")
(terpri) ;; prints a new line

Producción:

Establecer diferencia en ceceo