Homework: Lisp items that appear more than once in a list

Question

Given a list, I'm trying to return a new one that has only the items that appear more than once in the first list I receive as a parameter.

I have done the following:

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

If I run the following: (myf '(A A B A B C)), it returns (A A B). How can I make it return items only once (i.e., not have double "A")?

Answer 1

The problem seems to be that you are checking to see if the first element of the list is in the tail of the list and appending it to the result list. The problem comes up when you come to the second instance of A, which when checked says yes it is in the tail because there is a 3rd instance of A in the list. If the input list had 4 A's then it would return 3 of them.

So to solve this need to check if A is already a member of the result list. That is, if first lista is not a member of list then append first lista to list.

Answer 2

The problem seems to be that you're not checking if the element exists in the output list before appending to it.

Answer 3

Once you've found that a letter is in the list more than once, you don't need to check it again, so you don't need it in the rest of the list. So you could modify the remaining list...

Note: this answer intentionally somewhat vague, since it's for homework and all. :)

Answer 4

Right now, for each element in the list, you're adding that element to the result if its not contained in the remainder of the list.

To get the result you apparently want, you'd add each element in the list to the result if it's not yet contained in the result.

Answer 5

Vincent, Gishu and Jerry hinted that you need to check if the item is already in the result list before appending to it, while Derek hinted that you could modify the original list when you see that an item is repeated.

Read the documentation of the functions adjoin and remove here:

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

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

The HyperSpec is a very useful reference, add it your bookmarks.

Those two functions do not modify their arguments, but instead return the result as a new list. There are other functions that DO modify their arguments and thus might be more efficient, but at this point perhaps you shouldn't worry about them.

OK, I hope that by the time I have written this you have figured it out. If not, keep trying, that's the only way you'll really learn.

Now I'd like to talk to you about another approach, and that is about carrying the result through the recursive calls.

Our function repeated will do nothing but call a helper function repeatedr which will do the actual work, passing to it an initial empty result '():

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

Now let's define the helper function, it receives two parameters: the list to search for duplicates, and the result list where we will accumulate the duplicate items.

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

When the condition (member (first lst) (rest lst)) holds true we will adjoin the first item to the result, and the result of that adjoining will be passed to the recursive call as the second parameter; otherwise we just pass the result as is to the recursive call.

When the list is finally empty (if (null lst) we will return the result.

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

Notice that the result is (B A) and maybe you were expecting it to be (A B). Try to follow the execution of the recursive calls and the values of the parameters at each call with pen and paper, that will be a good exercise, and you'll have to play with adjoin to understand its behaviour. If you want to get the result reversed you can modify the function like this:

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

This reverses the result when the recursion finishes.

Now, what about the suggestion of removing the duplicate elements from the list before going forward? We could have written our function like this:

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

Try to play with remove at the REPL:

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

Notice that we are no longer adjoining to the result, instead we just create a new "cons cell" with (cons (first lst) result). cons and adjoin do the same thing, except that adjoin will add the value only if it is not already present in the list.

Hope this gives you something to play with.