java - Common Lisp 是否有类似 java 的 Set Interface/implementing classes 的东西？

Question

我需要这样的东西，一个不包含任何元素重复的元素集合。Common Lisp，特别是 SBCL，有这样的东西吗？

Answer 1

为了快速解决，只需使用哈希表，如前所述。

但是，如果您更喜欢更有原则的方法，您可以查看FSet，它是“一个功能集合论集合库”。其中，它包含集合和包的类和操作。

（编辑：）最干净的方法可能是将面向集合的操作定义为通用函数。毕竟，一组泛型函数基本上相当于一个 Java 接口。您可以简单地在标准 HASH-TABLE 类上实现方法作为第一个原型，并允许其他实现。

Answer 2

看看cl-containers。有一个集合容器类。

Answer 3

您可以使用列表，尽管它们可能被证明在表示大型集合时效率低下。这是通过使用 ADJOIN 或PUSHNEW将新元素添加到列表中来完成的，并使用DELETE 或 REMOVE来执行相反的操作。

(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}

需要注意的一件事是，这些运算符默认使用EQL来测试集合中的潜在重复项（就像 Java 使用 equals 方法一样）。这对于包含数字或字符的集合是可以的，但是对于其他对象的集合，应该将诸如EQUAL之类的“更深”的相等测试指定为 :TEST 关键字参数，例如对于一组字符串：-

(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"}

Lisp 与 Java 的一些 Set 操作对应的是：

• addAll -> UNION 或NUNION
• containsAll -> SUBSETP
• removeAll -> SET-DIFFERENCE 或 NSET-DIFFERENCE
• retainAll -> INTERSECTION 或 NINTERSECTION

Answer 4

是的，它有套装。请参阅Practical Common Lisp中关于“Sets”的这一部分。

基本上，您可以使用 和 创建一个集合，使用pushnew和adjoin查询它member，member-if并将member-if-not其与其他具有intersection、union、set-difference和set-exclusive-or等函数的集合组合subsetp。

Answer 5

使用哈希表可以轻松解决。

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

输出

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

Answer 6

不是我知道的，但是您可以将哈希表用于非常相似的事情。

Answer 7

Lisp 哈希表是基于 CLOS 的。规格在这里。

Answer 8

就个人而言，我只会实现一个函数，它接受一个列表并返回一个唯一的集合。我一起起草了一些对我有用的东西：

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

基本上，adjoin当且仅当该项目尚未出现在列表中时，该函数才会非破坏性地将项目添加到列表中，接受可选的测试函数（Common Lisp“相等”函数之一）。你也可以pushnew破坏性地这样做，但我发现尾递归实现要优雅得多。因此，Lisp 确实导出了几个基本函数，允许您将列表用作集合；不需要内置数据类型，因为您可以使用不同的函数将内容添加到列表中。

我所有这些的数据源（不是函数，而是信息）是Common Lisp HyperSpec和Common Lisp the Language (2nd Edition)的组合。