Есть ли в Common Lisp что-то вроде Java-интерфейса Set / реализации классов?

Question

Мне нужно что-то вроде this , набор элементов, который не содержит дубликатов ни одного элемента. У Common Lisp, особенно SBCL, есть что-то подобное?

Answer 1

Посмотрите на cl-container . Есть класс set-container.

Answer 2

Для быстрого решения просто используйте хеш-таблицы, как уже упоминалось ранее.

Однако, если вы предпочитаете более принципиальный подход, вы можете взглянуть на FSet , который является «функциональной теоретико-множественной библиотекой коллекций». Среди прочего, он содержит классы и операции для наборов и сумок.

(РЕДАКТИРОВАТЬ :) Самым чистым способом, вероятно, было бы определение ваших операций, ориентированных на наборы, как универсальных функций. В конце концов, набор универсальных функций в основном эквивалентен интерфейсу Java. Вы можете просто реализовать методы в стандартном классе HASH-TABLE в качестве первого прототипа, а также разрешить другие реализации.

Answer 3

Да, у него есть наборы. См. в этом разделе «Наборы» из Практический общий Лисп .

По сути, вы можете создать набор с помощью pushnew и adjoin, запросить его с помощью member, member-if и member-if-not и объединить его с другими наборами с такими функциями, как intersection, union set-difference, set-exclusive-or и subsetp.

Answer 4

Вы можете использовать списки, хотя они могут оказаться неэффективными для представления больших наборов. Это делается с помощью 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 -> СОЮЗ или ОБЪЕДИНЕНИЕ
• содержит все -> SUBSETP
• removeAll -> SET-DIFFERENCE или NSET-DIFFERENCE
• retainAll -> Пересечение или NINTERSECTION

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

Лично я бы просто реализовал функцию, которая принимает список и возвращает уникальный набор. Я написал кое-что вместе, что работает для меня:

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

Answer 8

Хеш-таблицы Lisp основаны на CLOS. Спецификации здесь .