Учебники

LISP — Набор

Декабрь 13, 2018

Common Lisp не предоставляет установленный тип данных. Однако он предоставляет ряд функций, позволяющих выполнять операции над списком.

Вы можете добавлять, удалять и искать элементы в списке на основе различных критериев. Вы также можете выполнять различные операции над множествами, такие как: объединение, пересечение и разность множеств.

Реализация наборов в LISP

Наборы, подобные спискам, обычно реализуются в терминах cons-ячеек. Однако именно по этой причине операции с множествами становятся все менее эффективными, чем больше сеты.

Примыкающая функция позволяет создавать набор. Он берет элемент и список, представляющий набор, и возвращает список, представляющий набор, содержащий элемент и все элементы в исходном наборе.

Примыкающая функция сначала ищет элемент в данном списке, если он найден, затем возвращает исходный список; в противном случае он создает новую ячейку cons со своим автомобилем в качестве элемента и cdr, указывающим на исходный список, и возвращает этот новый список.

Примыкающая функция также принимает аргументы : key и : test key . Эти аргументы используются для проверки наличия элемента в исходном списке.

Поскольку функция примыкания не изменяет исходный список, чтобы внести изменения в сам список, необходимо либо присвоить значение, возвращаемое примыканием, к исходному списку, либо использовать макрос pushnew для добавления элемента в набор.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo

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

Когда вы выполняете код, он возвращает следующий результат — 

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

Проверка членства

Группа функций-членов позволяет вам проверить, является ли элемент членом набора или нет.

Ниже приведены синтаксисы этих функций — 

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

Эти функции выполняют поиск в указанном списке для данного элемента, который удовлетворяет критерию. Если такой элемент не найден, функции возвращают ноль. В противном случае возвращается хвост списка с элементом в качестве первого элемента.

Поиск ведется только на верхнем уровне.

Эти функции могут быть использованы в качестве предикатов.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo 

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

Когда вы выполняете код, он возвращает следующий результат — 

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

Установить Союз

Группа функций объединения позволяет выполнять объединение множеств в двух списках, представленных в качестве аргументов этих функций на основе теста.

Ниже приведены синтаксисы этих функций — 

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

Функция union принимает два списка и возвращает новый список, содержащий все элементы, присутствующие в любом из списков. Если есть дубликаты, то в возвращенном списке сохраняется только одна копия члена.

Функция nunion выполняет ту же операцию, но может уничтожить списки аргументов.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo 

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

Когда вы выполняете код, он возвращает следующий результат — 

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

Пожалуйста, обратите внимание

Функция объединения не работает должным образом без : test-not # ‘несоответствующие аргументы для списка из трех векторов. Это потому, что списки состоят из cons-ячеек, и, хотя значения выглядят одинаково для нас, очевидно, cdr- часть ячеек не совпадает, поэтому они не совсем совпадают с интерпретатором / компилятором LISP. Это причина; реализация больших наборов не рекомендуется при использовании списков. Это работает хорошо для небольших наборов, хотя.

Установить пересечение

Группа функций пересечения позволяет выполнять пересечение в двух списках, представленных в качестве аргументов этих функций на основе теста.

Ниже приведены синтаксисы этих функций — 

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

Эти функции принимают два списка и возвращают новый список, содержащий все элементы, присутствующие в обоих списках аргументов. Если в любом списке есть повторяющиеся записи, избыточные записи могут появиться или не появиться в результате.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo 

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

Когда вы выполняете код, он возвращает следующий результат — 

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

Функция пересечения является деструктивной версией пересечения, то есть она может уничтожить исходные списки.

Установить разницу

Группа функций разности множеств позволяет выполнять разности множеств в двух списках, представленных в качестве аргументов этих функций на основе теста.

Ниже приведены синтаксисы этих функций — 

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

Функция set-Difference возвращает список элементов первого списка, которые не отображаются во втором списке.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo 

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

Когда вы выполняете код, он возвращает следующий результат —

47
Share: