I have written a function that creates a list containing integers from
a start value to an end value. It looks like:
(defun enumerate (start end)
(setq x nil)
(do ((i end (- i 1)))
((< i start) x)
(setq x (cons i x))
)
)
I am a newbie and was wondering if there are better ways to do the
same. I started with "(i end (- i 1)" because it gave me the list
sorted from start to end.
Thank you for your help.
vijay <········@gmail.com> writes:
> I have written a function that creates a list containing integers from
> a start value to an end value. It looks like:
>
> (defun enumerate (start end)
> (setq x nil)
> (do ((i end (- i 1)))
> ((< i start) x)
> (setq x (cons i x))
> )
> )
You are assigning a global X here. You probably want to make x a
variable of the DO as well, or else put a binding for x around the
loop (e.g., with LET). Unlike C and related languages, Lisp does not
create new bindings just because you do an assignment at top-level of
a sequence of expressions.
> I am a newbie and was wondering if there are better ways to do the
> same. I started with "(i end (- i 1)" because it gave me the list
> sorted from start to end.
It's common to just return (nreverse x) at the end in order to put things
in a better order. Since such algorithms are always O(n) anyway and
NREVERSE is also O(n), it doesn't increase the algorithmic complexity, just
adds a small constant factor.
You should know as a practical matter that you can also write:
(defun enumerate (start end)
(loop for i from start to end
collect i))
to get the same effect.
Many CL programmers would just use the loop and forget making a
function of it.
Den Tue, 29 Jan 2008 10:22:15 -0500 skrev Kent M Pitman:
>> (defun enumerate (start end)
>> (setq x nil)
>> (do ((i end (- i 1)))
>> ((< i start) x)
>> (setq x (cons i x))
>> )
>> )
>
> You are assigning a global X here. You probably want to make x a
> variable of the DO as well, or else put a binding for x around the loop
> (e.g., with LET). Unlike C and related languages, Lisp does not create
> new bindings just because you do an assignment at top-level of a
> sequence of expressions.
C (and all the derived statically-typed languages) don't introduce new
bindings just because you assign, it'd be an error in C causing
compilation to fail. Python and Ruby do, however. I assume it was a
thinko.
Cheers,
Maciej
Maciej Katafiasz <········@gmail.com> writes:
> Den Tue, 29 Jan 2008 10:22:15 -0500 skrev Kent M Pitman:
>
> >> (defun enumerate (start end)
> >> (setq x nil)
> >> (do ((i end (- i 1)))
> >> ((< i start) x)
> >> (setq x (cons i x))
> >> )
> >> )
> >
> > You are assigning a global X here. You probably want to make x a
> > variable of the DO as well, or else put a binding for x around the loop
> > (e.g., with LET). Unlike C and related languages, Lisp does not create
> > new bindings just because you do an assignment at top-level of a
> > sequence of expressions.
>
> C (and all the derived statically-typed languages) don't introduce new
> bindings just because you assign, it'd be an error in C causing
> compilation to fail. Python and Ruby do, however. I assume it was a
> thinko.
Heh. You're right to diagnose an error in what I said, though the exact
nature of the error is slightly misdiagnosed.
It's true that 'x = 3;' does not introduce a binding. But I meant
'int x = 3;' ... which is admittedly not properly referred to as an
assignment. I hadn't meant to get side-tracked on how the statement
is referred to, just to say that the notation (a "binding occurence"
if you will, I'm not actually sure of its formal name) can occur
anywhere in various code bodies and will scope to the rest of the
containing body. That is, in:
{ foo();
int a = 3;
bar(a);
}
the variable "a" will be scoped to the brace. Whereas in Lisp there is no
equivalent because:
(progn
(foo)
(setq a 3) ;assigns a global a
(bar a))
or
(progn
(foo)
(defvar a 3) ;creates and initializes a global a
(bar a))
and you have to actually put in a binding form to make it local, so you
can see the boundaries of the locality:
(progn
(foo)
(let ((a 3))
(bar)))
The equivalent in a block-structured language like C would be to require
that bindings always come at the head of one of those code blocks, so you'd
write:
{ foo();
{ int a = 3;
bar(a);
}
}
No one in the C world would expect to have to write extra braces there,
so I'm guessing that when people come to the Lisp world, they expect
things like soem Scheme dialects have where you can do:
(define (foo y)
(define x 3)
(+ x y))
and have only local effect. In Lisp, if you did the equivalent,
(defun foo (y)
(defvar x 3)
(+ x y))
you might as well have written:
(defun foo (y)
(proclaim '(special x)) ;this effect will happen at runtime
(setf (symbol-value 'x) 3) ;this effect will be global
(+ x y))
The extreme case, which most people would not expect (not because CL is
doing something obscure, but because CL thinks this usage is obscure and
does not intend you to use this feature for the purpose that might seem
"obviously intended" here):
(defun exhibit-strangeness (strangeness)
(defvar strangeness (+ strangeness 1))
strangeness)
=> EXHIBIT-STRANGENESS
(exhibit-strangeness 3)
=> 3
strangeness
=> 4
Den Tue, 29 Jan 2008 23:23:34 -0500 skrev Kent M Pitman:
>> C (and all the derived statically-typed languages) don't introduce new
>> bindings just because you assign, it'd be an error in C causing
>> compilation to fail. Python and Ruby do, however. I assume it was a
>> thinko.
>
> Heh. You're right to diagnose an error in what I said, though the exact
> nature of the error is slightly misdiagnosed.
>
> It's true that 'x = 3;' does not introduce a binding. But I meant 'int
> x = 3;' ... which is admittedly not properly referred to as an
> assignment. I hadn't meant to get side-tracked on how the statement is
> referred to, just to say that the notation (a "binding occurence" if you
> will, I'm not actually sure of its formal name) can occur anywhere in
> various code bodies and will scope to the rest of the containing body.
> That is, in:
>
> { foo();
> int a = 3;
> bar(a);
> }
>
> the variable "a" will be scoped to the brace. Whereas in Lisp there is
> no equivalent because:
>
> (progn
> (foo)
> (setq a 3) ;assigns a global a
> (bar a))
>
> or
>
> (progn
> (foo)
> (defvar a 3) ;creates and initializes a global a (bar a))
>
> and you have to actually put in a binding form to make it local, so you
> can see the boundaries of the locality:
>
> (progn
> (foo)
> (let ((a 3))
> (bar)))
>
> The equivalent in a block-structured language like C would be to require
> that bindings always come at the head of one of those code blocks, so
> you'd write:
>
> { foo();
> { int a = 3;
> bar(a);
> }
> }
That is actually the case in C before C99. C89 and K&R required you to
put all declarations before statements. And since in C {} introduce true
scope, not just group statements, it's possible to find code that uses
them for the sole purpose of introducing fresh bindings (although
admittedly that's very uncommon a need).
Cheers,
Maciej
On Wed, 30 Jan 2008 09:50:25 +0000 (UTC), Maciej Katafiasz
<········@gmail.com> wrote:
>Den Tue, 29 Jan 2008 23:23:34 -0500 skrev Kent M Pitman:
>
>> The equivalent in a block-structured language like C would be to require
>> that bindings always come at the head of one of those code blocks, so
>> you'd write:
>>
>> { foo();
>> { int a = 3;
>> bar(a);
>> }
>> }
>
>That is actually the case in C before C99. C89 and K&R required you to
>put all declarations before statements. And since in C {} introduce true
>scope, not just group statements, it's possible to find code that uses
>them for the sole purpose of introducing fresh bindings (although
>admittedly that's very uncommon a need).
It is much more common in C++ where RAII is pushed heavily.
George
--
for email reply remove "/" from address
On 29 Jan, 13:40, vijay <········@gmail.com> wrote:
> I have written a function that creates a list containing integers from
> a start value to an end value. It looks like:
>
> (defun enumerate (start end)
> (setq x nil)
> (do ((i end (- i 1)))
> ((< i start) x)
> (setq x (cons i x))
> )
> )
>
> I am a newbie and was wondering if there are better ways to do the
> same. I started with "(i end (- i 1)" because it gave me the list
> sorted from start to end.
>
> Thank you for your help.
In Qi
(define enum
Fin Fin -> [Fin]
St Fin -> [St | (enum (+ St 1) Fin)])
compiled into Lisp
(DEFUN enum (V2 V3)
(COND ((= V2 V3) (LIST V3))
(T (CONS V2 (enum (1+ V2) V3)))))
will work if the interval is not very large.
If you're beginning Lisp so I'd advise practising your recursion
before getting involved with loop.
Mark
On Jan 29, 2:19 pm, Mark Tarver <··········@ukonline.co.uk> wrote:
>
> If you're beginning Lisp so I'd advise practising your recursion
> before getting involved with loop.
>
> Mark
Yes, IMO LOOP is for blackbelts - not newbies.
On your way to learning about the primitive LABELS used by Pascal, you
may also consider using an optional parameter for another tail
recursive version:
(defun enumerate-with-op (start end &optional elist)
(if (> start end)
(reverse elist)
(enumerate-with-op (1+ start) end
(cons start elist))))
(enumerate-with-op 3 9)
(3 4 5 6 7 8 9)
Perhaps someone would comment on how LABELS might offer advantages
over the optional parameter?
agt
Den Tue, 29 Jan 2008 12:32:18 -0800 skrev viper-2:
> Perhaps someone would comment on how LABELS might offer advantages over
> the optional parameter?
It hides all your guts, so the outside only sees a clean interface
without cruft. That's also the advantage of LABELS over defining a
standalone FUNC-AUX to handle tail recursion.
Cheers,
Maciej
On Jan 29, 12:32 pm, viper-2 <········@mail.infochan.com> wrote:
> On Jan 29, 2:19 pm, Mark Tarver <··········@ukonline.co.uk> wrote:
>
>
>
> > If you're beginning Lisp so I'd advise practising your recursion
> > before getting involved with loop.
>
> > Mark
>
> Yes, IMO LOOP is for blackbelts - not newbies
Yagoddabekidding.
> On your way to learning about the primitive LABELS used by Pascal, you
> may also consider using an optional parameter for another tail
> recursive version:
>
> (defun enumerate-with-op (start end &optional elist)
> (if (> start end)
> (reverse elist)
> (enumerate-with-op (1+ start) end
> (cons start elist))))
I'm not a newbie, yet whenever I see code like this, it helps me to
mentally transliterate it to the loop that it wants to be, e.g:
(defun enumerate-with-op-iter (start end &aux elist)
(loop
;; test terminating condition, return result
(when (> start end)
(return (reverse elist)))
;; update variables for next iteration
(psetf
start (1+ start)
elist (cons start elist)))))
A newbie will more readily understand this than tail recursion.
It's better engineering too, since it produces code that is as good as
tail recursion without requiring special compiler support, and won't
blow your stack where that support is missing.
Recursion should only be used when the problem divides into
subproblems in such a way that the recursive depth is logarithmic in
the size of the input.
Newbies should definitely not be taught obfuscated crap that can
exhaust their stack storage when they don't have the right compiler or
don't invoke it in the right way. You're bringing in way too many
issues into a beginner's lesson.
Then there is the problem that people who are forced to study stuff
like this in university tend to become prejudiced against Lisp-like
languages for the rest of their lives.
P� Wed, 30 Jan 2008 06:49:32 +0100, skrev Kaz Kylheku <········@gmail.com>:
>
> I'm not a newbie, yet whenever I see code like this, it helps me to
> mentally transliterate it to the loop that it wants to be, e.g:
>
> (defun enumerate-with-op-iter (start end &aux elist)
> (loop
> ;; test terminating condition, return result
> (when (> start end)
> (return (reverse elist)))
> ;; update variables for next iteration
> (psetf
> start (1+ start)
> elist (cons start elist)))))
>
> A newbie will more readily understand this than tail recursion.
>
but.. This is a terrible way to use loop.
consider.
(loop for i from start to end collect i)
If you wanted to write it like this it is better to avoid loop all
together.
(And &aux is deprecated.. better to use let)
do is perhaps the most natural 'classic' way..
(defun enumerate (start end)
(let (list)
(do ((index start (1+ index)))
((> index end) (nreverse list))
(push index list))))
(You might notice that by starting at the end and decrementing index the
nreverse is unnecessary. I leave it to you whether you consider this
natural. Either beats the old newbie trap 'append'.)
Once you get accustomed to the parenthesises this looks a lot like a C
'for' loop.
do might look worse than loop but it is actually easier to use as it's
syntax and program flow is more predictable.
But I think you are missing the point. The reason to learn recursion is
that it is a powerfull and general technique in Lisp. Why teach newbies to
write C/Java in Lisp? The example is boring anyway. Try generating all
permutations of a list..
And stop 'translating' recursion to loops, focus on what happens to the
data structure ;)
(It feels like a foreigner trying to speak your language.)
--------------
John Thingstad
viper-2 <········@mail.infochan.com> writes:
> Perhaps someone would comment on how LABELS might offer advantages
> over the optional parameter?
>
Here's my trial, with what I concluded so far.
This is an issue I'd also like to be enlighten.
Say one programs in a stateful way --- push, progn, return,... ---
and wants the state of R to be the result of computing F.
The idea is that
- using `labels' to define F within the scope of R,
F will have access to R and can modify the state of R ;
- using R as an optional argument for F,
only values denoted by R will be passed around to F
and it won't be possible to modify the state of R like that.
1/ For example, let's collect atoms in R.
With `labels' and R from an enclosing scope, pushing in R can be performed :
(defun fl (l)
(let (r)
(labels ((f (x)
(if (atom x)
(push x r)
(progn (f (cdr x))
(f (car x))))))
(f l)))) ;r is returned.
(fl '(1 (3) . 4)) ;-> (1 3 NIL 4)
With `&optional' only the value of R is passed, not an access to R,
and FO, which differs from the previous "labels-ed" F
only by R in its signature, fails to perform the same task :
(defun fo (x &optional r)
(if (atom x)
(push x r)
(progn (fo (cdr x) r)
(fo (car x) r))))
Now, still with `&optional', if we have R a container of a list instead
then it's easy to access and modify its contents' state, viz (car R) :
(defun foc (x &optional (r (list ()))) ;Beware of '(()).
(if (atom x)
(push x (car r))
(progn (foc (cdr x) r)
(foc (car x) r))))
2/ In the case of a recursive F, going down and up the recursion,
either a single R is used all the way and
the same optional R has to be explicitly passed to each call of F,
or several R's are needed at different levels of the recursion and
`labels' will require several let-bindings of R for several calls of F.
3/ As a side note, the task done by F can be performed in a functional way :
(defun ff (x &optional r)
(if (atom x)
(cons x r)
(ff (car x)
(append (ff (cdr x))
r))))
(defun ff (x)
(if (atom x)
(list x)
(append (ff (car x))
(ff (cdr x)))))
--
Take it Easy Don't Hurry Be Happy
Thierry
�������o�o��������o�o��������o�o��������o�o��������o�o�������
Den Tue, 29 Jan 2008 05:40:25 -0800 skrev vijay:
> I have written a function that creates a list containing integers from a
> start value to an end value. It looks like:
>
> (defun enumerate (start end)
> (setq x nil)
> (do ((i end (- i 1)))
> ((< i start) x)
> (setq x (cons i x))
> )
> )
>
> I am a newbie and was wondering if there are better ways to do the same.
> I started with "(i end (- i 1)" because it gave me the list sorted from
> start to end.
It seems to be discussed at least once a week. Some searching would give
you many threads concerned with exactly that. But yes, there are better
ways:
(defun enumerate (start end)
(loop for i from start to end collecting i))
Or, if you use ITERATE (which I recommend):
(defun enumerate (start end)
(iter (for i from start to end)
(collect i)))
Cheers,
Maciej
In article
<····································@m34g2000hsf.googlegroups.com>,
vijay <········@gmail.com> wrote:
> I have written a function that creates a list containing integers from
> a start value to an end value. It looks like:
>
> (defun enumerate (start end)
> (setq x nil)
> (do ((i end (- i 1)))
> ((< i start) x)
> (setq x (cons i x))
> )
> )
A few remarks:
* x is not introduced as a variable. You can't
just use a variable like that. Local variables
can be introduced with LET and LET*.
* (SETQ x (cons i x)) is shorter written as (push i x)
* Choose a better name than x .
* don't use a formatting style with parentheses on
their own lines. Some people use that, but generally
most think it is a waste of space.
* you can use a documentation string.
(defun enumerate (start end)
"creates a list of numbers from start upto end"
(let ((result-list nil))
(do ((i end (- i 1)))
((< i start) result-list)
(push i result-list))))
Another variation:
(defun enumerate (start end)
"creates a list of numbers from start upto end"
(do ((result-list nil)
(i end (- i 1)))
((< i start) result-list)
(push i result-list)))
DO can create both RESULT-LIST and I as variables.
This gets us to the next version:
(defun enumerate (start end)
"creates a list of numbers from start upto end"
(do ((result-list nil (cons i result-list))
(i end (- i 1)))
((< i start) result-list)))
Above moves the updating of the result-list
to the update-form of the variable RESULT-LIST.
The shortest version you'll get with the LOOP macro:
(defun enumerate (start end)
"creates a list of numbers from start upto end"
(loop for i from start upto end collect i))
>
> I am a newbie and was wondering if there are better ways to do the
> same. I started with "(i end (- i 1)" because it gave me the list
> sorted from start to end.
>
> Thank you for your help.
vijay <········@gmail.com> writes:
> I have written a function that creates a list containing integers from
> a start value to an end value. It looks like:
>
> (defun enumerate (start end)
> (setq x nil)
setq is not the right way to introduce a variable. Use let instead.
> (setq x (cons i x))
This setq idiom is common enough that it has its own name. (push i x)
> )
> )
This is just a waste of perfectly good vertical space.
> I am a newbie and was wondering if there are better ways to do the
> same. I started with "(i end (- i 1)" because it gave me the list
> sorted from start to end.
Good idea.
Personally, I like loop, so I would write it as
(defun enumerate (start end)
(loop for i from start to end
collect i))
...Peder...
--
I wish a new life awaited _me_ in some off-world colony.
vijay <········@gmail.com> writes:
> I have written a function that creates a list containing integers from
> a start value to an end value. It looks like:
>
> (defun enumerate (start end)
> (setq x nil)
> (do ((i end (- i 1)))
> ((< i start) x)
> (setq x (cons i x))
> )
> )
>
> I am a newbie and was wondering if there are better ways to do the
> same. I started with "(i end (- i 1)" because it gave me the list
> sorted from start to end.
Don't listen to loopers! Just forget SETQ.
(defun enumerate (start end)
(when (< start end)
(cons start (enumerate (1+ start) end)))) ; is the nicest.
(defun enumerate (start end)
(labels ((enum (current result)
(if (<= start current)
(enum (1- current) (cons current result)) ; tail call
result)))
(enum (1- end) '()))) ; is the second best, as efficient as loop on normal implementations.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
;This is a bad solution forgeth that you see it
(defun enumerate (start end)
(let (res (diff (- end start)))
(dotimes (i (1+ (- end diff)) (nreverse res))
(push (+ i diff) res))))
cheers
Slobodan