Append object to list - Question
Dom. Early
Is there a better/more efficient way of appending an object to a list:
eg
(better-append 5 '(1 2 3 4))
> (1 2 3 4 5)
rather than
(append (list 5) '(1 2 3 4))
Thanks,
Dom.
Dom. Early
Early" <Dom....@usa.net> wrote:
Just to make it a bit clearer, is there a function/macro that produces the
same output as
(defun better-append(elt alist)
(append (list elt) alist))
)
but which is a standard function/macro. Also if there is, does it run more
effeciently.
Thanks again,
Dom.
Srinivas Palthepu
> Just to make it a bit clearer, is there a function/macro that produces the
> same output as
>
> (defun better-append(elt alist)
> (append (list elt) alist))
> )
>
> but which is a standard function/macro. Also if there is, does it run more
> effeciently.
>
I am surprised that you know APPEND but do not know CONS, which is
a more basic LISP function. CONS is what you want.
>(CONS 'a '(b c d))
(A B C)
>(CONS 1 '(2 3 4))
(1 2 3 4)
>(CONS 1 (CONS 2 (CONS 3 (CONS 4 NIL))))
(1 2 3 4)
srini
Barry Margolin
>
> >Hi,
> >
> >Is there a better/more efficient way of appending an object to a list:
> >
> >eg
> >
> > (better-append 5 '(1 2 3 4))
> >> (1 2 3 4 5)
> >
> >rather than
> >
> > (append (list 5) '(1 2 3 4))
It's not clear what you want, since the second form doesn't produce the
output of the first form, it produces (5 1 2 3 4). If you want the
specified output, you should use
(append '(1 2 3 4) (list 5))
And the answer to your question is that there isn't anything built-in that
does this any better. However, if you're collecting things into a list,
e.g. you have a loop that's appending something to the end of a list each
time through, you should look at things like MAPCAR and the COLLECTING verb
of LOOP.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Erik Naggum
| Just to make it a bit clearer, is there a function/macro that produces
| the same output as
|
| (defun better-append (elt alist)
| (append (list elt) alist)))
CONS does that. also see PUSH if you want to store the value back into a
variable. (PUSH is a macro, not a function.)
incidentally, an ALIST is a list of cons cells, the car of each being a
key and the cdr the value _associated_ with it. the A in ALIST stands
for Association. LIST is a perfectly valid variable name. (note that
ELT is a function's name, too.)
#:Erik
Srinivas Palthepu
>
| (defun better-append (elt alist)
> | (append (list elt) alist)))
>
> CONS does that. also see PUSH if you want to store the value back into a
> variable. (PUSH is a macro, not a function.)
>
> incidentally, an ALIST is a list of cons cells, the car of each being a
> key and the cdr the value _associated_ with it. the A in ALIST stands
> for Association.
Oh, I thought the use of A in ALIST is as a determiner as in "a list".
I did not think that he wanted an association list.
srini
-----
Srinivas Palthepu, Lucent Technlogies, Inc.
Email: psr...@lucent.com, phone: (630) 979-9154
Donald Fisk
> It's not clear what you want, since the second form doesn't produce the
> output of the first form, it produces (5 1 2 3 4). If you want the
> specified output, you should use
>
> (append '(1 2 3 4) (list 5))
> And the answer to your question is that there isn't anything built-in that
> does this any better.
If destructive assignment isn't a problem, I'd be surprised if(nconc '(1 2 3 4)
(list 5)) isn't faster.
> However, if you're collecting things into a list,
> e.g. you have a loop that's appending something to the end of a list each
> time through, you should look at things like MAPCAR and the COLLECTING verb
> of LOOP.
It's rather hard to infer exactly what's wanted, particularly as the original
posterdoesn't appear to have RTFM'ed about append. It might be possible for
him
to build up the list in reverse order and then use cons, or even just use cons
directly.
I would suggest to Dom....@usa.net that he refers to a introductory Lisp
text and learn exactly what cons, append and nconc do. Then, he should either
be able to solve the problem himself, or if I've really misunderstood him, at
least
post a clearer description of his problem (which I hope isn't homework).
> Barry Margolin, bar...@bbnplanet.com
--
Le Hibou (mo bheachd fhe/in: my own opinion)
"it's just that in C++ and the like, you don't trust _anybody_,
and in CLOS you basically trust everybody. the practical result
is that thieves and bums use C++ and nice people use CLOS."
-- Erik Naggum
Pierre Mai
> Is there a better/more efficient way of appending an object to a list:
>
> eg
>
> (better-append 5 '(1 2 3 4))
> > (1 2 3 4 5)
>
> rather than
>
> (append (list 5) '(1 2 3 4))
In other words you are seeking a data structure, that offers "fast"
(i.e. O(1) with low constant overhead) insertion of single elements at
the end. This suggests a number of specialized data structures, and
only closer inspection of your other requirements will narrow this
down to suitable candidates for your specific problem (i.e. will the
elements be removed again, and how often and in which order? And/Or
do you need compatibility with lists or other sequence types with low
overhead? What other operations will be performed on the data
structure, and what performance/space limits will there be?)
As it is, I can only suggest a number of probable candidates:
a) List-based linear queue, as presented by Paul Graham in ANSI Common
Lisp (recommended reading!):
Insertion at end: O(1)
Insertion/Removal at front: O(1)
Ordered insertion: O(n)
Random Access: O(n)
Coerce to list: O(1)
b) (Adjustable) vector with fill-pointer:
Insertion at end: O(1)
Insertion/Removal at front: O(n)
Ordered insertion: O(n)
Random access: O(1)
Coerce to list: O(n)
Coerce to vector O(1) (identity, but not a simple-vector!)
c) Priority-Queues (diverse implementations, all based on different
trees):
Ordered insertion: O(log n) (depends somewhat on implementation)
Removal at front: O(1)
d) See your favourite advanced data-structures and algorithms hand-book
for further specialized data structures...
If both a) and b) match your specs, you'll probably have to find out
for yourself, what constant factors hide themselves in your
implementation (remember to take into account GC-overhead).
When deciding between a) and c), your estimation of average queue
lengths, distribution of inserted values and comparison costs will
probably be the deciding factor. Often a) is good enough, given the
implementation costs of c). OTOH your short problem description seems
to indicate that you are not interested in ordered insertion...
Sample implementation of a):
;;; Einfache Queues, Quelle Graham96
(defun make-queue ()
"Creates a simple Queue with O(1) addition at end and O(1) removal at front."
(cons nil nil))
(defun enqueue (obj q)
"Inserts `obj' at the end of Queue `q'. Returns the queue contents."
(if (null (car q))
(setf (cdr q) (setf (car q) (list obj)))
(setf (cddr q) (list obj)
(cdr q) (cddr q)))
(car q))
(defun dequeue (q)
"Removes the first element of Queue `q' and returns it."
(pop (car q)))
(defun queue-list (q)
"Returns the queue contents as a list."
(car q))
For b) see ANSI HyperSpec under make-array, vector-push and
vector-push-extend. For c) either implement yourself, or have a look
at the CMU Lisp archive, where there might be implementations...
Regs, Pierre.
--
Pierre Mai <de...@cs.tu-berlin.de> http://home.pages.de/~trillian/
"Such is life." -- Fiona in "Four Weddings and a Funeral" (UK/1994)
David J Cooper Jr
> Hi,
>
> Is there a better/more efficient way of appending an object to a list:
1. When I am building up a list inside some kind of loop (e.g. a property
list), I often use push, then nreverse the final result, a technique used
often by Graham in ANSI Common Lisp:
;;
;; Build up a plist of articulation-state keywords and corresponding
Pitman arm ball stud angles
;;
(let ((result-list nil))
(dolist (angle-computation (list-elements (the
:ball-stud-angle-computations)) (nreverse result-list))
(push (the-object angle-computation :articulation-state)
result-list) ;; the plist key
(push (the-object angle-computation
:pitman-arm-to-drag-link-ball-stud-angles-longitudinal) ;;the plist
value
result-list)))
2. However, nine times out of ten if all you are doing is transforming
one list into another list of the same length, a simple mapcar will fill
the bill.
3. If all you want to do is append a single element to the end of a list,
Graham provides append1 (pg. 105):
(defun append1 (lst obj)
(append lst (list obj)))
But for doing a lot of these kinds of things inside loops or recursions
on long lists, I believe the push and nreverse approach is more
efficient, since a straight append to the end of a list requires walking
down the entire list to arrive at the last cdr cell, each time.
--
David J Cooper Jr Genworks International
dcoo...@genworks.com http://www.genworks.com
...Embracing an Open Systems Approach to Knowledge-based Engineering...
David J Cooper Jr
> (let ((result-list nil))
> (dolist (angle-computation (list-elements (the
>
>
> <snip>
>
Oops, sorry about that mess, I guess I should be using Gnus instead of
Netscape News, which wreaks absolute havoc on like breaks (probably
because I don't know what I'm doing with it, but anyway):
(let ((result-list nil))
(dolist (angle-computation (list-elements (the :angle-computations))
(nreverse result-list))
(push (the-object angle-computation :articulation-state) ;;key
result-list)
(push (the-object angle-computation :computed-angle) ;;value
result-list)))
David Hanley
Dom. Early wrote:
> (better-append 5 '(1 2 3 4))
> > (1 2 3 4 5)
>
> rather than
>
> (append (list 5) '(1 2 3 4))
>
> Thanks,
>
> Dom.
Well, what you have will probably be innefficent. Without rethinking
your algorithm, there's a few things you could do.
1) grit your teeth and use append, resulting in a slow program
2) use a vector with a fill-pointer (using vector-push ) maybe even
coercing to
a list later.
3) build your list backwards with push and reverse it when need be.
4) Use a queue-like structure, with a pointer to head and tail of the
list.
This will give you what you want with o(1) insertions.
dave
Daitaro Hagihara
> Hi,
>
> Is there a better/more efficient way of appending an object to a list:
>
> eg
>
> (better-append 5 '(1 2 3 4))
> > (1 2 3 4 5)
(setf (cdr (last '(1 2 3 4))) (list 5))
Tim Bradshaw
> 1. When I am building up a list inside some kind of loop (e.g. a property
> list), I often use push, then nreverse the final result, a technique used
> often by Graham in ANSI Common Lisp:
I tend to use this thing, that I wrote, but stole I'm sure from
somewhere else (possibly Interlisp?). It probably needs to be
generalised somehow, not to mention cleaned up (all those dollar
signs...), but it's quite useful, especially if you want to collect
things over several loops or something.
(defmacro collecting (&body forms)
;; Collect some random stuff into a list by keeping a tail-pointer
;; to it, return the collected list. No real point in using
;; gensyms, although one probably should on principle.
"Collect things into a list forwards. Within the body of this macro
The form `(COLLECT THING)' will collect THING into the list returned by
COLLECTING. Uses a tail pointer -> efficient."
(let (($resnam$ (gensym)) ($tail$ (gensym)) ($thing$ (gensym)))
`(let
(,$resnam$ ,$tail$)
(macrolet
((collect
(thing)
;; Collect returns the thing it's collecting
`(let ((,',$thing$ ,thing))
(if ,',$resnam$
(setf (cdr ,',$tail$)
(setf ,',$tail$ (list ,',$thing$)))
(setf ,',$resnam$
(setf ,',$tail$ (list ,',$thing$))))
,',$thing$)))
,@forms)
,$resnam$)))
--tim
Raffael Cavallaro
>Is there a better/more efficient way of appending an object to a list:
>
>eg
>
> (better-append 5 '(1 2 3 4))
>> (1 2 3 4 5)
>
>rather than
>
> (append (list 5) '(1 2 3 4))
>
>Thanks,
>
> Dom.
First, I hope you mean
(better-append 5 '(1 2 3 4)
>(5 1 2 3 4)
since #'(append) puts its first arg in *front* of its second arg and so on.
That is, in common lisp, (append (list 5) '(1 2 3 4))
returns:
>(5 1 2 3 4)
That said, this works:
------------------------------
(defun better-append (&rest atoms-n-lists)
"returns a new list composed of atoms-n-lists appended into a single list."
(do ((i 0 (1+ i)))
((= i (length atoms-n-lists)) (apply #'append atoms-n-lists))
(if (atom (nth i atoms-n-lists))
(setf (nth i atoms-n-lists) (list (nth i atoms-n-lists))))))
------------------------------
If you really want it the other way around:
------------------------------
(defun better-reverse-append (&rest atoms-n-lists)
"returns a new list composed of atoms-n-lists appended into a single
list, first arg last, last arg first."
(do ((i 0 (1+ i)))
((= i (length atoms-n-lists)) (apply #'append (reverse atoms-n-lists)))
(if (atom (nth i atoms-n-lists))
(setf (nth i atoms-n-lists) (list (nth i atoms-n-lists))))))
------------------------------
Raf
--
Raffael Cavallaro
Raffael Cavallaro
raf...@mediaone.net (Raffael Cavallaro) wrote:
>------------------------------
>(defun better-append (&rest atoms-n-lists)
> "returns a new list composed of atoms-n-lists appended into a single list."
> (do ((i 0 (1+ i)))
> ((= i (length atoms-n-lists)) (apply #'append atoms-n-lists))
> (if (atom (nth i atoms-n-lists))
^^^^^^^
Actually, when would be better here.
Raffael Cavallaro
(defun better-append (&rest atoms-n-lists)
"returns a new list composed of atoms-n-lists appended into a single list."
(apply #'append (mapcar #'(lambda (x) (if (atom x) (setf x (list x)) x))
atoms-n-lists)))
? (better-append 1 2 3 '(4) '(5 6) 7)
(1 2 3 4 5 6 7)
Raf
--
Raffael Cavallaro
Kent M Pitman
This is a commonly suggested approach, but I don't recommend it.
Lists are not just containers wanting to go away. In real situations,
beyond simple toy examples like this, indiscriminate mixes of things
in containers with things not in containers are quite rare in my
experience. Further, lists used properly are not something to fear.
Consequently, if you want to make a list that contains a list, how
can you do that if your function just randomly flattens other lists.
By the way, you still want to use REDUCE, not APPLY, in this situation
since you don't know how many list elements there are and it could easily
exceed CALL-ARGUMENTS-LIMIT. APPLY should mainly only be used when
you have reason to be able to bound the number of args to some
rational number that doesn't exceed CALL-ARGUMENTS-LIMIT.
Also, as a rule, (lambda (x) (if (atom x) (setf x (list x)) x))
doesn't do anything different than
(lambda (x) (if (atom x) (list x) x))
The setf isn't doing anything in your example because the value of
x is never used after the assignment; only the return value of the setf
is used, and so you might as well not assign x.
Incidentally, on a related matter, some people may not
know about or understand LIST* but it's very useful in cases like
this where you want to add several items to the front of a list.
(cons 'a '(b c d)) => (a b c d)
(list* 'a '(b c d)) => (a b c d) ;same as cons in 2-arg case
(cons 'a (cons 'b (cons 'c '(d)))) => (a b c d)
(list* 'a 'b 'c '(d)) => (a b c d)
Note that in the case of a list,
(list* 1 2 3 '(4) '(5 6) '(7 8 9))
(1 2 3 (4) (5 6) 7 8 9)
That is, all of the first n-1 arguments to list* just become
initial elements of a new list that ends with the elements
in the nth arg. When looking at naive examples like this, that
may not seem useful, but in practical situations it's very useful.
For example, when consing up a property list one might do
(list* new-indicator new-value old-indicators-and-values)
to add both an indicator and value to the front of a list,
even if the value might be, as often happens, a list.
David D. Smith
<pit...@world.std.com> wrote:
> raf...@mediaone.net (Raffael Cavallaro) writes:
>
> > This is more lisp-like, and faster too.
> >
> > (defun better-append (&rest atoms-n-lists)
> > "returns a new list composed of atoms-n-lists appended into a single
list."
> > (apply #'append (mapcar #'(lambda (x) (if (atom x) (setf x (list x)) x))
> > atoms-n-lists)))
> >
> > ? (better-append 1 2 3 '(4) '(5 6) 7)
> > (1 2 3 4 5 6 7)
>
> This is a commonly suggested approach, but I don't recommend it.
Assuming one does want to do this, this is a better approach (I treated
NIL differently though):
(defun better-append (&rest atoms-n-lists)
"returns a new list composed of atoms-n-lists appended into a single list."
(mapcon #'(lambda (y)
(let ((x (car y)))
;; We will treat NIL as the empty list rather than an ATOM
(if (consp x)
;; Don't copy a final element list
(if (cdr y) (copy-list x) x)
(list x))))
atoms-n-lists))
(better-append 1 2 3 '(4) '(5 6) 7) => (1 2 3 4 5 6 7)
>
> By the way, you still want to use REDUCE, not APPLY, in this situation
> since you don't know how many list elements there are and it could easily
> exceed CALL-ARGUMENTS-LIMIT. APPLY should mainly only be used when
> you have reason to be able to bound the number of args to some
> rational number that doesn't exceed CALL-ARGUMENTS-LIMIT.
The argument to APPLY in the original example passed one arg in addition
to the arguments to BETTER-APPEND, so it is reasonable to assume that
CALL-ARGUMENTS-LIMIT isn't a problem
d
David D. Smith
D. Smith) wrote:
I think I messed that up. Should be:
(defun better-append (&rest atoms-n-lists)
"returns a new list composed of atoms-n-lists appended into a single list."
(mapcon #'(lambda (y)
(let ((x (car y)))
;; We will treat NIL as the empty list rather than an ATOM
(if (LISTP x)
;; Don't copy a final element list
(if (cdr y) (copy-list x) x)
(list x))))
atoms-n-lists))
or
(defun better-append (&rest atoms-n-lists)
"returns a new list composed of atoms-n-lists appended into a single list."
(mapcon #'(lambda (y)
(let ((x (car y)))
;; We will treat NIL as the empty list rather than an ATOM
(and x
(if (consp x)
;; Don't copy a final element list
(if (cdr y) (copy-list x) x)
(list x)))))
atoms-n-lists))
d
raf...@my-dejanews.com
> This is a commonly suggested approach, but I don't recommend it.
>
> Lists are not just containers wanting to go away. In real situations,
> beyond simple toy examples like this, indiscriminate mixes of things
> in containers with things not in containers are quite rare in my
> experience. Further, lists used properly are not something to fear.
> Consequently, if you want to make a list that contains a list, how
> can you do that if your function just randomly flattens other lists.
Actually, I didn't want to do this at all. The original poster was looking
for a way to flatten lists and atoms into a single list which he referred to
as a "better append." The function is probably better named #'flatten-to-list
or something like that.
Thanks for pointing out the useless setf - it was left over from an earlier
iterative version of the function which did use the side effect.
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
raf...@my-dejanews.com
> This is a commonly suggested approach, but I don't recommend it.
>
> Lists are not just containers wanting to go away. In real situations,
> beyond simple toy examples like this, indiscriminate mixes of things
> in containers with things not in containers are quite rare in my
> experience. Further, lists used properly are not something to fear.
> Consequently, if you want to make a list that contains a list, how
> can you do that if your function just randomly flattens other lists.
Actually, I didn't want to do this at all. The original poster was looking
for a way to flatten lists and atoms into a single list which he referred to
as a "better append." The function is probably better named #'flatten-to-list
or something like that.
Thanks for pointing out the useless setf - it was left over from an earlier
iterative version of the function which did use the side effect.
Raf
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own