A procedure to extract atoms from a list

[laskin]

Hello. I need to right a recursive procedure that receives a list (could be nested) or an atom as input and returns a new list in which only the atoms of the input data are extracted. Further, if there are repeating atoms only one of them must be listed. It should look something like this:

(extract-atoms (a b (c d) (e f (c d b))))

: (a b c d e f)

I really need that procedure for a model I am trying to program. Any help will be appreciated.

[blandest]

You need to write the "flatten" function (you can search for it, but try to write it yourself).

Code: Select all

(defun extract-atoms (list)
  (sort (remove-duplicates (flatten list))
          #'string<
          :key #'symbol-name))

[laskin]

Thank you for your reply. I am rather new to Lisp, though, and I am not sure I completely understood your advice. Could you tell me a little more about that flatten function? And also, will two procedures be enough for the whole program?

[Exolon]

Could you tell me a little more about that flatten function?

He means:

Code: Select all

(flatten (a b (c d) (e f (c d b)))) -> (a b c d e f c d b)

Then you can remove duplicates from the list (by default, it'll keep the first occurrence I think, and you can specify the direction anyway). I don't see any reason to sort it afterwards though.

[danb]

will two procedures be enough for the whole program?

Yes. All you need to do is flatten the tree and remove all duplicates.

I am rather new to Lisp ... Could you tell me a little more about that flatten function?

How much do you know about recursion and functional programming?
FLATTEN is a great exercise for learning how to write recursive code.
The function needs to (a) examine its argument, (b) possibly call itself one or more times (with different arguments), and (c) each call to the function should return some appropriate value that will help contribute to the final result. As a final hint, remember that, after the function is done analyzing the tree from the top down, it has to finish calling itself at some point, and once it makes its last calls, the flattened list is constructed from the bottom up as the later calls return values to the earlier calls, and the earlier calls process or combine those values to construct the flattened list.

[laskin]

Thank you, your reply was really useful. I think I'm getting the hang of it

[Christopher Oliver]

I'm not so sure I'm happy about seeing flatten as a necessity here. While I recognize a place for programming paradigms (e.g. functional programming), I think we do others a disservice by promoting them in too doctrinaire a fashion. For a tree where there are few unique leaves, the suggested algorithm conses far more than necessary only to have much of the result discarded. Further, remove-duplicates at least in one implementation (SBCL) relies on an imperative data structure to support its operation. Hence you're already living in a state of sin via its use. I think it would be better to explicitly walk the tree recurring on non-atom CARs and CDRs, and use a hash table and list to record unique atoms encountered so far.

[danb]

I'm not so sure I'm happy about seeing flatten as a necessity here.

You're right. The OP was asking if flatten + remove-dups is sufficient, and I meant "all you need to do" in the sloppy colloquial sense of "yes, that's sufficient".

While I recognize a place for programming paradigms (e.g. functional programming), I think we do others a disservice by promoting them in too doctrinaire a fashion.

That's also true, except I don't think it's a problem in the (Common) Lisp community, and the OP's problem happens to be a good application for FP.

For a tree where there are few unique leaves, the suggested algorithm conses far more than necessary only to have much of the result discarded.

Premature optimization is the root of all evil.

Further, remove-duplicates at least in one implementation (SBCL) relies on an imperative data structure to support its operation. Hence you're already living in a state of sin via its use.

All programs that run on real computers in the real, physical world have to iterate at some point. The goal of high-level programming paradigms is to concentrate low-level code in as few places as possible so application programmers don't have to worry about it.

[eric-and-jane-smith]

Code: Select all

(defun atoms (tree)
  (when tree
    (if (atom tree)
        (list tree)
      (nconc (atoms (car tree))
             (atoms (cdr tree))))))

(atoms '(a b (c d) (e f (c d b))))
==> (A B C D E F C D B)

(defun extract-atoms (tree)
  (remove-duplicates
    (atoms tree)))

(extract-atoms '(a b (c d) (e f (c d b))))
==> (A E F C D B)

[gugamilare]

I think it would be better to explicitly walk the tree recurring on non-atom CARs and CDRs, and use a hash table and list to record unique atoms encountered so far.

Using hashtables? I really think that consing one or two cons cells for each atom extracted is way better than creating an entire hashtable - a hashtable will take more memory, and also require more computation, depending on the form of the element. Complicate things to make them slower and less flexible? I don't think so.

Lispers will mostly recomend flatten and remove-duplicates in this case because it is the most intuitive approach. And it uses already well-known functions - which is better than reinventing the wheel.
The version from eric-and-jane-smith is very good in this sense, and just changing

Code: Select all

(defun extract-atoms (tree)
  (delete-duplicates
    (atoms tree)))

would make it non-destructive and it won't create too many unused cons cells. The only cons cells that will be discarded are the ones from the duplicated elements.