LispForum

Discuss and learn Lisp programming of all dialects

This is a read-only archive of lispforum.com. The forum was locked to new users and posts and is preserved here as static HTML from a database snapshot taken on 2019-09-07.

A procedure to extract atoms from a list

12 posts · 9121 views

laskin
#1
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
#2

Re: A procedure to extract atoms from a list

You need to write the "flatten" function (you can search for it, but try to write it yourself).
(defun extract-atoms (list)
  (sort (remove-duplicates (flatten list))
          #'string<
          :key #'symbol-name))
laskin
#3

Re: A procedure to extract atoms from a list

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
#4

Re: A procedure to extract atoms from a list

laskin wrote:Could you tell me a little more about that flatten function?
He means: 
(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
#5

Recursion

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.
--Dan B.
laskin
#6

Re: A procedure to extract atoms from a list

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

Re: A procedure to extract atoms from a list

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
#8

Re: A procedure to extract atoms from a list

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.
--Dan B.
eric-and-jane-smith
#9

Re: A procedure to extract atoms from a list

(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 Administrator
#10

Re: A procedure to extract atoms from a list

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
(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.
Kohath
#11

Re: A procedure to extract atoms from a list

How about this? Define a function to map over a tree in a way analogous to mapc, say we call it maptree, and then use it with pushnew: 
(let ((result nil))
  (maptree #'(lambda (item)
               (when (atom item)
                 (pushnew item result)))
           your-tree)
  result)
blog.metalight.net
gugamilare Administrator
#12

Re: A procedure to extract atoms from a list

Actually this version seems pretty good. But it seems to be difficult to change if you problem changes a bit (at least to me).
For instance, I've concluded these (both yours and eric-and-jane-smith's) algorithm is O(n^2) in the worst case. If the elements have a total order (e.g. numbers) it is possible to make a O(n log(n)) version when the implementation sort algorithm is O(n logn) (e.g. on SBCL, even for lists):
(defun atoms (tree)
  (when tree
    (if (atom tree)
        (list tree)
      (nconc (atoms (car tree))
             (atoms (cdr tree))))))

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

(defun delete-duplicates-with-order (list order-test &key (test #'eql) key)
  (let ((last-elt (if key
                      (funcall key (first list))
                      (first list))))
    (cons (car list)
          (delete-if (lambda (x)
                       (prog1 (funcall test last-elt x)
                         (setf last-elt x)))
                     (cdr list)
                     :key key))))

;; this extracts atoms and return the sorted list acording to order-test
(defun extract-sort-ordered-atoms (tree order-test &key (test #'eql))
  (let ((atoms (atoms tree)))
    (delete-duplicates-with-order (sort atoms order-test) order-test :test test)))

;; if the actual order should be preserved, we need this complicated, extra-consing version
(defun extract-ordered-atoms (tree order-test &key (test #'eql))
  (let* ((atoms (atoms tree))
         ;; saving the actual position of each atom so it can be restored later
         (atoms-with-position (loop for elt in atoms
                                    for pos from 0
                                    collect (cons elt pos)))
         ;; sorting atoms acording to order-test
         (sorted-atoms (sort atoms-with-position order-test :key #'car))
         ;; deleting duplicates as required by algorithm
         (sorted-atoms-no-dups (delete-duplicates-with-order sorted-atoms order-test :key #'car))
         ;; restore the actual order as returned by atoms
         (atoms-no-dups (sort sorted-atoms-no-dups #'< :key #'cdr)))
    ;; finally, throw away the position of each slot
    (mapcar #'car atoms-no-dups)))
It seems to work: 
CL-USER> (extract-sort-ordered-atoms '(((1 5 2) 3 4) 2 9 7 8 7 4 6 5 (9 0)) #'< :test #'=)

(0 1 2 3 4 5 6 7 8 9)
CL-USER> (extract-ordered-atoms '(((1 5 2) 3 4) 2 9 7 8 7 4 6 5 (9 0)) #'< :test #'=)

(1 5 2 3 4 9 7 8 6 0)
Off course, due to code complexity, the extract-ordered-atoms should be slower for small lists. This must not be the case of extract-sort-ordered-atoms, although I didn't test if this is true.

I don't know how to adapt your version for this case, unless if we change the pushnew with push, which would make it a disguised flatten.