Hello
The following I've get from HS (section for NCONC).
Could you explain me second and last line of it ?
I knew what period (.) means by itself (notation for cons)
but not in such context.
(nconc) => ()
(nconc nil . lists) == (nconc . lists)
(nconc list) => list
(nconc list-1 list-2) == (progn (rplacd (last list-1) list-2) list-1)
(nconc list-1 list-2 . lists) == (nconc (nconc list-1 list-2) . lists)
What is the conventional way adding items to end of the
list starting from the empty list ?
I can think about such versions:
(defun append-1 (list)
(let ((result '()))
(loop for i in list
do (push i result)
finally (return (nreverse result)))))
;; Please note that my aim isn't (loop for i in list collecting i).
;; I'm using LOOP just for illustration.
(defun append-2 (list)
(let ((result '()))
(loop for i in list
if result do (nconc result (list i))
else do (setf result (list i)))
result))
;; Why NCONC didn't work on NIL ?
Also please see the following versions of SPLIT function:
;; #1
(defun split-1 (string &optional (separator #\Space))
(let ((in-word nil)
(result '())
(start 0)
(end (length string)))
(do ((i 0 (1+ i)))
((>= i end) result)
(let ((c (char string i)))
(cond ((and (not in-word) (not (eql c separator)))
(setf start i)
(setf in-word t))
((and in-word (eql c separator))
(setf in-word nil)
;; What is the conventional method of appending items
;; at the end of the list ?
(if result
(nconc result (list (subseq string start i)))
(setf result (list (subseq string start i))))))))))
;; # 2
(defun split-2 (string &optional (separator #\Space))
(let (in-word c (start 0))
(loop for i from 0 below (length string)
do (setf c (char string i))
if (and (not in-word) (not (eql c separator)))
do (setf start i) (setf in-word t)
if (and in-word (eql c separator))
do (setf in-word nil)
and collecting (subseq string start i))))
;; #3
(defun split-3 (string &optional (separator #\Space))
(let ((start 0) end)
(when (setf start (position-if #'(lambda (c) (not (eql c
separator))) string))
(if (setf end (position separator string :start (1+ start)))
(cons (subseq string start end) (split-3 (subseq string (1+ end))))
(subseq string start)))))
As I can see each thing can be expressed in Lisp in many ways.
I haven't much experience in programming on Lisp and sometimes
it is difficult to decide what way should be used. How you
(experienced Lispers) would write such function ?
--
Vladimir Zolotych ······@eurocom.od.ua
"Vladimir V. Zolotych" <······@eurocom.od.ua> writes:
> The following I've get from HS (section for NCONC).
> Could you explain me second and last line of it ?
> I knew what period (.) means by itself (notation for cons)
> but not in such context.
>
> (nconc) => ()
> (nconc nil . lists) == (nconc . lists)
> (nconc list) => list
> (nconc list-1 list-2) == (progn (rplacd (last list-1) list-2) list-1)
> (nconc list-1 list-2 . lists) == (nconc (nconc list-1 list-2) . lists)
This seems to me to be part of the meta-notation, i.e. it tries to
symbolically give invariants to the behaviour of nconc, but it isn't
executable code. The second and last lines mean specifically:
- (nconc nil list-a list-b list-c ... list-z)
is equivalent to
(nconc list-a list-b list-c ... list-z)
- (nconc list-1 list-2 list-a list-b ... list-z)
is equivalent to
(nconc (nconc list-1 list-2) list-a list-b ... list-z)
Actually you could use this meta-notation to write macros to convert
the expressions, using a destructuring pattern matching language, e.g.
(defrule (nconc nil . lists)
(nconc . lists))
(defrule (nconc list-1 list-2 . lists)
(nconc (nconc list-1 list-2) . lists))
> What is the conventional way adding items to end of the
> list starting from the empty list ?
You try to avoid it. Lists in CL can grow at the front in O(1), but
need O(n) to grow at the end. So if you find that you need to add to
a list at the end in a loop, you do this instead:
(do ((list nil (cons new-item list))
(new-item <whatever here>))
(<end-condition>
;; Return the reverted list
(nreverse list))
<whatever here>)
This will grow the list in reverse at the front by O(1) during each
iteration, and return the destructively reversed list at the end
(which takes O(n), but only once).
Another option would be to use queues, which also offer O(1) addition
at the end. There are several ways to implement queues, from the very
simple if you only need insertion at the end (using a Lisp list, and
keeping a reference to the last cons), to the very complex if you need
ordered insertion (skew heaps, splay trees, binomial heaps, fibonacci
heaps, calendar queues, ...[1]).
Of course if you only need to add an item at the end once in a while,
you can simply do
(setq list (nconc list (list item)))
or non-destructively
(setq list (append list (list item)))
> (defun append-2 (list)
> (let ((result '()))
> (loop for i in list
> if result do (nconc result (list i))
> else do (setf result (list i)))
> result))
> ;; Why NCONC didn't work on NIL ?
You are misunderstanding destructive functions: Destructive functions
are still functions in that they don't change the value of their
arguments, i.e. the variable list is still bound to the same object
after your call to nconc as it was before. It is just that
destructive functions are allowed (though _not required_) to destroy
the things passed in, i.e. the list referenced by list might get
thrashed in the process.
Hence the correct way to use destructive functions is to use them like
you would use their non-destructive counterparts, i.e.
* (let ((list nil))
(dotimes (i 10 list)
(setq list (nconc list (list i)))))
(0 1 2 3 4 5 6 7 8 9)
> (defun split-1 (string &optional (separator #\Space))
> (let ((in-word nil)
> (result '())
> (start 0)
> (end (length string)))
> (do ((i 0 (1+ i)))
> ((>= i end) result)
> (let ((c (char string i)))
> (cond ((and (not in-word) (not (eql c separator)))
> (setf start i)
> (setf in-word t))
> ((and in-word (eql c separator))
> (setf in-word nil)
> ;; What is the conventional method of appending items
> ;; at the end of the list ?
> (if result
> (nconc result (list (subseq string start i)))
> (setf result (list (subseq string start i))))))))))
Note that you can bind the initial variables inside the do as well, so
that we get:
(defun split (string &optional (separator #\Space))
(do ((in-word nil)
(result '())
(start 0)
(end (length string))
(i 0 (1+ i)))
((>= i end) (nreverse result))
(let ((char (char string i)))
(cond
((and (not in-word) (not (char= char separator)))
(setq start i in-word t))
((and in-word (char= char separator))
(push (subseq string start i) result)
(setq in-word nil))))))
> (defun split-2 (string &optional (separator #\Space))
> (let (in-word c (start 0))
> (loop for i from 0 below (length string)
> do (setf c (char string i))
> if (and (not in-word) (not (eql c separator)))
> do (setf start i) (setf in-word t)
> if (and in-word (eql c separator))
> do (setf in-word nil)
> and collecting (subseq string start i))))
Again you can fold the bindings into the loop, and you can use more
than one for loop:
(defun split (string &optional (separator #\Space))
(loop with in-word = nil
with start = 0
for char across string
for i from 0
when (and (not in-word) (not (char= char separator)))
do (setq start i in-word t)
when (and in-word (char= c separator))
do (setq in-word nil)
and collect (subseq string start i)))
> As I can see each thing can be expressed in Lisp in many ways.
> I haven't much experience in programming on Lisp and sometimes
> it is difficult to decide what way should be used. How you
> (experienced Lispers) would write such function ?
Sadly Google/Deja hasn't got their pre-August-2000 archives up yet, or
you could simply search for all the various implementations of split
(or partition, as it has been called here) that have been posted to
c.l.l in the previous years. Here's a link to just one implementation:
http://groups.google.com/groups?q=msgid:39F36F1A.B8F19D20%40simplex.nl&ic=1
Generally you can write such functions in very different ways, and one
of the strengths of CL is that it allows you to write most of them
equally well. E.g. you can look at the task as one that is best
solved with a simple state-machine, and you can write that directly
using prog/tagbody and go. Or you can use higher-order sequence
functions, like you did in your example #3. Or you could use
string-streams. Or iteration. Or even recursion.
The important thing is that you feel comfortable with the approach you
take, in order to avoid introducing bugs.
Regs, Pierre.
Footnotes:
[1] There's been a huge amount of research in this area, because
ordered event queues are one of the most critical components of
event-driven simulation systems.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
"Vladimir V. Zolotych" <······@eurocom.od.ua> writes:
> Could you explain me second and last line of [this below]?
> I knew what period (.) means by itself (notation for cons)
> but not in such context.
>
> (nconc) => ()
> (nconc nil . lists) == (nconc . lists)
> (nconc list) => list
> (nconc list-1 list-2) == (progn (rplacd (last list-1) list-2) list-1)
> (nconc list-1 list-2 . lists) == (nconc (nconc list-1 list-2) . lists)
Think of any sequence with a dot before the last element as being
constructed by list* without the dot. e.g.
( . A ) turns out to be invalid notation, but would mean A
because (LIST* 'A) => A
( B . A) means (LIST* 'B 'A) means ( B . A )
( C B . A ) means (LIST* 'C 'B 'A) means ( C . ( B . A ))
So
(NCONC NIL . LISTS)
is the same as saying
(NCONC . ( NIL . LISTS ))
The Lisp printer ordinarily uses this notatoin, so Lisp programmers are
expected to be familiar with it.
This is really just a fancy way of saying "...lists..." in the last position.
That is,
(nconc nil . lists ) == (nconc . lists)
means
(nconc nil ...lists...) == (nconc ...lists...)
means
(nconc nil l1 l2 l3 ... lN) == (nconc l1 l2 l3 ... lN)
and
(nconc list-1 list-2 . lists) == (nconc (nconc list-1 list-2) . lists)
means
(nconc list-1 list-2 ...lists...) == (nconc (nconc list-1 list-2) ...lists...)
means
(nconc l1 l2 l3 l4 ... lN) == (nconc (nconc l1 l2) l3 l4 ... lN)
Those are just meta-notations for talking about structure, though.
You can't use dot notation in code that way. Normally you'd use APPLY.
That is,
(nconc nil . lists ) == (nconc . lists)
means
(apply #'nconc nil lists) == (apply #'nconc lists)
AND
(nconc list-1 list-2 . lists) == (nconc (nconc list-1 list-2) . lists)
means
(apply #'nconc list-1 list-2 . lists)
== (apply #'nconc (nconc list-1 list-2) lists)
I hope that makes some sense.
> What is the conventional way adding items to end of the
> list starting from the empty list ?
As to adding items to the end of a list starting with an empty list, you
must ALWAYS use NCONC with SETQ around it since the first NCONC has nothing
to latch onto by side-effect. That is:
(setq x (nconc x (list new-element)))
and never just the NCONC by itself since if X is NIL, the NCONC will return
a list of the new-element, but X will not be changed by side-effect.
HOWEVER, the conventional way to build up a list of elements when adding
single elements to the end is to build them up on the front and reverse
the list as the last step. That's because NCONC is an O(N) operation and
becuase if you're building up a length (N) list, it will take you O(N^2),
while CONS (or PUSH, actually, which is a better abstraction) is O(1) and
REVERSE (or usually NREVERSE unless you have reason to believe the list
got shared while being consed up and cannot be destroyed) is O(N), so
constructing a list this way is only O(N). Using the COLLECT facility in
LOOP will hide these tricks but will do the right thing computationally.
(You can do trickery with NCONC where you remember successive tails and it
doesn't end up being O(N^2) when you're done, and sometimes you have to
do this if adding multiple elements at a time, but mostly its an inconvenience
and people screw it up a lot.)
> (defun append-2 (list)
> (let ((result '()))
> (loop for i in list
> if result do (nconc result (list i))
> else do (setf result (list i)))
> result))
> ;; Why NCONC didn't work on NIL ?
You must do SETQ. NCONC, like all functions, is call-by-value
(meaning call-by-identity in lisp, not call-by-copy). When it gets
the NIL, it doesn't know where it came from (i.e., does not know
about the RESULT variable). The fix is probably
(setq result (nconc result (list i))) although I didn't inspect your
code thoroughly to be sure.
> As I can see each thing can be expressed in Lisp in many ways.
> I haven't much experience in programming on Lisp and sometimes
> it is difficult to decide what way should be used. How you
> (experienced Lispers) would write such function ?
We all go through this. You learn by practice and sometimes by
having others critique your code or help you find bugs.