There has got to be a better way... 
Author Message
 There has got to be a better way...

As part of another project I had need of a function to collapse a
possibly nested list into an unnested version containing the same atoms.
After finishing my first hack at it I thought, "There has got to be a
better way".  I was hoping some of you Lisp experts (I'm mediocre in
this language, at best) would be able to help me out.  I am not
particularly concerned with performance.  I would like to see a simple
and elegant solution.

(defun collapse-list (l)
  "This function takes a list with that potentially contains nested
  elements and returns a list that contains all of the atoms contained
  in the original (and in the same quantities), but no nested lists.
  The atoms will be in their printing order in the returned list."
  (let ((result))
       (do ((temp_list (reverse l) (rest temp_list)))
           ((eq temp_list nil) result)
           (if (atom (first temp_list))
               (setf result (cons (first temp_list) result))
               (setf result
                     (append (collapse-list (first temp_list))
                             result)))))

--

  The world is full of fools and faint hearts; and yet everyone has
  courage enough to bear the misfortunes, and wisdom enough to manage
  the affairs, of his neighbor.  -- Benjamin Franklin



Wed, 10 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:
> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution.

> (defun collapse-list (l)
>   "This function takes a list with that potentially contains nested
>   elements and returns a list that contains all of the atoms contained
>   in the original (and in the same quantities), but no nested lists.
>   The atoms will be in their printing order in the returned list."
>   (let ((result))
>        (do ((temp_list (reverse l) (rest temp_list)))
>            ((eq temp_list nil) result)
>            (if (atom (first temp_list))
>                (setf result (cons (first temp_list) result))
>                (setf result
>                      (append (collapse-list (first temp_list))
>                              result)))))

The problem with this solution is that the recursive call to collapse-list
conses a result value which you then have to copy (for the append) in
order to add to the list.  I don't have time to write it, but the
conventional way of avoiding this is to pass a seed list.  Something like:
 (defun collapse-list (l)
   (labels ((collapse (l seed)
              ... your main function ..
           ))
      (collapse l '())))
where you find (append (collapse ...) result)
and replace it with something of the general shape
  (collapse (car l) (collapse  (cdr l) seed)))
or something like that.  That's tree recursion.  You might need
list recursion and that's slightly different.  But the point is you
have to carry the result stack with you if you want to avoid the copy.
Dunno if that'll help.  Gotta run.  Early meeting.  (Yes, on a Saturday.)


Wed, 10 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:
> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution.

I wouldn't actually write it like this.

(defun collapse-tree (tree)
  (labels ((walk (tr acc)
             (typecase tr
               (cons (walk (car tr)
                           (walk (cdr tr) acc)))
                 (null acc)
                 (t (cons tr acc)))))
    (walk tree '())))

--tim



Wed, 10 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:


> (By the way, I think your post contained tab characters which screwed
> up indentation somewhat for me.)

Probably, emacs does deep weirdness with tabs and untabifying and
stuff.

Quote:
> While I can't see a more elegant solution, I wonder if it would
> be clearer to use explicit collecting (by means of WITH-COLLECTOR^1)
> and left-to-right traversal (instead of right-to-left traversal
> with the accumulator serving as an implicit collector).

I might use that in real life.  I'd certainly try to use something
that didn't eat stack recursing on the CDRs which mine does.  And it
was a question about lists not trees so I wasn't really answering it.

But I wouldn't use a collecting macro if I was teaching this (and this
looks like some kind of semi-homework question).  The reason I
wouldn't is that, I think, it is hard enough for students to
understand how lists work, in particular what is fast and slow,
without burdening them with clever tricks like keeping tail pointers,
let alone hiding it behind nice syntax.  The danger is that they fail
to realise that lists are not arrays.

--tim



Thu, 11 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:




> (...)
> > > a function to collapse a
> > > possibly nested list into an unnested version containing the same atoms.
> (...)
> > > I am not
> > > particularly concerned with performance.  I would like to see a simple
> > > and elegant solution.
> (...)
> > (defun collapse-tree (tree)
> >   (labels ((walk (tr acc)
> >              (typecase tr
> >                (cons (walk (car tr)
> >                            (walk (cdr tr) acc)))
> >                (null acc)
> >                (t (cons tr acc)))))
> >     (walk tree '())))

> (By the way, I think your post contained tab characters which screwed
> up indentation somewhat for me.)

> While I can't see a more elegant solution, I wonder if it would
> be clearer to use explicit collecting (by means of WITH-COLLECTOR^1)
> and left-to-right traversal (instead of right-to-left traversal
> with the accumulator serving as an implicit collector).

I think there may be a slightly more elegant method,

(defun collapse-list (list)
    (if (null list)
        nil
        (if (consp (car list))
            (append (collapse-list (car list))
                (collapse-list (cdr list)))
            (if (atom (car list))
                (cons (car list) (collapse-list (cdr list)))))))

I think this can be made more elegant, using a case/typecase structure, but this
gives a fairly clear idea of how it works, all you do is check if you are at the
end of a list, if so, return nil, if not, check the car of the list, if this is
an atom, return it, it it is a list, collapse that list, and append the
collapsed cdr to it.   This works, as the only things the car of a list can be
are nil, an atom, or a list.

I hope this is of use

Chris Croft-White



Thu, 11 Oct 2001 03:00:00 GMT  
 There has got to be a better way...
...

Quote:

> I think there may be a slightly more elegant method,

> (defun collapse-list (list)
>     (if (null list)
>         nil
>         (if (consp (car list))
>             (append (collapse-list (car list))
>                 (collapse-list (cdr list)))
>             (if (atom (car list))
>                 (cons (car list) (collapse-list (cdr list)))))))

  Errr, you've missed the duality of NIL.   It is both a list and an atom!!!

 USER(15): (collapse-list '(a ( b c d)  ( () e)   f ))
(A B C D NIL E F)

  Additionally, you can do without the the extra predicate ( If something is
  not nil and not  a cons then it is by definition an atom. There's no way to
  take the implicit "else" of that last if.  )

   (defun collapse-list ( list )
     (if (null  list )
          nil
         (if (listp (car list ))
             (append (collapse-list (car list))
                     (collapse-list (cdr list)))
             ;;else (car list) is a  non-nil atom
             (cons (car list ) (collapse-list (cdr list))))))

   or if you'd like to avoid the "right drift" of that code....

(defun collapse-list ( list )
  (cond ((null list ) nil )
        ((listp (car list))
           (append (collapse-list ( car list)) (collapse-list (cdr list))))
        (t  ; (car list ) must be non-nil atom
           (cons (car list) (collapse-list (cdr list))))))

 Since the predicates are used to determine three different cases, a cond
 works.  I suspect the cond macro will expand into the equivalent of
 the original nested if, including the "extra" if.  It doesn't have the
 "extra" predicate though.  Ditto with typcase... it will likely expand into
 cond and that into a series of nested ifs.

 I've usually seen this function in most textbooks under the name "flatten".

 The "seed" method works  right-to-left over the tree which avoids the
 the garbage producing effect embedding an APPEND in a recursive process
 entails.    You could replace that with NONC and you'd get rid of the
 garbage problem.  [ There is still some "rewalking" of the subtree.
 However, avoiding that means staying at the end of original and the
 accumlated result.... which will require a macro to hide the mess. ]

--

Lyman



Thu, 11 Oct 2001 03:00:00 GMT  
 There has got to be a better way...
...

Quote:

> I might use that in real life.  I'd certainly try to use something
> that didn't eat stack recursing on the CDRs which mine does.  And it
> was a question about lists not trees so I wasn't really answering it.

  But nested lists are trees. :-)   At least you can look at them that
  way in this context, removing the nesting.

   (  ( a  b )  ( c d ) )

                    -----
                    |*|*|
                    -----
                    /   \
                   /     \
              -----      -----
              |*|*|      |*|\|
              -----      -----
              /  |        |
             a   |        |
                -----    -----
                |*|\|    |*|*|
                -----    -----
                /        /   \
               b        c    -----
                             |*|\|
                             -----
                             /
                            d

  While usually presented in a more horizontal fashion, the above is
  more conducive to illustrating the "treeness".

  I'm not sure how you do this without a stack. You can explicitly
  manage your own or by recursion implicitly use the funcall call stack.
  Once you go "down" one side of this "tree" how do you know how to get
  to the "other" branch? That has to be "recorded" somewhere... it might as
  well be the call stack.

Quote:
> ......  The danger is that they fail
> to realise that lists are not arrays.

   From experience this is a common way for newbies to deal with lists
   in right to left fashion.

--

Lyman



Thu, 11 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:

> ...

> > I might use that in real life.  I'd certainly try to use something
> > that didn't eat stack recursing on the CDRs which mine does.  And it
> > was a question about lists not trees so I wasn't really answering it.

>   But nested lists are trees. :-)   At least you can look at them that
>   way in this context, removing the nesting.

>    (  ( a  b )  ( c d ) )

>                     -----
>                     |*|*|
>                     -----
>                     /   \
>                    /     \
>               -----      -----
>               |*|*|      |*|\|
>               -----      -----
>               /  |        |
>              a   |        |
>                 -----    -----
>                 |*|\|    |*|*|
>                 -----    -----
>                 /        /   \
>                b        c    -----
>                              |*|\|
>                              -----
>                              /
>                             d

There is a "standard bug" in algorithms that try to do tree-recursion
on lists, and that comes with the ambiguity of recognizing NIL.

This code, contributed by someone (Tim?) has that bug:

Quote:
> (defun collapse-tree (tree)
>   (labels ((walk (tr acc)
>              (typecase tr
>                (cons (walk (car tr)
>                            (walk (cdr tr) acc)))
>                (null acc)
>                (t (cons tr acc)))))
>     (walk tree '())))

(collapse-tree '((a b) (c d (e f nil g nil) h i) j))

loses the NILs.



Fri, 12 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:
>   Errr, you've missed the duality of NIL.   It is both a list and an atom!!!

Oops. I just sent this same message.


Fri, 12 Oct 2001 03:00:00 GMT  
 There has got to be a better way...


< As part of another project I had need of a function to collapse a
< possibly nested list into an unnested version containing the same
< atoms.

You can use an accumulator instead of append; makes the code smaller.
This is from Norvigs AIP book.

(defun flatten (l)
  (flatten2 l ()))

(defun flatten2 (l accumulator)
  (cond ((null l) accumulator)
        ((atom l) (cons l accumulator))
        (t (flatten2 (car l)
                     (flatten2 (cdr l) accumulator)))))

You can use an optional parameter or a local function as well.

(defun flatten (l &optional accumulator)
  (cond ((null l) accumulator)
        ((consp l)
         (flatten (car l)
                  (flatten (cdr l) accumulator)))
       (t (cons l accumulator))))

I saw a version that uses pointers in cl-http, maybe it's worth
checking out...



Fri, 12 Oct 2001 03:00:00 GMT  
 There has got to be a better way...
This is my vote:

CL-USER 51 >
(defun collapse-list (l)
  (loop for x in l nconc
        (if (atom x)
            (list x)
          (collapse-list x))))
COLLAPSE-LIST

CL-USER 52 > (collapse-list +)
(DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST
X)

CL-USER 53 >


Quote:
> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution.

> (defun collapse-list (l)
>   "This function takes a list with that potentially contains nested
>   elements and returns a list that contains all of the atoms contained
>   in the original (and in the same quantities), but no nested lists.
>   The atoms will be in their printing order in the returned list."
>   (let ((result))
>        (do ((temp_list (reverse l) (rest temp_list)))
>            ((eq temp_list nil) result)
>            (if (atom (first temp_list))
>                (setf result (cons (first temp_list) result))
>                (setf result
>                      (append (collapse-list (first temp_list))
>                              result)))))



Fri, 12 Oct 2001 03:00:00 GMT  
 There has got to be a better way...
This is my vote:

CL-USER 51 >
(defun collapse-list (l)
  (loop for x in l nconc
        (if (atom x)
            (list x)
          (collapse-list x))))
COLLAPSE-LIST

CL-USER 52 > (collapse-list +)
(DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST
X)

CL-USER 53 >


Quote:
> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution.

> (defun collapse-list (l)
>   "This function takes a list with that potentially contains nested
>   elements and returns a list that contains all of the atoms contained
>   in the original (and in the same quantities), but no nested lists.
>   The atoms will be in their printing order in the returned list."
>   (let ((result))
>        (do ((temp_list (reverse l) (rest temp_list)))
>            ((eq temp_list nil) result)
>            (if (atom (first temp_list))
>                (setf result (cons (first temp_list) result))
>                (setf result
>                      (append (collapse-list (first temp_list))
>                              result)))))



Fri, 12 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:

> This is my vote:

> CL-USER 51 >
> (defun collapse-list (l)
>   (loop for x in l nconc
>         (if (atom x)
>             (list x)
>           (collapse-list x))))
> COLLAPSE-LIST

> CL-USER 52 > (collapse-list +)
> (DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST
> X)

Uh, just to be clear, Nick's code is fine but, cute as it is for
example purposes, programmers are ill-advised to do anything like his
example in production code.  Doing a destructive side-effect on
anything you've given to EVAL or COMPILE other than a quoted literal
could have undefined consequences.  For example, if the system had
kept a pointer to that very code to execute interpreted, it could find
its own datastructure falling apart as it executed.


Fri, 12 Oct 2001 03:00:00 GMT  
 There has got to be a better way...

Quote:

> Uh, just to be clear, Nick's code is fine but, cute as it is for
> example purposes, programmers are ill-advised to do anything like his
> example in production code.

Hang about! This code only destructively-modifies conses it has built itself. (Or
is Nick even deeper asleep than usual this morning? What did I miss?)

CL-USER 52 > (COLLAPSE-LIST +)
(DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST X)

CL-USER 53 > ++
(DEFUN COLLAPSE-LIST (L) (LOOP FOR X IN L NCONC (IF (ATOM X) (LIST X)
(COLLAPSE-LIST X))))

CL-USER 54 >

Quote:
> Doing a destructive side-effect on
> anything you've given to EVAL or COMPILE other than a quoted literal
> could have undefined consequences.  For example, if the system had
> kept a pointer to that very code to execute interpreted, it could find
> its own datastructure falling apart as it executed.

  Oh, absolutely. I didn't think I had.

- nick



Fri, 12 Oct 2001 03:00:00 GMT  
 
 [ 73 post ]  Go to page: [1] [2] [3] [4] [5]

 Relevant Pages 

1. Having it both ways: BYTES and AU's

2. Having It Both Ways

3. Help I am having an Internal error:tpsbt.cpp line 1477

4. I am having touble logging alarm status in labview

5. I am having problems setting the page break through Active X

6. I am having trouble reading a time stamp on a video using OCR

7. I am having a problem configuring my DAQ to generate continous waveforms

8. I am having array problems in MS FORTRAN ver 3.31

9. I am having compiler problems with MS FORTRAN 3.31

10. Best Place to trap all ways out of a window

11. Which ways better??

12. best ways to flush?

 

 
Powered by phpBB® Forum Software