Discussion of Common Lisp
MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

I tried my first LISP today. I got stuck trying to build a list of all intermediate values of the function 'c-series':

Code: Select all

``````(defun even (n) (= (mod n 2) 0))
(defun square (x) (* x x))

(defun c-series (n a)
(if (= n 0)
a
(if (even n)
(log (c-series (- n 1) a))
(square (c-series (- n 1) a))
)
)
)
``````
What if I wanted to print out a finite list of all the intermediate c-series values?
A list containing

Code: Select all

``````(let (a 5)
((c-series (1 a)) (c-series (2 a)) (c-series (3 a)) ...
)
``````
Of course, with actual reuse of the previous results.
I just can't seem to find a way to fit the recursion in there. (I've played with Haskell before and just can't get my head around how to implement this type of recursion in Lisp). Do I really need a helper function? Thanks for helping me on my way,

MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

### Re: question about recursion (easy)

Ok, I managed to do it with the 'dotimes' macro:

Code: Select all

``````(defun cseries-list (n a)
(let ((l (list a)))
(dotimes (i n)
(if (even i)
(push (log (car l)) l)
(push (square (car l)) l)))
(nreverse l)))``````
Is this the 'Lisp' way?

AlexPaes
Posts: 21
Joined: Sat Jun 28, 2008 3:38 am
Location: Lisbon, Portugal

### Re: question about recursion (easy)

I think i'd do something like:

Code: Select all

``````(defun cseries-list (n a)
(loop for i from 1 upto n collect (c-series i a)))
``````
Not sure if that's more lispy than what you provided, but has the advantage of using the c-series function thus better code re-use. One sidenote is that you don't need to define the even function since there's already a evenp function that you can use test if some argument is even.
CL-USER> (setf *boss* (make-instance 'smart-person))
NIL
CL-USER>

MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

### Re: question about recursion (easy)

But this recalculates a large number of recursive branches redundantly, doesn't it? Or is there some magic goign on there I'm not aware of?

reuben.cornel
Posts: 7
Joined: Sun Jun 29, 2008 9:48 am
Location: Sterling, Virginia, USA
Contact:

### Re: question about recursion (easy)

I wrote up two functions that do the same thing, except that for the first one you need to reverse the result.

Code: Select all

``````(defun reverse-recursive-c-series(n a)
(if (zerop n)
(list a)
(let ((return-a (reverse-recursive-c-series (- n 1) a)))
(cond ((evenp (- n 1)) (cons  (log (first return-a)) return-a))
((oddp  (- n 1)) (cons  (square (first return-a)) return-a))))))
``````
Same function where you don't need to reverse the result

Code: Select all

``````(defun recursive-c-series(n a)
(if (zerop n)
(list a )
(let ((return-a (recursive-c-series (- n 1) a)))
(cond ((evenp (- n 1)) (append  return-a (list (log (first (last return-a))))))
((oddp  (- n 1)) (append return-a (list (square (first (last return-a))))))))))
``````

dmgenp
Posts: 13
Joined: Sat Jun 28, 2008 10:15 am

### Re: question about recursion (easy)

Haskell gives lazy lists and memoization for them out-of-the-box.

for common lisp, you can use this library:

http://cl-heresy.sourceforge.net/Heresy.htm

Code: Select all

``````The clichÃ©d Fibonacci example:

(Request 1000000th element in Fibonacci sequence using self-referencing list)

(nth/ 1000000
(self-ref-list/ fib (list*/ 1 1 (map/ #'+ fib (tail/ fib)))))

; self-ref-list internally memoized (to allow order-n solution); but with deferred creation (until extract time) to prevent storage bloat by holders of list reference.
``````

dmgenp
Posts: 13
Joined: Sat Jun 28, 2008 10:15 am

### Re: question about recursion (easy)

and here's my version of the function in question:

Code: Select all

``````;; generate a list of first n C-series values
(defun c-series-list (n a)
(when (zerop n) (return-from c-series-list))
(labels
((c-s (n a)
(if (= 1 n)
(list a)
(let* ((rest (c-s (- n 1) a))
(prev (car rest)))
(cons (if (evenp n)
(log prev)
(* prev prev))
rest)))))
(nreverse (c-s n a))))
``````
and the loop-based version:

Code: Select all

``````(defun c-series-list (n a)
(loop for i from 2 to n
with result = (list a)
for prev = (first result)
do (push (if (evenp i)
(log prev)
(* prev prev))
result)
finally (return (nreverse result))))
``````

MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

### Re: question about recursion (easy)

Thanks guys, for the examples.
I now understand better how to implement left-hand side in Lisp with pure recursion instead of loops.

danb
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US
Contact:

### Re: question about recursion (easy)

MaartenM wrote:I now understand better how to implement left-hand side in Lisp with pure recursion instead of loops.
Here's another way. It avoids both appending and reversing.

Code: Select all

``````(defun c-series (n a)
(labels
((c-cons (i x)
(unless (> i n)
(cons x (c-cons (+ i 1)
(if (oddp i) (log x) (* x x)))))))
(c-cons 0 a)))
``````