Hi,
I'm trying to create a list of sequential numbers, something like that:
(1 2 3 4 5 6 7 8 ... n)
being 'n' a predefined value)
To do this I've defined this function
(defun create-seq-list (list)
(if (eq (list-length list) 15)
(return-from create-seq-list list)
(create-seq-list (cons (+ (list-length list) 1) list))))
So to create the list: (reverse (create-seq-list '()))
I'm wondering if Lisp provides any sentence to do this directly, by the
way any improvement on this code is welcome.
Best regards
javi wrote:
> Hi,
>
> I'm trying to create a list of sequential numbers, something like that:
>
> (1 2 3 4 5 6 7 8 ... n)
>
> being 'n' a predefined value)
>
> To do this I've defined this function
>
> (defun create-seq-list (list)
> (if (eq (list-length list) 15)
> (return-from create-seq-list list)
> (create-seq-list (cons (+ (list-length list) 1) list))))
>
> So to create the list: (reverse (create-seq-list '()))
>
> I'm wondering if Lisp provides any sentence to do this directly, by the
> way any improvement on this code is welcome.
This is very inefficient because list-length iterates over the
intermediate lists in each recursive call.
If you insist on using recursion, recurse over the numbers you insert:
(defun create-seq-list (n)
(labels ((create (i)
(if (= i n)
(list i)
(cons i (create (1+ i))))))
(create 1)))
This is not tail-recursive, though. You could fix that by using an
accumulator. It's much better to use iteration here, though:
(defun create-seq-list (n)
(loop for i from 1 upto n collect i))
More detailed comments on your code: You shouldn't use eq on numbers (or
character) because it might not work. Use eql or = instead. The use of
return-from was gratuitous. You only need to use return constructs to
break out of sequence of instructions (usually introduced via a progn),
not if the form in question is the last one to be executed in your
function anyway.
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Jan 19, 6:16 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Jan 19, 11:14 pm, Chris Russell <·····················@gmail.com>
> wrote:
>
> > On Jan 19, 10:01 pm, "John Thingstad" <·······@online.no> wrote:
>
> > > På Sat, 19 Jan 2008 22:36:42 +0100, skrev Rainer Joswig <······@lisp.de>:
>
> > > >> (defun csl-rec (n &optional res)
> > > >> (if (zerop n) res
> > > >> (csl-rec (1- n) (push n res))))
>
> > > > PUSH?
>
> > > push!
>
> > cons.
>
> Girl I want to make you sweat
> sweat till you can't sweat no more
> and if you cry out
> I'm gonna push it some, more, more
> girl I want to make you sweat
> sweat till you can't sweat no more
> and if you cry out
> I'm gonna push it
> Push it, push it some more
Slobodan, "The Pros and Cons of Breathing" are about all I could come
up with, so don't bury me standing (Fall Out Boy) but Javi, take this
to your grave ;-)
This is the non-tail recursive version:
(defun n-lister (n)
(reverse (n-list n)))
N-LISTER
>
(defun n-list (n)
(if (zerop n) nil
(cons n (n-list (1- n)))))
N-LIST
>
(n-list 5)
(5 4 3 2 1)
>
(n-lister 5)
(1 2 3 4 5)
Slobodan's more efficient tail recursive version does not require that
you reverse the list, but it is more conventional to use CONS instead
of PUSH - a macro effecting both a CONS and a SETF, which just amounts
to extra sweat. ;-)
http://www.lispworks.com/documentation/HyperSpec/Body/m_push.htm
>
(defun n-list2 (n &optional nlist)
(if (zerop n) nlist
(n-list2 (1- n) (cons n nlist))))
N-LIST2
>
(n-list2 5)
(1 2 3 4 5)
agt
P� Sun, 20 Jan 2008 21:30:18 +0100, skrev viper-2
<········@mail.infochan.com>:
> ( defun csl-rec (n &optional res)
> (if (zerop n) res
> (csl-rec (1- n) (push n res))))
vs.
> (defun n-list2 (n &optional nlist)
> (if (zerop n) nlist
> (n-list2 (1- n) (cons n nlist))))
Personally I like the push. It sees somewhat clearer what is happening.
(readability is a concern in itself.)
This has the side effect of setting res as well, but since it is tail
recursive and it would do that anyhow it has no effect on performance.
push is somewhat of a black sheep in lisp as it actually alters it's
second argument. That is the function has side effects. For this reason I
think many see cons as a purer solution.
So you can write:
(let (x)
(push 1 x)
x)
instead of:
(let (x)
(setf x (push 1 x))
x)
This is different from functions like remove and sort that require that
you use the returned value.
As a final note push is a macro that expands to a cons.
This is what it looks like in LispWorks:
CL-USER 1 > (pprint(macroexpand '(push 1 x)))
(LET ((#:|new-value-791| 1))
(LET* ((#:G790 (CONS #:|new-value-791| X))) (SETQ X #:G790)))
Note that the temporary unique variables are used to avoid side effects.
Appart from that it is in effect a cons followed by a setq.
Note also that you can push onto anything that can be adressed by setf not
just setq.
(push 1 (aref *A* 1)) for example.
CL-USER 4 > (defparameter *A* (make-array 3 :initial-element nil))
*A*
CL-USER 8 > (push 1 (aref *A* 1))
(1)
CL-USER 9 > *A*
#(NIL (1) NIL)
CL-USER 16 > (pprint (macroexpand '(push 1 (aref *a* 1))))
(LET ((#:|new-value-805| 1))
(LET* ((#:G803 *A*)
(#:G804 1)
(#:G802 (CONS #:|new-value-805| (AREF #:G803 #:G804))))
(SETF::\"COMMON-LISP\"\ \"AREF\" #:G802 #:G803 #:G804)))
This could also be written as (setf (aref *A* 1) (cons 1 (aref *A* 1))) of
cource.
--------------
John Thingstad
On Jan 19, 6:16 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
>
> Girl I want to make you sweat
> sweat till you can't sweat no more
> and if you cry out
> I'm gonna push it some, more, more
> girl I want to make you sweat
> sweat till you can't sweat no more
> and if you cry out
> I'm gonna push it
> Push it, push it some more
BTW Slobodan, UB40 is one of my favourite bands too. I saw them live
in about 1981 or 1982 at the University of Aberdeen and fell for them
instantly, just before they became famous some months later.
Your code substituting CONS for PUSH in the recursive call:
(defun csl-rec (n &optional res)
(if (zerop n) res
(csl-rec (1- n) (cons n res))))
Remember that the arguments to a function call are first evaluated and
then the values are assigned to that function's formal parameters. We
say (loosely) that the formal parameters are bound to the arguments in
the call.
So we don't need PUSH which invokes SETF, when the evaluated CONS
form is already assigned automatically to the parameter RES by the
"binding" process.
agt
On Jan 21, 3:30 am, viper-2 <········@mail.infochan.com> wrote:
> On Jan 19, 6:16 pm, Slobodan Blazeski <·················@gmail.com>
> wrote:
>
>
>
> > Girl I want to make you sweat
> > sweat till you can't sweat no more
> > and if you cry out
> > I'm gonna push it some, more, more
> > girl I want to make you sweat
> > sweat till you can't sweat no more
> > and if you cry out
> > I'm gonna push it
> > Push it, push it some more
>
> BTW Slobodan, UB40 ..
UB40? Are they authors. I've only heard about Inner circle's
http://www.youtube.com/watch?v=7rQY682SoyQ
cheers
Slobodan
On Jan 21, 4:22 am, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Jan 21, 3:30 am, viper-2 <········@mail.infochan.com> wrote:
>
> > On Jan 19, 6:16 pm, Slobodan Blazeski <·················@gmail.com>
> > wrote:
>
> > > Girl I want to make you sweat
> > > sweat till you can't sweat no more
> > > and if you cry out
> > > I'm gonna push it some, more, more
> > > girl I want to make you sweat
> > > sweat till you can't sweat no more
> > > and if you cry out
> > > I'm gonna push it
> > > Push it, push it some more
>
> > BTW Slobodan, UB40 ..
>
> UB40? Are they authors. I've only heard about Inner circle'shttp://www.youtube.com/watch?v=7rQY682SoyQ
Ouch! It's been such a long time since I heard that track. I suspect
that Bob Marley is the author of the song, which was originally
entitled "Looking in your big brown eyes". Inner Circle's version was
released in 1993 "Sweat A La Long", then UB40 released their version
later "Girl I want to make you sweat".
I'm not altogether sure, so I wouldn't push it. :-)
agt
From: Holger Schauer
Subject: Re: Create a list of number
Date:
Message-ID: <yxz3asr8ons.fsf@gmx.de>
On 5254 September 1993, Pascal Costanza wrote:
> (defgeneric csl/acc (n result)
> (:method ((n (eql 1)) result) (cons n result))
> (:method ((n integer) result) (csl/acc (1- n) (cons n result))))
> (defgeneric csl (n)
> (:method ((n integer))
> (assert (> n 0))
> (csl/acc n ())))
I really like that style, having done quite a lot with Prolog several
(light)years ago. However, this immediately brings back the discussion
about general predicate dispatch we had some days ago: it would have
been nice to avoid the assertion in favour of method dispatch.
Holger
--
--- http://hillview.bugwriter.net/ ---
"I have some people saying `This way',
I have some people saying `That way',
I have some people saying `No way'."
-- The Hives, "Walk idiot walk"
P� Mon, 21 Jan 2008 11:21:27 +0100, skrev Holger Schauer
<··············@gmx.de>:
> On 5254 September 1993, Pascal Costanza wrote:
>> (defgeneric csl/acc (n result)
>> (:method ((n (eql 1)) result) (cons n result))
>> (:method ((n integer) result) (csl/acc (1- n) (cons n result))))
>
>> (defgeneric csl (n)
>> (:method ((n integer))
>> (assert (> n 0))
>> (csl/acc n ())))
>
> I really like that style, having done quite a lot with Prolog several
> (light)years ago. However, this immediately brings back the discussion
> about general predicate dispatch we had some days ago: it would have
> been nice to avoid the assertion in favour of method dispatch.
>
> Holger
>
Instead of assert he could have written
(check-type n (integer 0 *))
or
(deftype positive-integer () `(integer 0 *))
(deftype odd-integer () `(and integer (satisfies oddp)))
(The backquote is only needed if there are variables in the second
argument to be substituted in, but I use it for consistency in my
declaration as it never hurts.)
unfortunately this facillity works only for types not for classes.
Ie. I would have liked:
(defgeneric csl (n)
(:method ((n (integer 0 *))) ...)
(:method ((n odd-integer)) ...)
(:method ((n integer) ...))))
--------------
John Thingstad
Holger Schauer wrote:
> On 5254 September 1993, Pascal Costanza wrote:
Wow, what a date... ;)
>> (defgeneric csl/acc (n result)
>> (:method ((n (eql 1)) result) (cons n result))
>> (:method ((n integer) result) (csl/acc (1- n) (cons n result))))
>
>> (defgeneric csl (n)
>> (:method ((n integer))
>> (assert (> n 0))
>> (csl/acc n ())))
>
> I really like that style, having done quite a lot with Prolog several
> (light)years ago. However, this immediately brings back the discussion
> about general predicate dispatch we had some days ago: it would have
> been nice to avoid the assertion in favour of method dispatch.
You can always go back to cond, which is not that different, if you
think about it:
(defun csl/acc (n result)
(cond ((eql n 1) (cons n result))
((integerp n) (csl/acc (1- n) (cons n result)))))
(defun csl (n)
(cond ((not (> n 0)) (error "Invalid parameter for csl."))
(otherwise (csl/acc n '()))))
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Den Mon, 21 Jan 2008 12:43:41 +0100 skrev Pascal Costanza:
> Holger Schauer wrote:
>> On 5254 September 1993, Pascal Costanza wrote:
>
> Wow, what a date... ;)
It's been discussed here recently.
http://en.wikipedia.org/wiki/Eternal_September
Cheers,
Maciej
From: Holger Schauer
Subject: Re: Create a list of number
Date:
Message-ID: <yxzzluz71hl.fsf@gmx.de>
On 5255 September 1993, Pascal Costanza wrote:
> Holger Schauer wrote:
>> On 5254 September 1993, Pascal Costanza wrote:
[...]
>> I really like that style, having done quite a lot with Prolog several
>> (light)years ago. However, this immediately brings back the discussion
>> about general predicate dispatch we had some days ago: it would have
>> been nice to avoid the assertion in favour of method dispatch.
> You can always go back to cond, which is not that different, if you
> think about it: [...]
True. But the same reasons why one favours method dispatch over manual
typecase apply here, too. The way you lay out the code immediately
suggests a declarative way to approach a problem (or it's
solution). In my eye, that's not true for cond (and similar
constructs).
I know it's of no value to howl at the moon because of the world being
as cruel as it is, but still ... Well, Kenny is probably right in his
judgement that it makes a lot more sense to use that damn screwdriver
and get the job done and forget about that clean looking hammer.
Holger
--
--- http://hillview.bugwriter.net/ ---
"I have some people saying `This way',
I have some people saying `That way',
I have some people saying `No way'."
-- The Hives, "Walk idiot walk"
In article <···············@gmx.de>,
Holger Schauer <··············@gmx.de> wrote:
> On 5255 September 1993, Pascal Costanza wrote:
> > Holger Schauer wrote:
> >> On 5254 September 1993, Pascal Costanza wrote:
> [...]
> >> I really like that style, having done quite a lot with Prolog several
> >> (light)years ago. However, this immediately brings back the discussion
> >> about general predicate dispatch we had some days ago: it would have
> >> been nice to avoid the assertion in favour of method dispatch.
>
> > You can always go back to cond, which is not that different, if you
> > think about it: [...]
>
> True. But the same reasons why one favours method dispatch over manual
> typecase apply here, too. The way you lay out the code immediately
> suggests a declarative way to approach a problem (or it's
> solution). In my eye, that's not true for cond (and similar
> constructs).
>
> I know it's of no value to howl at the moon because of the world being
> as cruel as it is, but still ... Well, Kenny is probably right in his
> judgement that it makes a lot more sense to use that damn screwdriver
> and get the job done and forget about that clean looking hammer.
It's not just a hammer. It's a huge cannon.
>
> Holger
Method dispatch in Common Lisp is fully dynamic. That's the service
provided by Generic Functions in Common Lisp. CLOS is best
applicable when the domain has rich and changing structure
and behavior.
Generic Functions were not designed to break up functions
in smaller pieces and to work efficiently with static
data types (like numbers). One can apply Generic Functions
to, say, list processing in Lisp or one could extend
CLOS to also handle predicates or types
- but I would not recommend that.
CONSes are tiny and CLOS is a very large cannon.
OK,
thanks to everybody, I didn't expect so many answers to this question but
I delighted with all of them because I've learned a lot about recursion,
new functions and lisp in general.
So thanks again
<·············@hotmail.com> writes:
> I'm trying to create a list of sequential numbers, something like that:
>
> (1 2 3 4 5 6 7 8 ... n)
>
I wrote this "Look Ma, no cons/append" for my toolbox
(defun range (n)
(if (= 0 n) () `(,@(range (1- n)) ,n)))
(But I wouldn't recommand it since
I still wonder if there are issues,
like with the result being a constant.)
In article <··············@thierrypirot.net>,
Thierry Pirot <·@thierrypirot.net> wrote:
> <·············@hotmail.com> writes:
> > I'm trying to create a list of sequential numbers, something like that:
> >
> > (1 2 3 4 5 6 7 8 ... n)
> >
> I wrote this "Look Ma, no cons/append" for my toolbox
>
> (defun range (n)
> (if (= 0 n) () `(,@(range (1- n)) ,n)))
>
> (But I wouldn't recommand it since
> I still wonder if there are issues,
> like with the result being a constant.)
Is the result a constant?
No cons/append?
Clozure CL:
? (read-from-string "`(,@(range (1- n)) ,n))")
(APPEND (RANGE (1- N)) (LIST N))
Thierry Pirot <·@thierrypirot.net> writes:
> <·············@hotmail.com> writes:
>> I'm trying to create a list of sequential numbers, something like that:
>>
>> (1 2 3 4 5 6 7 8 ... n)
>>
> I wrote this "Look Ma, no cons/append" for my toolbox
>
> (defun range (n)
> (if (= 0 n) () `(,@(range (1- n)) ,n)))
>
> (But I wouldn't recommand it since
> I still wonder if there are issues,
> like with the result being a constant.)
The main issue being still the APPEND that lies behind, so it's O(n�) at best.
CLISP> (ext:expand-form '`(,@(range (1- n)) ,n))
(APPEND (RANGE (1- N)) (LIST N)) ;
T
SBCL> (SB-WALKER:WALK-FORM '`(,@(range (1- n)) ,n))
(SB-IMPL::BACKQ-APPEND (RANGE (1- N)) (SB-IMPL::BACKQ-LIST N))
etc...
--
__Pascal Bourguignon__
"Pascal J. Bourguignon" <···@informatimago.com> wrote in message
···················@pbourguignon.anevia.com...
> Thierry Pirot <·@thierrypirot.net> writes:
>
>> <·············@hotmail.com> writes:
>>> I'm trying to create a list of sequential numbers, something like that:
>>>
>>> (1 2 3 4 5 6 7 8 ... n)
>>>
>> I wrote this "Look Ma, no cons/append" for my toolbox
>>
>> (defun range (n)
>> (if (= 0 n) () `(,@(range (1- n)) ,n)))
>>
>> (But I wouldn't recommand it since
>> I still wonder if there are issues,
>> like with the result being a constant.)
>
> The main issue being still the APPEND that lies behind, so it's O(n�) at best.
So he could use the seemingly little known ,. rather than ,@ which will yield an
<nconc>.
(defun range (n)
(if (= 0 n) () `(,.(range (1- n)) ,n)))
Carl Taylor