stuck

Discussion of Common Lisp
burton
Posts: 10
Joined: Sat Aug 28, 2010 6:05 pm

stuck

Post by burton » Sat Aug 28, 2010 6:15 pm

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

Code: Select all

(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 "

Code: Select all

" tags - nuntius]

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: stuck

Post by nuntius » Sat Aug 28, 2010 9:47 pm

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.

burton
Posts: 10
Joined: Sat Aug 28, 2010 6:05 pm

Re: stuck

Post by burton » Sun Aug 29, 2010 8:27 am

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

Duke
Posts: 38
Joined: Sat Oct 17, 2009 10:40 pm
Contact:

Re: stuck

Post by Duke » Sun Aug 29, 2010 12:51 pm

Edit: missed a crucial detail. Tsk.
Last edited by Duke on Sun Aug 29, 2010 3:41 pm, edited 1 time in total.
"If you want to improve, be content to be thought foolish and stupid." -Epictetus

s-imp
Posts: 11
Joined: Sat Aug 28, 2010 5:04 am

Re: stuck

Post by s-imp » Sun Aug 29, 2010 3:25 pm

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

Code: Select all

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

burton
Posts: 10
Joined: Sat Aug 28, 2010 6:05 pm

Re: stuck

Post by burton » Sun Aug 29, 2010 4:57 pm

hmmmm, recursively....
pretty elegant!

s-imp
Posts: 11
Joined: Sat Aug 28, 2010 5:04 am

Re: stuck

Post by s-imp » Sun Aug 29, 2010 5:47 pm

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.

Duke
Posts: 38
Joined: Sat Oct 17, 2009 10:40 pm
Contact:

Re: stuck

Post by Duke » Sun Aug 29, 2010 6:16 pm

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))
"If you want to improve, be content to be thought foolish and stupid." -Epictetus

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: stuck

Post by findinglisp » Sun Aug 29, 2010 7:10 pm

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.)
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

s-imp
Posts: 11
Joined: Sat Aug 28, 2010 5:04 am

Re: stuck

Post by s-imp » Sun Aug 29, 2010 8:24 pm

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.

Post Reply