Discussion of Common Lisp

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?
MaartenM

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

### 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>

AlexPaes

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

### 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?
MaartenM

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

### 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))))))))))`
reuben.cornel

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

### 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))))`
dmgenp

Posts: 13
Joined: Sat Jun 28, 2008 10:15 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.
MaartenM

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

### 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)))`
danb

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