Домашнее задание: элементы Lisp, которые появляются более одного раза в списке

Question

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

Я сделал следующее:

(defun myf (lista) 
    (if (endp lista) 
     nil 
     (if (member (first lista) (rest lista)) 
      (append (list (first lista)) (myf (rest lista))) 
      (myf (rest lista))))) 

Если я запускаю следующее: (myf '(A A B A B C)), он возвращает (A A B). Как я могу вернуть элементы только один раз (т. Е. Не иметь двойной «А»)?

Answer 1

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

Прочитайте документацию функций adjoin и remove здесь:

http://www.lispworks.com/documentation/HyperSpec/Body/f_adjoin.htm

http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm

HyperSpec является очень полезным справочником, добавьте его в закладках.

Эти две функции не изменяют свои аргументы, но вместо этого возвращают результат как новый список. Существуют и другие функции, которые ДОЛЖНЫ модифицировать свои аргументы и, следовательно, могут быть более эффективными, но на данный момент, возможно, вам не стоит беспокоиться о них.

ОК, я надеюсь, что к тому времени, как я это написал, вы поняли это. Если нет, продолжайте пытаться, это единственный способ, которым вы действительно научитесь.

Теперь я хотел бы поговорить с вами о другом подходе, а именно о переносе результата через рекурсивные вызовы.

Наша функция repeated не будет делать ничего, но назвать вспомогательную функцию repeatedr, которая будет делать реальную работу, передавая ему первоначальный пустой результат '():

(defun repeated (lst) 
    (repeatedr lst '())) 

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

(defun repeatedr (lst result) 
    (if (null lst) 
    result 
    (if (member (first lst) (rest lst)) 
     (repeatedr (rest lst) (adjoin (first lst) result)) 
     (repeatedr (rest lst) result)))) 

Когда условие (member (first lst) (rest lst)) справедливо мы примыкают первый пункт к result, и результат этого прилегания будет передан рекурсивного вызова в качестве второго параметра; в противном случае мы просто передаем result как и для рекурсивного вызова.

Когда список, наконец, пуст (if (null lst), мы вернем result.

> (repeated '(a a b a b c)) 
(B A) 

Обратите внимание, что результат (B A) и, возможно, вы ожидали, что это будет (A B). Постарайтесь выполнить выполнение рекурсивных вызовов и значений параметров при каждом вызове с помощью пера и бумаги, что будет хорошим упражнением, и вам нужно будет сыграть с adjoin, чтобы понять его поведение. Если вы хотите, чтобы получить результат обратных вы можете изменить функцию следующим образом:

(defun repeatedr (lst result) 
    (if (null lst) 
    (reverse result) 
    (if (member (first lst) (rest lst)) 
     (repeatedr (rest lst) (adjoin (first lst) result)) 
     (repeatedr (rest lst) result)))) 

Это обратного сек результата, когда рекуррентные заканчивается.

Теперь, как насчет предположения об удалении повторяющихся элементов из списка перед тем, как идти вперед? Мы могли бы написать нашу функцию так:

(defun repeatedr (lst result) 
    (if (null lst) 
    result 
    (if (member (first lst) (rest lst)) 
     (repeatedr (remove (first lst) lst) (cons (first lst) result)) 
     (repeatedr (rest lst) result)))) 

Попробуйте играть с remove на РЕПЛ:

> (remove 'a '(a b c d a e f b a d)) 
(B C D E F B D) 

Обратите внимание, что мы больше соседствуют не ИНГ к результату, а мы просто создать новый "cons cell" с (cons (first lst) result). cons и adjoin делают то же самое, за исключением того, что adjoin добавит значение только в том случае, если оно еще не присутствует в списке.

Надеюсь, это даст вам возможность поиграть.

Answer 2

Проблема заключается в том, что вы проверяете, находится ли первый элемент списка в хвосте списка и добавляет его в список результатов. Проблема возникает, когда вы приходите ко второму экземпляру A, который, когда проверяется, говорит «да», находится в хвосте, потому что в списке есть третий экземпляр A. Если в списке входных данных было 4 A, тогда оно вернет 3 из них.

Для решения этой проблемы необходимо проверить, является ли A уже членом списка результатов. То есть, если первый список не является членом списка, тогда добавьте первый список в список.

Answer 3

Проблема заключается в том, что вы не проверяете, существует ли элемент в списке вывода перед добавлением к нему.

Answer 4

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

Примечание: этот ответ намеренно несколько расплывчатый, поскольку он предназначен для домашней работы и для всех. :)

Answer 5

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

Чтобы получить результат, который, по-видимому, вам нужен, вы должны добавить каждый элемент в список к результату, если он еще не содержится в результате.

Answer 6

Если заказ не является проблемой, то вы также можете сделать:

(defun my-fun-no-order (lst) 
    (loop for (item . rest) on lst 
    when (= (count item rest) 0) 
    collect item)) 

Здесь мы перебирать список Сплевывание его в текущий элемент итерируемая снова и еще должны быть рассмотрены остальные пункты. Условие when определяет ситуацию, по которой мы собираем элемент.