thus spoke ············@gmail.com:
> CL has find, position, remove, subsitute, and others. Why no insert
> (at least for list) ?
Sure it has. See PUSH and tail-consing. Note that PUSH doesn't modify
the original list, if it's passed as an argument, the change won't
propagate by itself into the calling function.
--
Nawet świnka wejdzie na drzewo kiedy ją chwalą.
Stanisław Halik <··············@tehran.lain.pl> writes:
> thus spoke ············@gmail.com:
>
>> CL has find, position, remove, subsitute, and others. Why no insert
>> (at least for list) ?
>
> Sure it has. See PUSH and tail-consing. Note that PUSH doesn't modify
> the original list,
Not always true. PUSH modifies the place you give it. If this places
is a cell in the list, PUSH will modify that list. See my other answer.
> if it's passed as an argument, the change won't
> propagate by itself into the calling function.
--
__Pascal Bourguignon__
············@gmail.com writes:
> CL has find, position, remove, subsitute, and others. Why no insert
> (at least for list) ?
Basically, because there is no list in lisp.
See the lisp paradoxes in: http://www.informatimago.com/usenet.html
Otherwise, insert could (very) naively be implemented as:
(defun insert (value index list)
(push value (nthcdr index list)))
so the reason why there is no INSERT is the same as why there is no
(SETF NTHCDR). See:
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/e97408eed2a8d7d9/576860b23df03370?lnk=st&q=
Namely: (insert 'head 0 list) cannot be defined.
(let ((list (list 'neck 'body 'leg)))
(let ((a list)
(b list))
(insert 'head 0 list)
;; what would you get from:
(print a)
(print b)
(print list)
;; ?
(values)))
Ok, so you could define an insert similar to delete:
(defun insert (value index sequence)
(etypecase sequence
(null (list value))
(list (if (zerop index)
(cons value sequence)
(progn (push value (cdr (nthcdr (1- index) sequence)))
sequence)))
(vector '\...)))
C/USER[32]> (let ((list (list 1 2 3 4 5 6 7)))
(setf list (insert pi 3 list))
(print list)
(setf list (insert -1 0 list))
(print list)
(values))
(1 2 3 3.1415926535897932385L0 4 5 6 7)
(-1 1 2 3 3.1415926535897932385L0 4 5 6 7)
But this is about as far as you can go, without a true list ADT.
If you really need to insert elements inside a list, then you should
define a list data type to let you do so easily, efficiently, and
meaningfully. Definitely with identity, perhaps with double-links, etc.
--
__Pascal Bourguignon__
> Basically, because there is no list in lisp.
> See the lisp paradoxes in:http://www.informatimago.com/usenet.html
There is no list *but* you may use 'list with the typep function ?
Hum ... I'll have follow the white^^link and better understand your
meaning ;)
> so the reason why there is no INSERT is the same as why there is no
> (SETF NTHCDR). See:http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/e9...
Ok, I'll investigate on this to understand the issues.
> Ok, so you could define an insert similar to delete:
> [...]
Well, I know it's not that hard to define the functions I need by
myself, but I was wondering why the standard lacks them. I'll follow
the links and read them twice.
Thanks.
-Nicolas
<············@gmail.com> wrote:
+---------------
| ···@informatimago.com (Pascal J. Bourguignon) wrote:
| > Basically, because there is no list in lisp.
| > See the lisp paradoxes in:http://www.informatimago.com/usenet.html
|
| There is no list *but* you may use 'list with the typep function ?
| Hum ... I'll have follow the white^^link and better understand your
| meaning ;)
+---------------
TYPEP is a red herring here (or at least probably a source of
considerable confustion for you). The important thing Pascal is
trying to tell you is that there is no "list" *object* type in Lisp!!
The "type" LIST is *NOT* the type of any object -- "object" as in
"object identity" -- but is a union type of two *other* types,
CONS & NULL (whose sole member is the object NIL). If someone
passes you a "list" in a function call, all you can see inside
your function is that they passed you either NIL or a CONS. Since
NIL is an immutable literal constant [w.r.t. RPLACA/RPLACD], you
cannot mutate it, thus you cannot "insert" into it. [Said another
way, NIL is not a SETF-able "place".] Thus in this case you *CANNOT*
return the same LIST-type object that was passed to you with a
new element "inserted" into it. End of story. QED.
-Rob
p.s. Note that by using a considerable amount of imperative mutation,
you *can* return the "same" LIST-type object with a new element "inserted"
into it IF the LIST-type object is a CONS, even if you're inserting
into the front of the list. What you have to do is create a *new*
CONS cell, copy the contents of the existing CONS into it, then
RPLACA the new contents into the original CONS and also RPLACD the
original CONS with the newly-alocated one:
> (defun push/inplace (obj place)
(cond
((consp place)
(let ((new-cons (cons (car place) (cdr place))))
(setf (car place) obj)
(setf (cdr place) new-cons)
place))
(t (error "PLACE arg must be a CONS, wasn't: ~s" place))))
PUSH/INPLACE
>
Now compare this:
> (let* ((x (list 1 2 3))
(y ((lambda (z)
(push 4 z))
x)))
(list x y (eq x y)))
((1 2 3) (4 1 2 3) NIL)
>
with this:
> (let* ((x (list 1 2 3))
(y ((lambda (z)
(push/inplace 4 z))
x)))
(list x y (eq x y)))
((4 1 2 3) (4 1 2 3) T)
>
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> p.s. Note that by using a considerable amount of imperative mutation,
> you *can* return the "same" LIST-type object with a new element "inserted"
> into it IF the LIST-type object is a CONS, even if you're inserting
> into the front of the list. What you have to do is create a *new*
> CONS cell, copy the contents of the existing CONS into it, then
> RPLACA the new contents into the original CONS and also RPLACD the
> original CONS with the newly-alocated one:
Yes. This other can of worm allows us to mention that in addition,
there is a strong tradition of structure sharing in lisp (which is
possible to do efficiently by the very fact that there is no list data
type), and that applying destructive operations like this doesn't mesh
well with that tradition.
(let ((l1 (list 'c 'b 'a)))
(let ((l1 l1)
(l2 l1))
(push 'd1 l1)
(format t "l1' = ~S~%l2 = ~S~%" l1 l2)
(push/inplace 'd2 l2)
(format t "l1' = ~S~%l2 = ~S~%" l1 l2))
(format t "l1 = ~S~%" l1)
(values))
l1' = (D1 C B A)
l2 = (C B A)
l1' = (D1 D2 C B A)
l2 = (D2 C B A)
l1 = (D2 C B A)
is not often what you want to get.
--
__Pascal Bourguignon__ http://www.informatimago.com/
READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the Grand Unified Theory, the primary particles
constituting this product may decay to nothingness within the next
four hundred million years.
Pascal Bourguignon <···@informatimago.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > p.s. Note that by using a considerable amount of imperative mutation,
| > you *can* return the "same" LIST-type object with a new element
| > "inserted" into it IF the LIST-type object is a CONS ...
| > RPLACA the new contents into the original CONS and also
| > RPLACD the original CONS with the newly-alocated one:
|
| Yes. This other can of worm allows us to mention that in addition,
| there is a strong tradition of structure sharing in lisp (which is
| possible to do efficiently by the very fact that there is no list data
| type), and that applying destructive operations like this doesn't mesh
| well with that tradition.
+---------------
I completely agree -- it breaks the functional model completely --
and I was not *recommending* it per se, just pointing out that if one
really wanted to one *can* do it while maintaining object identity
with the first CONS.
Anyway, the bigger point was that one *CAN'T* do that if the initial
list arg is NIL, since NIL (considered as a value, not a symbol) is
immutable. So if one really wants a list-type "object" that one can
insert into anywhere and/or empty out completely while maintaining
object identity, it would really be better to create a wrapper object
for the object identity part of it, e.g.:
> (defstruct list-obj head)
LIST-OBJ
> (make-list-obj :head (list 3 2 1))
#S(LIST-OBJ :HEAD (3 2 1))
> (push 4 (list-obj-head *))
(4 3 2 1)
> **
#S(LIST-OBJ :HEAD (4 3 2 1))
>
This will maintain object identity even when "empty", which normal
CL lists won't:
> (eq (list) (list))
T
> (eq (make-list-obj :head nil) (make-list-obj :head nil))
NIL
>
Plus, it lets one add hooks for better performance if some of
the operations are more frequent than others, e.g., add a TAIL
slot, allowing appending to the end in O(1) time. And so forth...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607