(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.
He means:laskin wrote:Could you tell me a little more about that flatten function?
Code: Select all
(flatten (a b (c d) (e f (c d b)))) -> (a b c d e f c d b)
Yes. All you need to do is flatten the tree and remove all duplicates.laskin wrote:will two procedures be enough for the whole program?
How much do you know about recursion and functional programming?I am rather new to Lisp ... Could you tell me a little more about that flatten function?
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.
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".Christopher Oliver wrote:I'm not so sure I'm happy about seeing flatten as a necessity here.
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.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.
Premature optimization is the root of all evil.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.
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.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.
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)
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.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.
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)))