Hello all,
I want to concatenate 2 given lists in the most general form throug a
code and i am restaining myself from using the conactenate function.
The code i am using for this is like:
(defun merge-list(x y)
(print (length y))
(let ((len(length y)))
(cond
((equal len 0) nil)
((print(cons (car y) x))
(merge-list x (cdr y))))))
But i am still havin problems since not able to maintain the variable
value as such..
Can anyone help me out with this ..
Thanks
·········@yahoo.co.in writes:
> Hello all,
> I want to concatenate 2 given lists in the most general form throug a
> code and i am restaining myself from using the conactenate function.
> The code i am using for this is like:
> (defun merge-list(x y)
Wrong!
Name it: concatenate-list
> (print (length y))
> (let ((len(length y)))
Wrong!
LENGTH applied to a list is O(n) Since you'll be calling recursively
the function n times, this will give O(n�).
> (cond
> ((equal len 0) nil)
> ((print(cons (car y) x))
Wrong!
Please, read a tutorial or the HyperSpec reference which gives the
syntax of COND. Why this is valid, this is most probably NOT what you
want. It doesn't mean what you think it means.
> (merge-list x (cdr y))))))
> But i am still havin problems since not able to maintain the variable
> value as such..
You don't need to maintain any variable.
It's just a matter of declaring what the concatenation of two lists
is. Decompose it in various cases:
(concatenate-list () list) == list
(concatenate-list (head . tail) list) == (cons head (concatenate-list tail list))
and there is no other cases. These definitions are enough, given both
lists (head . tail) and list are proper lists, since the length of
tail is than the length of (head . tail) therefore eventually the
first argument will be the empty list (), for which case we know the answer.
So you can write it directly:
(defun concatenate-list (left list)
(cond ((null left) list)
(t (cons (first left) (concatenate-list (rest left) list)))))
(concatenate-list '(1 2 3) '(a b c)) --> (1 2 3 A B C)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Litter box not here.
You must have moved it again.
I'll poop in the sink.
·········@yahoo.co.in wrote:
> Hello all,
> I want to concatenate 2 given lists in the most general form throug a
> code and i am restaining myself from using the conactenate function.
what's wrong with "append"?
CL-USER > (append nil '(1 2 3))
(1 2 3)
CL-USER > (append '(1 2) '(3 4))
(1 2 3 4)
CL-USER > (append '(1 2 3) nil)
(1 2 3)
CL-USER > (append nil)
NIL
CL-USER > (append nil nil)
NIL
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> ·········@yahoo.co.in wrote:
>
>
>>Hello all,
>> I want to concatenate 2 given lists in the most general form throug a
>>code and i am restaining myself from using the conactenate function.
>
>
> what's wrong with "append"?
>
His professor said they couldn't use that either.
On Tue, 14 Feb 2006 08:13:42 GMT, David Sletten <·····@slytobias.com>
wrote:
>> what's wrong with "append"?
>>
>
>His professor said they couldn't use that either.
Can he use LAST and RPLACD?
(let ((list1 (list 1 2 3))
(list2 (list 4 5 6)))
(rplacd (last list1) list2)
list1)
==> (1 2 3 4 5 6)
Or NREVERSE and PUSH?
(let ((list1 (list 1 2 3))
(list2 (list 4 5 6)))
(dolist (x (nreverse list1))
(push x list2))
list2)
==> (1 2 3 4 5 6)
In article <··································@4ax.com>,
····@unreal.uncom wrote:
> On Tue, 14 Feb 2006 08:13:42 GMT, David Sletten <·····@slytobias.com>
> wrote:
>
> >> what's wrong with "append"?
> >>
> >
> >His professor said they couldn't use that either.
>
> Can he use LAST and RPLACD?
Probably not -- they're probably studying the chapter on recursion.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
·········@yahoo.co.in writes:
> Hello all,
> I want to concatenate 2 given lists in the most general form throug a
> code and i am restaining myself from using the conactenate function.
> The code i am using for this is like:
> (defun merge-list(x y)
> (print (length y))
> (let ((len(length y)))
> (cond
> ((equal len 0) nil)
> ((print(cons (car y) x))
> (merge-list x (cdr y))))))
> But i am still havin problems since not able to maintain the variable
> value as such..
> Can anyone help me out with this ..
> Thanks
Congratulations! Your code is quite close to almost working.
The base case of the recursion needs fixing
((equal len 0) nil) ===>>> ((equal len 0) x)
and your attempt to change x is failing because cons is a
pure function, you need push
(print(cons (car y) x) ===>>> (print(push (car y) x))
So now you have
CL-USER> (defun merge-list(x y)
(print (length y))
(let ((len(length y)))
(cond
((equal len 0) x)
((print(push (car y) x))
(merge-list x (cdr y))))))
MERGE-LIST
CL-USER> (merge-list '(1 2 3) '(a b c))
3
(A 1 2 3)
2
(B A 1 2 3)
1
(C B A 1 2 3)
0
(C B A 1 2 3)
and you have something half-way working that you can try to
debug.
Interestingly, the worst bug, the one that is making the
experienced Lisp programmers vomit up their lunch (nothing
personal, its the code) is a performance problem.
After stripping out the print statements and setting print
length to 5 I try timing it on some long lists:
CL-USER> (time (merge-list (make-list 10000)
(make-list 10000)))
; Evaluation took:
; 1.245407 seconds of user run time
CL-USER> (time (merge-list (make-list 20000)
(make-list 20000)))
; Evaluation took:
; 5.163614 seconds of user run time
CL-USER> (time (merge-list (make-list 40000)
(make-list 40000)))
; Evaluation took:
; 20.996485 seconds of user run time
Doubling the length of the list ought to double the run
time, but no, it is taking four times as long. Lists four
times as long are taking 16 times as long.
This is the kind of bug that makes it past testing and out
to the paying customers, because the answers are correct.
Then you get a support call "Your program goes into an
infinite loop when we try to process large files." It is not
actually going into an infinite loop, it is just taking an
unreasonable amount of time.
The culprit is the call to length. Length walks all the way
down the 40000 long list to count up how long it is. On the
next step of the recursion it walks all the way down the
39999 long list to count up how long that one is. On the
third step of the recursion it walks all the way down,
excuse me while I rest, I'm getting tired just thinking
about it, all the way down the 39998 long list to count ....
You get the idea.
The irony is that CL is cunningly designed so that the empty
list is considered to be false by the conditional tests, and
everything else, including lists with 1, 2, ... etc elements
is considered to be true by the conditional tests. So you
don't need (equal (length y) 0) just plain (not y) would do.
(endp y) is better because it checks that y is actually a list.
An amusing point is that you are supposed to write a cond
like this
(cond ((predicate stuff) (do when true))
(t (do this)(and this)(when false)))
but you get away with writing
(cond ((predicate stuff) (do when true))
((do this)(and this)(when false)))
missing out the second predicate, which you need to be
always true, because in your code (do this) returns a
non-empty list, and non-empty lists are always true.
Another surprising point is that the PUSH is actually a
total waste. You need (cons (car y) x). Saving (cons (car y)
x) in x with (push (cons (car y) x)) is sufficient, but not
needed. You are going to pass it to the recursive call of
merge, so do so directly without saving it in a variable.
(defun merge-list(x y)
(cond ((endp y) x)
(t (merge-list (cons (car y) x)
(cdr y)))))
Still not correct, but you can probably finish debugging it
on your own from there.
One thing you need to be aware of is that "merge" is a
technical term. There is even a function that does it and
which can be abused like this.
CL-USER> (defun merge-list (x y)
(merge 'list x y (constantly nil)))
MERGE-LIST
CL-USER> (merge-list '(1 2 3) '(a b c))
(1 2 3 A B C)
There are many ways of concatenating two lists in CL for
example
CL-USER> (defun merge-list (x y)
(reduce #'cons x
:from-end t
:initial-value y))
CL-USER> (defun merge-list (x y)
`(,@x ,@y))
You might later try to find the flaws in these two really
bad ways of doing it
CL-USER> (defun merge-list (x y)
(subst y nil x))
MERGE-LIST
CL-USER> (merge-list '(1 2 3) '(a b c))
(1 2 3 A B C)
CL-USER> (defun merge-list-comedy-stupid-way (x y)
(coerce (make-array (+ (length x)
(length y))
:displaced-to (make-array (list 2 (length x))
:initial-contents
(list x y)))
'list))
MERGE-LIST
CL-USER> (merge-list '(1 2 3) '(a b c))
(1 2 3 A B C)
CL-USER> (time (merge-list-comedy-stupid-way (make-list 40000)
(make-list 40000)))
; Evaluation took:
; 0.119728 seconds of user run time
Notice that even the comedy-stupid way is 200 times faster
than making the blunder with length.
Alan Crowe
Edinburgh
Scotland
Here's another one... it builds up a third list and then cons's that to
the destination list
;;;; like append
;;; given two lists stick them together
;;; only cons, car and cdr
;;; while a is non-null build a list c with the car of a
;;; then cons b with the car of a until c is empty
(defun concat(a b &optional c)
(cond
(a
(concat (cdr a) b (cons (car a) c)))
(c
(concat a (cons (car c) b) (cdr c)))
(t
b)))
justinhj wrote:
> (defun concat(a b &optional c)
you don't need c:
(defun concat (a b)
(if a
(cons (car a) (concat (cdr a) b))
(when b
(cons (car b) (concat a (cdr b))))))
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> justinhj wrote:
>
> > (defun concat(a b &optional c)
>
> you don't need c:
>
> (defun concat (a b)
> (if a
> (cons (car a) (concat (cdr a) b))
> (when b
> (cons (car b) (concat a (cdr b))))))
>
> --
> Frank Buss, ··@frank-buss.de
> http://www.frank-buss.de, http://www.it4-systems.de
No you don't need it, and Pascal presented a more succint version
earlier...
(defun concatenate-list (left list)
(cond ((null left) list)
(t (cons (first left) (concatenate-list (rest left) list)))))
I just liked it :)
Justin
I'm pretty new to the world of Lisp but why always with the conds? :)
I'm sure they're very concise under the right situation but when you
have a test then-else condition surely if is more appropriate for the
task at hand? The way I understand it is cond is most useful for doing
if-then-else-if-else's?
(defun merge-lists (x y)
(if (null x)
y
(cons
(car x) (merge-lists (cdr x) y))))
Please someone correct me if my thinking about cond is wrong but I
think the if is much cleaner for the most part :). Just my personal
opinion.
I picked up a lot from this thread thanks to everyone involved
especially Pascal for his very nice post.
I started timing some of the functions and surprisingly I found
recursive code above is faster than the tail-recursive version with
acting as an accumulator. I understand why but I wasn't expecting it,
up until now I'd always assumed the tail-recursive versions to be
faster, not when you can avoid half the work apparently ;).
Take care,
Mark.
netytan wrote:
> I'm pretty new to the world of Lisp but why always with the conds? :)
> I'm sure they're very concise under the right situation but when you
> have a test then-else condition surely if is more appropriate for the
> task at hand? The way I understand it is cond is most useful for doing
> if-then-else-if-else's?
I use cond if I choose from more than two conditions.
netytan wrote:
> (defun merge-lists (x y)
> (if (null x)
> y
> (cons
> (car x) (merge-lists (cdr x) y))))
>
> Please someone correct me if my thinking about cond is wrong but I
> think the if is much cleaner for the most part :). Just my personal
> opinion.
That's a matter of taste, sometimes "cond" looks better when formatting.
Another way to format Pascal's idea:
(defun merge-lists (x y)
(or (and x (cons (first x) (merge-lists (rest x) y))) y))
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
"netytan" <·······@gmail.com> writes:
> I'm pretty new to the world of Lisp but why always with the conds? :)
> I'm sure they're very concise under the right situation but when you
> have a test then-else condition surely if is more appropriate for the
> task at hand? The way I understand it is cond is most useful for doing
> if-then-else-if-else's?
> [...]
> Please someone correct me if my thinking about cond is wrong but I
> think the if is much cleaner for the most part :). Just my personal
> opinion.
Indeed, when there is only one condition, and only one expression in
each branch, an IF can be better than a COND.
Why for these simple exercises do we use COND anyways?
Because COND was part of the original lisping by McCarthy, not IF. :-)
But if you want a more serrious reason, when you start thinking about
such a function, you don't know a-priori the number of different cases
you will have to test. So you start to write:
(COND
((first-test) ...)
((second-test) ...)
...
(t ...))
If it happens that after the first test it remains only the other
case, it's simplier to just add:
(t ...))
rather than substitute IF for COND and remove a level of parenthesis.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
Pascal Bourguignon <······@informatimago.com> writes:
> "netytan" <·······@gmail.com> writes:
>
> > I'm pretty new to the world of Lisp but why always with the conds? :)
> > I'm sure they're very concise under the right situation but when you
> > have a test then-else condition surely if is more appropriate for the
> > task at hand? The way I understand it is cond is most useful for doing
> > if-then-else-if-else's?
> > [...]
> > Please someone correct me if my thinking about cond is wrong but I
> > think the if is much cleaner for the most part :). Just my personal
> > opinion.
>
> Indeed, when there is only one condition, and only one expression in
> each branch, an IF can be better than a COND.
>
> Why for these simple exercises do we use COND anyways?
> Because COND was part of the original lisping by McCarthy, not IF. :-)
Well, there is also the issue of more than one expression in a branch.
IF then gets a bit more ugly with the addition of the PROGN forms.
I suppose there is an additional argument in favor of simplicity of
presentation. By presenting the most general construct COND, you can do
a lot of programming without needing to find out about IF, WHEN and
UNLESS. That reduces the amount of work that is needed on the part of
the textbook writer, and reduces the number of things that must be
learned by the new programmer.
I guess it's part of the teach generality and then later introduce
special cases.
--
Thomas A. Russ, USC/Information Sciences Institute