Subject: Re: New to Common Lisp; range function
From: rpw3@rpw3.org (Rob Warnock)
Date: Sun, 26 Aug 2007 22:31:49 -0500
Newsgroups: comp.lang.lisp
Message-ID: <AJOdnYv7qvU42E_bnZ2dnUVZ_hisnZ2d@speakeasy.net>
Rob Hoelz  <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@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607