¿Tiene Common Lisp algo así como la interfaz de conjunto de Java/implementación de clases?

Question

Necesito algo como this, una colección de elementos que no contiene duplicados de ningún elemento. ¿Common Lisp, específicamente SBCL, tiene algo como esto?

Answer 1

No es que yo sepa, pero puede utilizar hash tables para algo bastante similar.

Answer 2

Lisp hashtables basado en CLOS. Especificaciones here.

Answer 3

Para una solución rápida, solo use tablas hash, como se ha mencionado anteriormente.

Sin embargo, si prefiere un enfoque más basado en principios, puede echar un vistazo a FSet, que es "una biblioteca de colecciones teórico-de-conjuntos funcional". Entre otros, contiene clases y operaciones para conjuntos y bolsas.

(EDIT :) La manera más limpia probablemente sea definir sus operaciones orientadas a conjuntos como funciones genéricas. Después de todo, un conjunto de funciones genéricas es básicamente equivalente a una interfaz Java. Simplemente puede implementar métodos en la clase estándar HASH-TABLE como primer prototipo y permitir otras implementaciones también.

Answer 4

Puede usar listas, aunque pueden resultar ineficaces para representar conjuntos grandes. Esto se hace usando ADJOIN o PUSHNEW para agregar un nuevo elemento a una lista, y DELETE or REMOVE para hacer lo opuesto.

(let ((set (list))) 
    (pushnew 11 set) 
    (pushnew 42 set) 
    (pushnew 11 set) 
    (print set) ; set={42,11} 
    (setq set (delete 42 set)) 
    (print set)) ; set={11} 

Una cosa a tener en cuenta es todo lo que estos operadores utilizan EQL por defecto para la prueba de posibles duplicados en el conjunto (tanto como Java utiliza el método equals). Eso está bien para conjuntos que contienen números o caracteres, pero para conjuntos de otros objetos, una prueba de igualdad "más profunda" como EQUAL se debe especificar como un parámetro de palabra clave TEST, p. para un conjunto de cadenas: -

(let ((set (list))) 
    (pushnew "foo" set :test #'equal) 
    (pushnew "bar" set :test #'equal) 
    (pushnew "foo" set :test #'equal) ; EQUAL decides that "foo"="foo" 
    (print set)) ; set={"bar","foo"} 

homólogos de Lisp a algunas de las operaciones Set de Java son:

• addAll ->UNION or NUNION
• containsAll ->SUBSETP
• removeAll ->SET-DIFFERENCE or NSET-DIFFERENCE
• keepAll ->INTERSECTION or NINTERSECTION

Answer 5

Mire cl-containers. Hay una clase set-container.

Answer 6

Sí, tiene juegos. Ver this section on "Sets" de Practical Common Lisp.

Básicamente, puede crear un conjunto con pushnew y adjoin, consultar con member, member-if y member-if-not, y combinarlo con otros conjuntos con funciones como intersection, union, set-difference, set-exclusive-or y subsetp.

Answer 7

Se puede solucionar fácilmente con una tabla hash.

(let ((h (make-hash-table :test 'equalp))) ; if you're storing symbols 
    (loop for i from 0 upto 20 
     do (setf (gethash i h) (format nil "Value ~A" i))) 
    (loop for i from 10 upto 30 
     do (setf (gethash i h) (format nil "~A eulaV" i))) 
    (loop for k being the hash-keys of h using (hash-value v) 
     do (format t "~A => ~A~%" k v))) 

salidas

0 => Value 0 
1 => Value 1 
... 
9 => Value 9 
10 => 10 eulaV 
11 => 11 eulaV 
... 
29 => 29 eulaV 
30 => 30 eulaV 

Answer 8

Personalmente, yo sólo sería implementar una función que toma una lista y devolver un conjunto único. He redactado algo juntos que funciona para mí:

(defun make-set (list-in &optional (list-out '())) 
    (if (endp list-in) 
     (nreverse list-out) 
     (make-set 
     (cdr list-in) 
     (adjoin (car list-in) list-out :test 'equal)))) 

Básicamente, la función adjoin antepone un elemento a una lista de forma no destructiva si y sólo si el artículo no está ya en la lista, la aceptación de una prueba opcional función (una de las funciones "iguales" de Common Lisp). También puede usar pushnew para hacerlo destructivamente, pero creo que la implementación recursiva de cola es mucho más elegante. Entonces, Lisp exporta varias funciones básicas que le permiten usar una lista como un conjunto; no se necesita ningún tipo de datos incorporado porque puede usar diferentes funciones para anteponer las cosas a una lista.

Mi fuente de datos para todo esto (no la función, sino la información) ha sido una combinación de Common Lisp HyperSpec y Common Lisp the Language (2nd Edition).