A procedure to extract atoms from a list

Discussion of Common Lisp
laskin
Posts: 3
Joined: Fri Jan 23, 2009 3:23 am

A procedure to extract atoms from a list

Post by laskin » Fri Jan 23, 2009 3:26 am

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
Posts: 19
Joined: Mon Jun 30, 2008 1:22 am

Re: A procedure to extract atoms from a list

Post by blandest » Fri Jan 23, 2009 5:41 am

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
Posts: 3
Joined: Fri Jan 23, 2009 3:23 am

Re: A procedure to extract atoms from a list

Post by laskin » Fri Jan 23, 2009 6:04 am

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
Posts: 49
Joined: Sat Jun 28, 2008 12:53 pm
Location: Ireland
Contact:

Re: A procedure to extract atoms from a list

Post by Exolon » Fri Jan 23, 2009 8:51 pm

laskin wrote: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
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US
Contact:

Recursion

Post by danb » Sun Jan 25, 2009 1:48 am

laskin wrote: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
Posts: 3
Joined: Fri Jan 23, 2009 3:23 am

Re: A procedure to extract atoms from a list

Post by laskin » Sun Jan 25, 2009 1:53 pm

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

Christopher Oliver
Posts: 5
Joined: Fri Sep 05, 2008 2:05 pm

Re: A procedure to extract atoms from a list

Post by Christopher Oliver » Sun Feb 01, 2009 7:00 pm

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
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US
Contact:

Re: A procedure to extract atoms from a list

Post by danb » Mon Feb 02, 2009 8:21 am

Christopher Oliver wrote: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. :D
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
Posts: 2
Joined: Fri Feb 20, 2009 5:29 am

Re: A procedure to extract atoms from a list

Post by eric-and-jane-smith » Sat Feb 21, 2009 1:13 am

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
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: A procedure to extract atoms from a list

Post by gugamilare » Sat Mar 07, 2009 9:32 pm

Christopher Oliver wrote: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.

Post Reply