stuck

hi, trying to write a function that counts odd numbers in a list:
so far

(defun odd-count(lst)

  (do ((i 0 (+ i 1)
        (sum 0))

((>(+ 1 i) (length lst)

   (if (oddp lst)
       (+ 1 sum)

??not sure what to do from this point??
could somebody help?

[ed note: added "

" tags - nuntius]

If you're looping over a list, the DOLIST macro is your friend. Also note that (+ 1 sum) calculates a new value but doesn't store it anywhere. Use setf or incf.

ok, so dolist. it doesn't need anything (stop condition, etc) other than the (lst), right? and it will know when the list ends.
where do i initialize the variable sum?right after the dolist?

(dolist (sum (lst)
(sum 0))
(if (t(oddp lst))
(setq sum (+ 1 sum)
(
)

im not sure..

Edit: missed a crucial detail. Tsk.

I'm just a newbie, how is this for a recursive solution:

(defun odd-count (lst)
  (if (null lst)
       0
       (+ (if (oddp (first lst)) 1 0)
            (odd-count (rest lst)))))

Is there a simpler way to do this recusively?

hmmmm, recursively....
pretty elegant!

I heard that recursion was a lispy way of doing things, but there could be a better way. I'm not sure if it comes with a performance cost. Perhaps one of the pros can chime in. I'm still trying to get my head around what tail recursion is.

s-imp wrote:I heard that recursion was a lispy way of doing things, but there could be a better way. I'm not sure if it comes with a performance cost. Perhaps one of the pros can chime in. I'm still trying to get my head around what tail recursion is.

Recursion isn't necessarily "more Lispy". Lisp is a multi-paradigm language, so you can do procedural or OOP if you want. IMO, "idiomatic" Lisp has more to do with transforming code, and building the language from bottom-up so that you can express a solution in whatever language is most suitable to the problem.

Recursion, in my limited experience, is always slower than iterating... maybe compiling or using (declare (optimize (speed 1))) would even things up, but I've never tested. Still, if your recursion is the same as the iteration, but with a tail-call and accumulator, I think you can expect a penalty. Again, I could be wrong, and I don't know the whole story.


Tail recursion is when the last call in the function is the function itself. For example, a function that is not tail-recursive might end like this: (cons foo (rec-func (cdr lst)))

In this case, the stack has to unwind before the first iteration can return, which means that for every iteration, the interpreter has to remember all the stack frames that have executed so far.


Here's a more concise (and probably extremely slow) way to do odd counting: (length (remove-if-not #'oddp lst))

Duke wrote: Tail recursion is when the last call in the function is the function itself. For example, a function that is not tail-recursive might end like this: (cons foo (rec-func (cdr lst)))

This is true as stated, but can be generalized. To be a bit more precise, a tail call does not have to be a recursive call to the same function. A tail call is any call where the calling function immediately returns after invoking the callee; the return value of the caller is the return value of the callee. In this case, there is little value in setting up a stack frame when invoking the callee; the caller can jump to the callee and whatever value the callee returns is returned to the code that invoked the caller. The great insight around tail calls was that they allowed compilers to optimize with a simple goto/jmp rather than creating stack frames. This means that a function that calls itself from a tail call (tail recursion) will never run out of stack space. The tail call is effectively a loop written in recursive syntax. But this works when you don't call yourself, too.

If you want to see a great example of this put to use, see Fig. 1 in this paper:
http://www.cs.brown.edu/~sk/Publication ... /paper.pdf

(This is Shriram Krishnamurthi's work on state machines in Scheme that came from his famous Swine Before Perl talk.)

Yeah, I thought about 'length', but I knew to avoid creating cons cells for a new list as you do get a performance penalty for it.

Thank you both for the info on tail-recursion. So my function is not tail recursive (as it calls #'+ last). I traced it and then disassembled it to see what was going on. Very interesting.

burton wrote:(dolist (sum (lst)
(sum 0))
(if (t(oddp lst))
(setq sum (+ 1 sum)
(
)

im not sure..

Close, but there are still a few oddities in your code.

DOLIST doesn't take the same parameter list as DO. The function prototype is (DOLIST (var list [result]) body), where the result-form is optional. Use LET to create a counter outside the loop: (let ((count 0)) ...). Then iterate over each item in a list: (dolist (item list) ...).

I'm not sure what the first clause in your IF does. It should look something like (if (oddp item) (incf count)), or preferably use WHEN for IF statements with no "else" clause.


[OT]: Recursion is the "Schemey" way to write code. It is not so popular in common lisp.

Got'cha

s-imp wrote:Yeah, I thought about 'length', but I knew to avoid creating cons cells for a new list as you do get a performance penalty for it.

Thank you both for the info on tail-recursion. So my function is not tail recursive (as it calls #'+ last). I traced it and then disassembled it to see what was going on. Very interesting.

It should also be said that Common Lisp makes no guarantees around tail recursion; implementations are not required to be properly tail recursive. In practice, some are, but that's really outside the dictum of the standard. That stands in strong contrast to Scheme where every conforming implementation to RxRS is required to be properly tail recursive. As a result, Scheme tends to rely much more heavily on tail recursion to implement loops, whereas CL has a stronger set of iteration constructs (e.g., DO, DO*, DOLIST, LOOP, etc.).

Here are 5 ways of doing it. I added timing for SBCL on my computer without tweaking any optimization stuff.

;; using a reduction
(defun odd-count1 (list) (reduce #.(lambda (acc i) (if (oddp i) (1+ acc) acc)) list :initial-value 0))

;; using 'loop'
(defun odd-count2 (list) (loop for i in list counting (oddp i)))

;; Using recursion
(defun odd-count3 (lst)
  (if (null lst)
      0
      (+ (if (oddp (first lst)) 1 0)
	 (odd-count3 (rest lst)))))

;; using tail recursion
(defun odd-count4 (lst count) (if (null lst) count (odd-count4 (cdr lst) (if (oddp (car lst)) (1+ count) count))))

;; using destructive updates and jumps
(defun odd-count5 (lst)
  (let ((count (the fixnum 0)))
    (tagbody :start (when lst (when (oddp (car lst)) (incf count)) (setf lst (cdr lst)) (go :start)))
    count))

(defvar *data* (loop repeat 1024 collecting (random 256)))

(time (dotimes (i 1000)(odd-count1 *data*)))    ;; 0.038 seconds
(time (dotimes (i 1000)(odd-count2 *data*)))    ;; 0.023 seconds
(time (dotimes (i 1000)(odd-count3 *data*)))    ;; 0.048 seconds
(time (dotimes (i 1000)(odd-count4 *data* 0)))  ;; 0.031 seconds
(time (dotimes (i 1000)(odd-count5 *data*)))    ;; 0.023 seconds

Warren Wilkinson wrote:Here are 5 ways of doing it. I added timing for SBCL on my computer without tweaking any optimization stuff.

(time (dotimes (i 1000)(odd-count1 *data*)))    ;; 0.038 seconds
(time (dotimes (i 1000)(odd-count2 *data*)))    ;; 0.023 seconds
(time (dotimes (i 1000)(odd-count3 *data*)))    ;; 0.048 seconds
(time (dotimes (i 1000)(odd-count4 *data* 0)))  ;; 0.031 seconds
(time (dotimes (i 1000)(odd-count5 *data*)))    ;; 0.023 seconds

The LOOP macro typically expands into a TAGBODY/GO under the hood, which explains why its performance is similar. If I remember right, SBCL also implements proper tail recursion, so ODD-COUNT4 also does well. Real recursion and REDUCE involve lots of true function calls, so there's higher overhead there.

IMO, LOOP is almost always a win and I tend to use it in preference to other styles, unless the problem screams for recursion (whether tail-recursion or not).

That said, find your style. Lisp allows a lot of different styles. Most code is not performance-critical.

-- Dave