Finding duplicate atoms in possibly nested lists in LISP

Question

I am trying to figure out how to find duplicate atom in possibly nested lists. I have been trying to figure this out all day. If you could please give me the logic, that would be great because I really want to learn.

basically

(findDup '(a b b)) would return t

(findDup '(a c ((d (f a)) s))) would also return t

Answer 1

The easiest and most efficient way would be the following (pseudocode):

1. Create a data structure (such as Common Lisp's hash table) to remembering which atoms were seen
2. Create a recursive sub-function that does the actual traversing - walking the nested lists and adding all new atoms to the data structure, and if one is already there, returning true

Answer 2

If the list is empty/without an atomic car however deeply you go (e.g. (car (car (car ...))) recursively), then the answer is false.

You want to find the first atom of the list, and see if that atom occurs anywhere else in the list. You can do that with a function like member-of?—something similar is discussed in The Little Schemer, but basically you just test all the atoms in the list, and recur on lists, against that atom.

Then if that atom is in the list, you can return true.

Else, you'll try again (recur on) with the cdr of the list.

Answer 3

I'd start with a wrapper function that creates a hash table and passes the hash table and the list to a second function (alternatively, use a &optional argument, if you're using Common Lisp).

Then, the following pseudo-code should be enough:

If we're looking at an empty list, there are no duplicates
If the head is a list, we can return the logical OR of "inspect the head" and "inspect the tail"
If the head is an atom, it's a duplicate if it's already in the hash table. If not, add it to the hash table and inspect the tail for duplicates.