Hello everyone,
I'm new to Common Lisp, but not to functional programming (I've used ML
and Haskell) or Lisp (I've used Scheme). My first question for this
newsgroup is whether or not a range function exists in Common Lisp.
I've looked around, but couldn't seem to find anything, so I thought
I'd consult you, the experts. In case range is the incorrect name for
this function, I'll clear it up with a Lisp definition:
(defun range (start end)
(if (> start end)
nil
(cons start (range (+ start 1) end))))
Thanks!
-Rob
Rob Hoelz <·····@wisc.edu> wrote:
+---------------
| I'm new to Common Lisp, but not to functional programming (I've used ML
| and Haskell) or Lisp (I've used Scheme). My first question for this
| newsgroup is whether or not a range function exists in Common Lisp.
| I've looked around, but couldn't seem to find anything, so I thought
| I'd consult you, the experts. In case range is the incorrect name for
| this function, I'll clear it up with a Lisp definition:
|
| (defun range (start end)
| (if (> start end)
| nil
| (cons start (range (+ start 1) end))))
+---------------
There's nothing in the CL stantard per se, but the function you
describe would, in CL, commonly be done using LOOP to avoid possible
stack overflow for *large* values of (- END START):
> (defun range (start end)
(loop for i from start below end collect i))
RANGE
> (range 5 17)
(5 6 7 8 9 10 11 12 13 14 15 16)
>
I deliberately changed the contract of RANGE to *exclude* the END
value. This is because many, many standard sequence functions in CL
take :START & :END keyword arguments which designate "bounding indices"
defining half-open intervals in which the upper limit is *not* included
in the resulting designated subsequence. [See the CLHS Glossary entries
for "bounded", "bounding index", & "bounding index designator", all near
<http://www.alu.org/HyperSpec/Body/glo_b.html#bounding_index_designator>.]
It is widely recognized that using half-open bounding indices is both
less error-prone and more convenient, especially when combining ranges.
E.g., if [s1,e1) and [s2,e2) are two ranges, and e1 == s2, then [s1,e2)
is the range which exactly describes their concatenation. Dijkstra once
wrote a nice little paper about this:
http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
"Why numbering should start at zero"
Edsger W. Dijkstra (August 1982)
A related function to your RANGE is one often called IOTA, probably
from the index generator function in APL. While APL's IOTA takes only
one argument, the signature is often extended to provide more features
by using CL's optional arguments, as in my own personal version:
> (defun iota (count &optional (start 0) (step 1))
(loop repeat count for i from start by step collect i))
IOTA
> (iota 12)
(0 1 2 3 4 5 6 7 8 9 10 11)
> (iota 12 5)
(5 6 7 8 9 10 11 12 13 14 15 16)
> (iota 12 5 10)
(5 15 25 35 45 55 65 75 85 95 105 115)
>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> Rob Hoelz <·····@wisc.edu> wrote:
> +---------------
> | I'm new to Common Lisp, but not to functional programming (I've used ML
> | and Haskell) or Lisp (I've used Scheme). My first question for this
> | newsgroup is whether or not a range function exists in Common Lisp.
> | I've looked around, but couldn't seem to find anything, so I thought
> | I'd consult you, the experts. In case range is the incorrect name for
> | this function, I'll clear it up with a Lisp definition:
> |
> | (defun range (start end)
> | (if (> start end)
> | nil
> | (cons start (range (+ start 1) end))))
> +---------------
>
> There's nothing in the CL stantard per se, but the function you
> describe would, in CL, commonly be done using LOOP to avoid possible
> stack overflow for *large* values of (- END START):
>
> > (defun range (start end)
> (loop for i from start below end collect i))
>
> RANGE
> > (range 5 17)
>
> (5 6 7 8 9 10 11 12 13 14 15 16)
> >
>
> I deliberately changed the contract of RANGE to *exclude* the END
> value. This is because many, many standard sequence functions in CL
> take :START & :END keyword arguments which designate "bounding indices"
> defining half-open intervals in which the upper limit is *not* included
> in the resulting designated subsequence. [See the CLHS Glossary entries
> for "bounded", "bounding index", & "bounding index designator", all near
> <http://www.alu.org/HyperSpec/Body/glo_b.html#bounding_index_designator>.]
>
> It is widely recognized that using half-open bounding indices is both
> less error-prone and more convenient, especially when combining ranges.
> E.g., if [s1,e1) and [s2,e2) are two ranges, and e1 == s2, then [s1,e2)
> is the range which exactly describes their concatenation. Dijkstra once
> wrote a nice little paper about this:
>
> http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF
> http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
> "Why numbering should start at zero"
> Edsger W. Dijkstra (August 1982)
>
> A related function to your RANGE is one often called IOTA, probably
> from the index generator function in APL. While APL's IOTA takes only
> one argument, the signature is often extended to provide more features
> by using CL's optional arguments, as in my own personal version:
>
> > (defun iota (count &optional (start 0) (step 1))
> (loop repeat count for i from start by step collect i))
>
> IOTA
> > (iota 12)
>
> (0 1 2 3 4 5 6 7 8 9 10 11)
> > (iota 12 5)
>
> (5 6 7 8 9 10 11 12 13 14 15 16)
> > (iota 12 5 10)
>
> (5 15 25 35 45 55 65 75 85 95 105 115)
> >
I wrote this function for my numerical applications:
(defun num-sequence (&key (from nil from-given-p) (to nil to-given-p)
(by nil by-given-p) (length nil length-given-p)
(type 'double-float))
"Create a one-dimensional array which contains a sequence with the
given parameters. The parameters are checked for consistency. Two
values are returned, first the sequence (simple-array with type), then
the fourth parameter which was not given. Note: the sequence stops at
or before reaching \"to\", eg (num-sequence :from 0 :to 10 :by pi)
will stop end at (* 3 pi)."
(unless (= 3 (reduce #'+
(mapcar #'(lambda (x) (if x 1 0))
(list from-given-p to-given-p
by-given-p length-given-p))))
(error "Exactly 3 of from-given-p, to-given-p, by-given-p and length-given-p
need to be supplied."))
(flet ((seq (from by length)
"Create a sequence with given parameters."
(let* ((from (coerce from type))
(by (coerce by type))
(result (make-array length :element-type type)))
(dotimes (i length)
(setf (aref result i) (+ from (* i by))))
result)))
(cond
;; from, to, by => sequence, length
((not length-given-p)
(let* ((range (- to from))
(length (1+ (floor (/ range by)))))
(unless (plusp (* by range))
(error "by needs to have the same sign as (- to from)."))
(values (seq from by length) length)))
;; from, to, length => sequence, by
((not by-given-p)
(cond
((and (= from to) (= length 1))
(values (make-array 1 :element-type type :initial-element from) 0))
((and (/= from to) (> length 1))
(let ((by (/ (- to from) (1- length))))
(values (seq from by length) (coerce by type))))
(t (error "Mismatching from, to and length."))))
;; from, by, length => sequence, to
((not to-given-p)
(let ((result (seq from by length)))
(values result (aref result length))))
;; to, by, length => sequence, from
(t
(let ((from (- to (* by length))))
(values (seq from by length) (coerce from type)))))))
Rather baroque, but covers all the cases I use.
HTH,
Tamas
From: Klaus Schilling
Subject: Re: New to Common Lisp; range function
Date:
Message-ID: <87wsvhfe0d.fsf@web.de>
> There's nothing in the CL stantard per se, but the function you
> describe would, in CL, commonly be done using LOOP to avoid possible
> stack overflow for *large* values of (- END START):
would an iteration with "do" or a tail recursive formulation work?
Klaus Schilling
On Aug 27, 3:49 am, Klaus Schilling <···············@web.de> wrote:
> > There's nothing in the CL stantard per se, but the function you
> > describe would, in CL, commonly be done using LOOP to avoid possible
> > stack overflow for *large* values of (- END START):
>
> would an iteration with "do" or a tail recursive formulation work?
Common Lisp implementations aren't required to do tail recursion
optimization, unlike Scheme. (This is in part to ensure that you can
debug recursive functions.)
I like to use SERIES (described in CLtL2) for dealing with ranges, as
sometimes it's able to optimize away construction of the IOTA list.
mfh
Klaus Schilling wrote:
>> There's nothing in the CL stantard per se, but the function you
>> describe would, in CL, commonly be done using LOOP to avoid possible
>> stack overflow for *large* values of (- END START):
>
> would an iteration with "do" or a tail recursive formulation work?
Yes, but the loop version is simpler and easier to read.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
>>>>> "Pascal" == Pascal Costanza <··@p-cos.net> writes:
Pascal> Klaus Schilling wrote:
>>> There's nothing in the CL stantard per se, but the function you
>>> describe would, in CL, commonly be done using LOOP to avoid possible
>>> stack overflow for *large* values of (- END START):
>> would an iteration with "do" or a tail recursive formulation work?
Pascal> Yes, but the loop version is simpler and easier to read.
I like the series version:
(collect (scan-range :from start :below end))
The collect isn't necessary if you're going to operate on the result
with other series functions.
Ray
Klaus Schilling <···············@web.de> wrote:
+---------------
| > There's nothing in the CL stantard per se, but the function you
| > describe would, in CL, commonly be done using LOOP to avoid possible
| > stack overflow for *large* values of (- END START):
|
| would an iteration with "do" or a tail recursive formulation work?
+---------------
As others have said, tail recursion [or more generally,
tail call optimization] is not required in Common Lisp,
and is not possible in the general case in the presence of
dynamic variable bindings or exception handler bindings.[1]
Thus, lacking "safe-for-space" tail call optimization,
one can run into the stack overflow issue I mentioned.
-Rob
[1] Yes, yes, I know there have been some exotic ways
proposed to handle tail call optimization in the
presence of dynamic variable bindings, but I don't
know of any implementation that does so. And even
then exception handler bindings would mess things up.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607