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

@LSTSnaiper · Регистрация: 18.03.2018

Author24 — интернет-сервис помощи студентам

Доброго времени суток, господа.
Предо мной поставлена такая задача: Разработать функцию, находящую теоретико-множественную разность двух списков.
Код, который бы решал эту задачу я нашёл, но хотелось бы разобраться в сути решения, как работает этот код всё понять не могу даже с трассировкой.

Lisp

(defun difference (w v)
  (cond ((null w) w)
        ((member (car w) v) (difference (cdr w) v))
        ((cons (car w) (difference (cdr w) v)))))

Для проверки кода

Lisp

1	(difference '(1 2 3 4 5) '(4 5 6))

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

Мои мысли:
1. Объявляется функция difference с двумя параметрами w и v
2. Объявляются 3 условия для оператора cond из них
2.1. ((null w) w) - я так понял тут проверяется каждый элемент списка w на null, если нет null-ов, то возвращается nil
2.2. ((member (car w) v) (difference (cdr w) v)) - Функция member проверяет, находится ли первый аргумент внутри списка , представленного вторым аргументом, то есть member проверяет находится ли первый элемент (голова списка) w (1) в списке v (4 5 6) и после функция вызывает саму себя с аргументами, равными конечному элементу списка w (5) и v (456) и после я теряю связь с реальностью, т.к не могу такую вложенность уместить у меня в голове ☺

@Catstail · 21.12.2021, 22:09

Сообщение от LSTSnaiper

((null w) w) - я так понял тут проверяется каждый элемент списка w на null, если нет null-ов, то возвращается nil

- нет. Проверяется весь список w - не пуст ли он. Если пуст, то пусто и пересечение. Автор кода немного "выпендрился". Понятнее было бы так:

Lisp

1
2
3

 ...
(cond ((null w) nil)
 ...

Lisp

1	((member (car w) v) (difference (cdr w) v))

Если голова w входит в v, то ее нужно отбросить. т.е. разность списков w=(1 2 3) и v=(6 7 1) не должна содержать 1, верно?

Lisp

1	((cons (car w) (difference (cdr w) v)))))

А иначе голову (которая не входит во второй список) нужно сохранить.

@_sg · 22.12.2021, 09:02

как вариант:

Lisp

(defun -set-difference
    (w v &aux (a (car w)) (d ( cdr w)))
  (when w (if (member a v) (-set-difference d v)
              (cons a (-set-difference d v)))))
 
> (-set-difference '(1 2 3 4 5) '(4 5 6))
(1 2 3)
> (set-difference '(1 2 3 4 5) '(4 5 6))
(1 2 3)

@LSTSnaiper · 22.12.2021, 09:08 **[ТС]**

Понял, спасибо большое вам за объяснение!

@LSTSnaiper 1 / 1 / 1 Регистрация: 18.03.2018 Сообщений: 138
	22.12.2021, 09:08 [ТС]	4
	Понял, спасибо большое вам за объяснение! 0

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

Решение