help understanding a simple function

[Philipp]

In general, you can write an iterative algorithm to substitute a recursive and vice versa.
It's up to you...
But if you want to learn about recursion the answer is 'yes, you need to!'

[sycamorex]

hmm, I must say it's not easy for me. Let's start with:

Check if a list contains only numbers (assume it's not empty).

First I wrote the following:

Code: Select all

CL-USER> (defun numbersp (lst)                                                                           
           (cond                                                                                         
             ((numberp (car lst)) 'car-is-a-number)                                                       
             (nil)))                                                                                     
NUMBERSP                                                                                                 
CL-USER> (numbersp '(1 2 3))                                                                             
CAR-IS-A-NUMBER                                                                                           
CL-USER> (numbersp '(a 2 3))                                                                             
NIL     

So I thought that I'll add recursion by:

Code: Select all

CL-USER> (defun numb (lst)                                                                               
           (cond                                                                                         
             ((numberp (car lst)) (numb (cdr lst)))                                                       
             (nil)))     


But here it returns NIL in all cases:(

/me confused

[Philipp]

Ok, you're on the right way, but:

First, think about the cases you need to express.
Though we defined the incoming list to be not nil, we'll find nil once we looked at each element (and found only numbers).
We want to use the two basic cases when working with lists:
If the car is nil, return ...
Else:
If the car is a number, return ...
Else, return ...

You can express this with a cond-form to avoid nested if's, as you tried, but then you should look at the rules of the cond-form again.
(Look here http://www.lispworks.com/documentation/ ... m_cond.htm, here http://www.cs.cmu.edu/Groups/AI/html/cl ... 0000000000 or in LoL).
cond returns nil by default if none of the test-forms evaluates to T.

[sycamorex]

Thanks a lot. The moment I read your post I realised my mistake. Of course, once the list is empty, it evaluates to NIL.

Code: Select all

(defun numbersp (lst)                                                                           
           (cond                                                                                         
             ((null lst) T)                                                                               
             ((numberp (car lst)) (numbersp (cdr lst))))) 

It seems to work fine. Is that correct?

Time to look at another of the tasks.

[virex]

Nearly. The current function returns T for an empty list, but an empty list obviously does not consist of only numbers, as it consists of nothing at all. So you need to handle the case of the function being called initially on an empty list as well.

[Philipp]

For simlicity, the task was defined to work with not-empty lists only. So very good!

By the way, though cond returns nil by default, I think it's convention to always state the 'fall-through'-case in cond, like so:

Code: Select all

(defun numbersp (lst)                                                                           
           (cond                                                                                         
             ((null lst) T)                                                                               
             ((numberp (car lst)) (numbersp (cdr lst)))
             (t nil)))


This way it's clear that you didn't just forgot a case.

[sycamorex]

For simlicity, the task was defined to work with not-empty lists only. So very good!

By the way, though cond returns nil by default, I think it's convention to always state the 'fall-through'-case in cond, like so:

Code: Select all

(defun numbersp (lst)                                                                           
           (cond                                                                                         
             ((null lst) T)                                                                               
             ((numberp (car lst)) (numbersp (cdr lst)))
             (t nil)))


This way it's clear that you didn't just forgot a case.

Thanks a lot, both of you.
I think I need to pick you brains about the following. Just to make sure. I don't want to skip this bit. Is my understanding correct?
We have got three conditions here:
1. ((null lst) T) - After we've gone through the list, the list is empty. If the list is empty, return T, otherwise the numbersp function returns NIL in all cases (even if the list contains only numbers)
2. ((numberp (car lst)) (numbersp (cdr lst)))) - If (car lst) is a number, call the numbersp function feeding it (cdr lst) to recursively go through other elements.
3. (t nil))) - If neither 1 nor 2 is true (ie. an element of the list is not a number) return NIL. As it was mentioned above, cond returns nil (if none of the conditions have been met) by default, so we added it only as good practice.

I think slowly but steadily I'm getting there. Thank you for your help.

[sycamorex]

Ok, I think I got another one. The problem is that it is NOT done recursively - I've got a sneaking suspicion that's not the way it's meant to be solved.

Extract the numbers!

Code: Select all

(defun numbers (lst) ...)
> (numbers '(1 2 a b 3 c 4 1)) => (1 2 3 4 1)


Code: Select all

(defun numbers (lst)                                                                             
           (labels ((is-number (elt)                                                                     
                    (numberp elt)))                                                                       
             (delete-if-not #'is-number lst))) 

I modified the "objects-at" function from the Land of Lisp.

The last stab at trying to do it in a purely recursive way was like that:

Code: Select all

 (defun numbers (lst)                                                                             
           (setq new-lst '())                                                                             
           (cond                                                                                         
             ((numberp (car lst)) (cons (car lst) new-lst) (numbers (cdr lst)))                           
             ((null lst) new-lst)                                                                         
             (t (numbers (cdr lst)))))           

Obviously, it doesn't work. My understanding was:
1. Create a new list (new-lst)
2. If (car lst) is a number:
a) Add (car lst) to new-lst
b) and call numbers (cdr lst)
3. If I've gone over the whole list (ie null lst)), return the new-lst list.
4. If it's true but didn't meet condition 2 and 3, call numbers (cdr lst)

Where am I wrong? Is my logic wrong or just my implementation of it?
Thanks

[virex]

Well, for one, assuming that new-lst is a variable defined outside of the function, you're setting it to '() every time you call the function, so you never actually build a full list. the second problem is that you're using cons. Cons is a non-destructive function, meaning that (cons (car lst) new-lst) won't actually alter new-lst, but instead produce a new list, which is immediately discarded. There are 2 ways to get the effect you want. You either use push or (setq new-lst (cons (car lst) new-lst), both of which essentially do the same. If you do this you'll also note that you're building the list in reverse, so you'll have to use reverse (or it's destructive brother nreverse) to get it back in the right order. Note that these also do not alter new-lst, but return a new list that is a reversed variant of new-lst.

Now, to solve the first problem, you either need to make it so that new-lst is shared between the different instances of numbers (a so-called closure, closing over an external value) using

Code: Select all

(let ((new-lst (list)))
    (defun numbers (lst) ...)


but that has the problem that you need to null the list by hand (or using a wrapper function) every time you call numbers. A better way would be to use labels to define a recursive function local to numbers and use that for recursion:

Code: Select all

(defun numbers (lst)
    (let ((new-lst (list)))
        (labels ((list-walker (list) ....))
            (list-walker lst)
            (nreverse new-lst)) ;assuming you're using push or cons to build your list you need to reverse it when you're done

However, while using a closure is a good idea in this case, it misses a central point of recursion and that is how to handle return values. We could modify your specification as following:
1.) If the car of our list is a number, make a list of all numbers in the remaining list and cons them together.
2.) else, if there are still elements in the list beyond this one, return all numbers in that list
3.) else, return nil.

This takes advantage of the fact that consing to nil will result in a fresh list consisting of 1 element, the thing you consed to nil. I'll let you figure out the resulting definition yourself.

On a side note, don't use setq to introduce new variables, it's not common lisp compliant. To see what exactly happens if I run your function I would have to track down an implementation that does support this idiom instead of using the one I usually use. Used defvar to introduce globally-bound, special* variables or let to introduce local, lexical* variables.

*The difference between lexical and special is best illustrated with an example:

Code: Select all

(defvar *a* 3) ;*a* is now defined as special

(defun test-a () *a*)

(test-a) ;This yields 3

(let ((*a* 5)) ;Even though we use let, *a* was already special and will not become lexical
    (test-a) ;Because *a* is special, we can shadow it at run-time with let, and the effect will propagate to functions defined earlier

(let ((b 4)) ;b is now lexical
    (defun test-b () b)) ;Since b is lexical, it's value will be locked in when we compile this function

(test-b) ;this yields 4

(let ((b 6))
    (test-b)  ;this also yields 4, because due to b's lexical nature, we cannot shadow it any more.

In essence, special variables behave like global variables in other languages, while lexical variables behave like local variables. This isn't perfectly correct of course, defining 2 functions that refer to the same lexical variable and you have a "local" variable that isn't local to either function, but it helps to think like that. Also if you really need to, you can use (declare (special variable)) directly after a let-form's variable definition to tell the compiler that variable is special, which allows shadowing, but prevents outside access since there is no global symbol associated with the variable, so you have a special local variable then.

[Paul]

Code: Select all

(defun numbers (lst)                                                                             
           (labels ((is-number (elt)                                                                     
                    (numberp elt)))                                                                       
             (delete-if-not #'is-number lst))) 

Just do (delete-if-not #'numberp lst) -- is-number serves no purpose here. (But please name your argument "list" rather than "lst")