Как использовать «минусы» без генерации вложенных списков в схеме?

Question

При попытке создать список подмножеств, существующих в двух наборах, я столкнулся с проблемой с cons .Процедура принимает список с именем result и пытается создать новый список из result и car из другого набора.Пока набор генерируется с правильными элементами, но они содержатся в вложенном списке размером N , где N - количество вложений и количество элементов в подмножестве, которое я ищу.

Как применить cons с result без создания вложенного списка?

Пример:

;These are two sets that I will be checking
(define s1 '(1 2 3 4))
(define s2 '(1 2 3))
;Result from running these lists through my procedure
(((() . 1) . 2) . 3)
;What I want to have generated
(1 2 3)

Мне нужно позвонить (car list) и получить 1 не ((() . 1) . 2)

Answer 1

Прежде всего (((() . 1) . 2) . 3) - это не вложенный список - это вообще не список. (((() 1) 2) 3) будет вложенным списком. (((() . 1) . 2) . 3) - это пунктирная пара, первый элемент которой также является пунктирной парой.

Теперь объясним поведение, которое вы видите: В семействе языков lisp (cons a b) создает пару, содержащую a в качестве car и b в качестве cdr.

Теперь список - это либо пустой список (()), либо пара, чья cdr также является списком (car может содержать что угодно - если и cdr, и car являются списком список называется вложенным списком).

Пара, которая не является списком, называется пунктирной парой. Это то, что вы создаете здесь, потому что вы вызываете cons со вторым аргументом, который не является списком.

Вывод:

Вы не можете использовать cons для добавления в конец списка. Если вам нужно добавить в конец списка, вы можете использовать concat со списком из одного элемента в качестве второго аргумента.

Обратите внимание, что добавление в конец списка - это операция O(n), в то время как добавление спереди (с использованием cons) - это операция O(1), поэтому, если возможно, вы должны изменить свой алгоритм, чтобы он был только нужно добавить в передней части.