by smithzv » Sun Dec 11, 2011 5:23 am
Yes and no. I am perhaps spoiling the pedagogy here (which I take is the essence of the exercise), but just so we're clear, I talking about instead of computing the length of the list and then seeing it equals 1, just checking the CDR of the list to see if it is NIL (which works out to be the same). I am not sure I know of compilers that will do this optimization. Perhaps a Haskell compiler can? I am almost certain that no Common Lisp compilers do this, so that's something to keep in mind. In Paul Graham's books, one of the first examples he gives is a function that basically does this test efficiently (it's in On Lisp and probably Ansi CL).
Common Lisp has a feature called compiler macros. They are a pretty cool feature that allows users to write these kinds of source level optimizations. However, so you don't shoot yourself in the foot, you can only define these kind of optimization for user defined symbols (i.e. functions like EQUAL are off limits). You can get around this, if you really want. Point is, you can implement this optimization yourself, but it is pretty narrow in applicability.
BTW, I just tried to write this compiler macro myself and succeeded in shooting myself in the foot.
Regarding your second post: your exit form makes no sense. How is it ever true? Given a list L, with length x, how is it ever true that x=x-n unless n=0? That is what you have written.
Also, you might get more interest if you properly formatted your code. It is hard to read they way it is written.