Bind a variable based on another variable inside a condition / loop / let

Question

I am going through the tutorial at Lisp Tutor Jr, on my own. After completing an assignment on recursion, I started thinking about expanding the numeric range to negative numbers.

If I bind as in the following code, it gets adjusted together with x.

1) Do I understand correctly that using defconstant inside the function is wrong?

2) How would I bind a minimal variable based on x, in this case attempted via (- x).

(defun list-odd-range(x)
  (let ((neg (- x)))
    (cond 
          ((< x neg) nil) 
          ((oddp x)(cons x (list-odd (1- x))))
        (t (list-odd (1- x))))))

The function as-is returns

(list-odd 5)=>(5 3 1)

I would like to bind neg once, as (- x) and have the function return a range from positive to negative x:

(list-odd 5)=>(5 3 1 -1 -3 -5)

Binding with an integer, such as the following bit, works: (let ((neg -5))

What is the correct way to have it defined in relation to x, such as (- x) ?

Svante · Accepted Answer · 2020-02-20 21:23:27Z

1

1) Defconstant doesn't really make sense in a function. It defines a global constant, which is constant. If you ever call the function again, you either provide the same (eql) value and have no effect, or a different value, which is illegal.

2) As you observed, the inner call doesn't know anything about the outer environment except what is passed as an argument. You can either keep it at that and add the remaining part after the return of the inner call (I elide checking the inputs in the following, you'd need to make sure that x is always a nonnegative integer):

(defun odd-range (x)
  (cond ((zerop x) ())
        ((evenp x) (odd-range (1- x)))
        (t (cons x
                (append (odd-range (1- x))
                        (list (- x)))))))

Or you can pass the end number along as an additional argument:

(defun odd-range (start end)
  (cond ((< start end) ())
        ((evenp start) (odd-range (1- start) end))
        (t (cons start
                 (odd-range (1- start) end)))))

This would have the benefit of giving the caller free choice of the range as long as end is smaller than start.

You can also pass along the constructed list so far (often called an accumulator, abbreviated acc):

(defun odd-range (start end acc)
  (cond ((< start end) (reverse acc))
        ((evenp start) (odd-range (1- start) end acc))
        (t (odd-range (1- start) end (cons start acc)))))

This conses to the front of the list while accumulating and only reverses the result at the end. This avoids walking the accumulated list at every step and is a big improvement on running time. It also moves the recursive call into tail position so that the compiler may produce code that is equivalent to a simple loop, avoiding stack limits. This compiler technique is called tail call elimination or tail call optimization (TCO).

Since Common Lisp compilers are not required to do TCO, it is good style to write loops actually as loops. Examples:

(defun odd-range (start)
  (do ((x start (1- x))
       (end (- start))
       (acc ()
            (if (oddp x)
                (cons x acc)
                acc)))
      ((<= x end) (reverse acc))))

(defun odd-range (x)
  (let* ((start (if (oddp x) x (1- x)))
         (end (- start)))
    (loop :for i :from start :downto end :by 2
          :collect i)))

answered Feb 20, 2020 at 21:23

Svante

51.8k11 gold badges84 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lambda Over a year ago

Thank You for providing such a detailed reply, @Svante I have reviewed loop and came up with the following. Is this correct? (defun odd-range-looped (y) (loop for x from (- y) to y if (oddp x) collect x))

Svante Over a year ago

It will give ascending numbers instead of descending as in your question, but otherwise yes, looks good.

Collectives™ on Stack Overflow

Bind a variable based on another variable inside a condition / loop / let

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related