Newbie questions - and yes, its homework :-(

Hi Everyone.

I need some very basic help. I am taking a course on lisp, but was up until now unable to attend (just moved to a new city (and continent. ha) and family and health issues :-S...) Now I just figured out that I have an assignment due this monday.

Now the last two days I have done my best to learn as much as possible, but I still feel quite far away from actually solving any of the problems. Maybe someone here can give me some pointers on how to think of them. Here is the first problem.
----------------------
(1) Write a recursiveLISP function add‐to‐odd which takes a list of numbers as its argument and returns the same list, but with 1 added to each of the odd numbers. So:
> (add‐to‐odd '(3 6 7 4 6 5))
(4 6 8 4 6 6)
----------------------

(I am using Allegro Common Lisp by Franz if thats of any relevence)

The way I figure this should work is something like this:

;; write function add-to-list with a list as input
(defun add-to-odd (mylist)
;;some sort of condition to brake the loop 
;;(my reasoning: when mylist is equal nil,
;; its an empy list and we have gone through all elements of the list)
	 (cond ((eql mylist nil) nil))
;;check whether the first number of the list is odd or even	
	 (cond (eql(mod (car mylist)) 1) )
	 ;; if its odd, add 1 
	 ((+ (car mylist) 1) ,
	 ;; repeat with the rest of the list
	 (add-to-odd (cdr mylist))))

Well anyway, this does not work - I am currently working myself through this lisp tutorial: http://www.gigamonkeys.com/book/ but so far it has not specifically been of help for my problems.

I am looking for
a) A tutorial which focuses on recursion
b) Someone to point out my mistakes in the code I posted (I realise its very foulty most of it is me just guessing what it should be like)
and
c) Someone who could describe to me how to think of this problem, what the structure of the solution should look like.


******

I am not trying to get you guys to do my homework for me. I just need to learn how to do this in three days and would apreceate all the help I get.

Thanks in advance

Regards

p.


(ah, also: is there any program you could recommend to me which is similar to the allegreo cl interpreter/compiler by franz which uses colour for marking comments etc. Something to make the code easyer to read, like notepad++ does?)

FKeeL wrote:a) A tutorial which focuses on recursion

A recursive approach is not the usual one in Common Lisp. Scheme uses recursion much more often. Although "raw" recursion perhaps not even that often, it mostly happens in contrived homework examples. Anyway, probably the best general introduction to this methodology of programming would be SICP, but that is more of a book that a tutorial. Being familiar with mathematical induction is generally helpful.

FKeeL wrote:b) Someone to point out my mistakes in the code I posted (I realise its very foulty most of it is me just guessing what it should be like)
and
c) Someone who could describe to me how to think of this problem, what the structure of the solution should look like.

You need only one cond form. Refer to the Hyperspec for reference on form syntax, while it is quite technical the syntax description is reasonably standard Backus-Naur Form.

In general, recursive problems have to be solved by separating the base condition from recursive conditions. In the simple case where there is only one, self-recursing function, in all non-base cases there must be a recursive call to itself. You have correctly identified the base case, which is an empty list. But note that you must call the function again in both other branches, when the list is not empty, for both odd and even number.

Most of the time when applying recursion you probably don't want to change anything, which means that a function works not by altering some state (like a list), but by constructing a new result. In this case, since the result is a list, you need the CONS function. You need to CONS a head (that is, a CAR) of list, appropriately modified, onto a tail (CDR) created by a recursive call to the tail of the argument.

FKeeL wrote:(ah, also: is there any program you could recommend to me which is similar to the allegreo cl interpreter/compiler by franz which uses colour for marking comments etc. Something to make the code easyer to read, like notepad++ does?)

The majority of people using Common Lisp use either commercial IDEs or Emacs with Slime.

FKeeL wrote:Maybe someone here can give me some pointers on how to think of them
----------------------
(1) Write a recursiveLISP function add‐to‐odd which takes a list of numbers as its argument and returns the same list, but with 1 added to each of the odd numbers. So:
> (add‐to‐odd '(3 6 7 4 6 5))
(4 6 8 4 6 6)
----------------------

OK, so what you need to do is build a list that's made up of the elements of the previous list, with the twist that you need to add one to elements with an odd value before adding them to the new list.
Where functional programming differs from the likes of C is that you don't have to create a separate variable, set its value to that of the source variable, manipulate the new variable, and then use the value. You can (and should) simply use the value returned by applying a function to the source variable. It's been described as thinking "inside-out" compared to procedural programming, which is an apt enough description.
mapcar is your friend here, though you can also use a recursive approach; in this case, it's largely a matter of taste.

FKeeL wrote:I am using Allegro Common Lisp by Franz if thats of any relevence

One of the nice things about Common Lisp is that it's standardised. There are things in each implementation that go beyond (or beside) the standard but, as long as you stick with the standard, the same code will normally work everywhere.

FKeeL wrote:

;; write function add-to-list with a list as input
(defun add-to-odd (mylist)
;;some sort of condition to brake the loop 
;;(my reasoning: when mylist is equal nil,
;; its an empy list and we have gone through all elements of the list)
	 (cond ((eql mylist nil) nil))
;;check whether the first number of the list is odd or even	
	 (cond (eql(mod (car mylist)) 1) )
	 ;; if its odd, add 1 
	 ((+ (car mylist) 1) ,
	 ;; repeat with the rest of the list
	 (add-to-odd (cdr mylist))))

It looks like you're confusing cond with if - they do similar things, but are used differently. cond is similar in spirit to switch, and can be very useful in replacing a complex nest of if-statements. You've also provided the function with no way to actually accumulate the new list.
Further things you'll want to investigate are the distinctions between eql, equal and =, and it's worth knowing about oddp and evenp.

In this case, it's a bit hard to guide you through such a relatively simple thing without actually writing it for you, but I'll try. Starting with cond:

(defun add-to-odd (lst acc)
  (cond
    ((first test)
        ;; end of the list; just return the accumulator
        acc)
    ((next test)
        (add-to-odd (cdr lst) (something involving the accumulator and (car lst))))
    ((last test)
        (add-to-odd (cdr lst) (something else involving the accumulator and (car lst))))))

For bonus points, once you have that working, you can collapse the "next" and "last" clauses into one, by working out which bits are common and where the difference between them actually lies. But now I'm just being annoying, because it takes a while to assimilate this aspect of functional programming.

Something that really takes a while to get your head around is that Common Lisp is a multiparadigm language: it's both fully object-oriented to a degree that Java isn't, it's great for functional programming, and you can still use a procedural style when it suits best. Personally, I mix-and-match them in a way that would make a purist's head spin.

FKeeL wrote:I am not trying to get you guys to do my homework for me. I just need to learn how to do this in three days and would apreceate all the help I get.

I like this approach.

FKeeL wrote:ah, also: is there any program you could recommend to me which is similar to the allegreo cl interpreter/compiler by franz which uses colour for marking comments etc. Something to make the code easyer to read, like notepad++ does?)

I'm a heretic whose idea of an IDE is Vim and a terminal with VIlisp connecting them. If you're comfortable with Vim, this may well suit you, though the setup of VIlisp may be a bit more elaborate than you're willing to go through if you don't expect to use the language much after this assignment.


Hope this helps,
James

Thanks for the help so far guys, I feel like I am - slowly - understanding lisp. Basically "cond" is used similar to guards (|) in Haskell then. So far so good.

@ james

I am trying to get your suggestion to work and again I am failing. Its not quite the solution required I think (because it asks for 2 inputs) but I guess once I have it figured out the way you suggest I can turn it into what they want...

EDIT: I have incorporated vivitrons suggestion (taking out the extra brackets)(didnt want a new post, for some reason). Now this is sort of working, just I am getting infinite recursion

(defun add-to-odd (lst acc)
  (cond
   ((null lst) acc)) 
    ((evenp (car lst)) ;if first number is even
        ((cons (car lst) acc)(add-to-odd (cdr lst) acc))) ;add that number to the acc list, restart the function
    ((oddp (car lst)) ;if first number is odd,
        ((cons (+ 1 (car lst)) acc) (add-to-odd (cdr lst) acc)))) ; add 1 to that number and cons it to the acc list, restart function

I thought that if I call the function add-to-odd with (cdr list) it will eventually turn into an empy list, so the base case will kick in and brake the loop. This is not happening. What do I not see?

*

Thanks for the help so far and if you find time to nudge me on a little further - it would be apreceated

cheers

p.

(oh, and I do hope to be using this in the future ... but I guess for the time beeing I will stick with franz lisp and notepad++)

(acc) is telling lisp to evaluate the function acc with 0 arguments. Try returning just acc not (acc).

You are currently mixing two different approaches to solving this problem: one, to pass an accumulator argument to the successive function calls, and two, to cons an initial result to an additional call to the function.

An exercise in recursion is probably intended to draw out the latter version, but you might find it instructive to make both.

FKeeL wrote:I thought that if I call the function add-to-odd with (cdr list) it will eventually turn into an empy list, so the base case will kick in and brake the loop. This is not happening. What do I not see?

If you used CL-aware editor like Emacs/Slime, it could indent automatically and then it would become apparent that the evenp/oddp forms are not part of the COND, and are executed unconditionally:

(defun add-to-odd (lst acc)
  (cond
    ((null lst) acc))
  ((evenp (car lst))
   ((cons (car lst) acc)(add-to-odd (cdr lst) acc)))
  ((oddp (car lst))
   ((cons (+ 1 (car lst)) acc) (add-to-odd (cdr lst) acc))))

In fact, I don't see how you could get infinite recursion out of that, since it is not valid Common Lisp and doesn't compile. But if the COND scope is fixed, only one problem remains (well, two, or maybe three?): as I had written before usually when using recursion you do not mutate state. In fact the description I linked does state quite clearly that it creates a fresh cons, rather than modify anything. You have to pass this fresh cons to the recursive call as the accumulator argument.

The other problem is that in CL and Lisps in general parentheses are not a grouping operator, they designate forms, so even if you wanted a sequential procedure, which you don't, you would use the PROGN form, except you wouldn't, because COND has an implicit PROGN anyway. That is not important for this case, anyway.

The final problem is that if you use the accumulator approach the result list will be reversed due to the way it was constructed. You have to either REVERSE the accumulator in the base case, or don't use accumulator and built the result directly, that is, by consing a new element on the result of recursive call. This uses linear stack space, but that doesn't matter for homework exercise unless it is specified to use tail calls.

I'm going to give you a tutorial on recursion.

Consider factorials. 5! (five factorial) is defined as 5 * 4 * 3 * 2 * 1. Here are more examples:

• 0! = 1
• 1! = 1
• 2! = 2 * 1
• 3! = 3 * 2 * 1
• 4! = 4 * 3 * 2 * 1
• 5! = 5 * 4 * 3 * 2 * 1

Or, put another way:

• 1! = 1 * 0!
• 2! = 2 * 1!
• 3! = 3 * 2!
• 4! = 4 * 3!
• 5! = 5 * 4!

Compute N!
Multiply N by (N-1)! How do you compute (N-1)!? By running this same computation on N-1.

Lets assume we have a black box function called next-factorial that given N could compute (N-1)!.

• (next-factorial 0) = error
• (next-factorial 1) = 1
• (next-factorial 2) = 1
• (next-factorial 3) = 2
• (next-factorial 4) = 6

Given such a function, writing factorial would be very easy. There are two cases: N <= 0 (in which case we don't call next-factorial, because that would produce an error!) and everything else.

(defun factorial (n) 
    (assert (>= n 0))
    (if (zerop n) 1 (* n (next-factorial n))))

But how do we write next-factorial?

Since it's a factorial, we can define it in terms of our factorial function.

(defun next-factorial (n) (factorial (1- n)))

Now we are just going in circles!

Yes, lots of circles. But N keeps getting smaller and will eventually be 0 and the circles will stop. This is recursion. Once you get comfortable with the idea, we can eliminate next-factorial entirely by inlining it into factorial like this:

(defun factorial (number)
   (assert (>= number 0))
   (if (zerop number) 1 (* number (factorial (1- number)))))

Recursion on Lists

Recursion works provided their is a end to the recursion. Recursion on lists tends to focus on the CDR's and the end is when the list is empty. If you watched a recursive function called REC that processed the list (a b c d) then you would probably see REC called over and over with these arguments in this order:

• (rec '(a b c d))
• (rec '(b c d))
• (rec '(c d))
• (rec '(d))
• (rec '()) ;; '() == nil --- rec is probably defined to stop at this point.

So lets write a recursive list function that takes a number of steps and reports the stair you are at each stage. So if positive means step up, and negative means step down then (3 4 -2 -2) means up 3 stairs, up 4 stairs, down 2 stairs, down 2 stairs. I want the answer (3 7 5 3) which means I was at stair 3, then stair 7, then stair 5 then stair 3.

Again, lets assume we have a routine rec-more-steps that takes our current stair and a list of step-ups/downs and returns a list of stairs we were on. If we had that routine, it would be easy to write the function rec. Rec just takes the first step-ups/downs and adds them to 0 to get our current stair --- then we pass that and the rest of the list onto rec-more-steps. The only special case to consider is if the list is empty, in which case the result is nothing.

(defun rec (list &optional (start-stair 0)) 
  (unless (null list)
    (let ((current-stair (+ start-stair (first list))))
      (cons current-stair (rec-more-steps (rest list) current-stair)))))

Now what is the definition of rec-more-steps? It performs the same task as rec, but on the rest of the list...

(defun rec-more-steps (list start-stair) (rec list start-stair))

That wasn't so hard now was it? Now that we see the pattern, it's easy to substitute rec for rec-more-steps. The final result is:

(defun rec (list &optional (start-stair 0)) 
  (unless (null list)
    (let ((current-stair (+ start-stair (first list))))
      (cons current-stair (rec (rest list) current-stair)))))

CL-USER> (rec '(3 4 -2 -2))
(3 7 5 3)

Thanks Ramarran and Warren for your help.

So this is what I did to figure this out (Just in case anyone is as dumbfounded as me and wants to follow what I did) (maybe it makes sense to (once I've worked myself through all my problems) turn it into a big recusrion tutorial?)

First I tried to express a recursive definition of factorials in my own "vocabulary" (I believe my prof is a functional purist, so I am trying to be that as well)

(defun factorials (number)
	(cond
		((eql number 0) 1)
		((> n 0) (* number(factorial (- n 1 ))))))

The a tried doing the same with the stairs example, but failed miserably. However, it got me thinking - I realised that all of my approaches would give me a reversed list of my desired answer. So I figured, just to see if my thinking is right, I would create a function which gives back a reverse list.

(defun rev (lst &optional  (result (list)))
	(cond
		((null (cdr lst)) (cons (car lst) result))
		((not (null lst)) (rev (cdr lst) (cons (car lst) result)))))

Once that was done, I started thinking about reversing this process. Recursivly defining a new list, which is not reverse. So I googled a bit and found the append function. I cam up with this code, which, in essence simply reproduces the original list which is entered.

(defun revrev (lst &optional  (result (list)))
	(cond
		((null (cdr lst)) (append result (list(car lst))))
		((not (null lst)) (revrev (cdr lst) (append result (list(car lst)))))))

Now I was ready to tackle my original problem. Creating a function which adds 1 to all odd numbers. In essence I had to do exactly what I had just done, however this time I made different conditions (checking for odd and even) and simply added one to all the odd calls.

 (defun add-to-odd (lst &optional  (result (list)))
	(cond
		((null lst) result)
		((evenp (car lst)) (add-to-odd (cdr lst) (append result (list(car lst)))))
		((oddp (car lst)) (add-to-odd (cdr lst) (append result (list (+ 1 (car lst))))))))

So, I have the answer to my first problem.

I will go take a look at the second problem and most likely will be back here with a tun of questions or (hopefully not) just generall confusion asking for tipps again. Anyway, just so that all the effort you other people put into this is put to its best use, I promise sumarize this into a tutorial wehn I'm done.

I would really apreceate any comments on the code snippets I posted. If there are simpler and more efficiant ways, or if I am doing anything unnecesary I would like to know about it. (This is not just for an assignment, I really want to actually learn lisp to a level where it becomes a usefull tool.)

Anyway, I guess I'll be back soon.

Thanks so far

P.

Edit: (nevermind, I figured it out)
is there a function which tells me whether an element is a list or not? i.e. a function which tells me (car '((a b c) b c d a a b c)) is a list? Edit: ---> its listp

Thanks for posting this. I'm a Lisp-novice as well (working out of the Practical Common Lisp book), and the exercise was good to sharpen my teeth on. I think I like your approach better, but this is what I worked out.

(defun add-to-odd (input-list)
  (if (not (equalp input-list nil))             ; if we're not at end of list
      (append (list (if (oddp (car input-list)) ;    if first element is odd
                (+ (car input-list) 1)          ;       +1 and add to list
                (car input-list)))              ;    else just add to list
            (add-to-odd (cdr input-list)))      ;    add-to-odd rest of list
      (return-from add-to-odd nil)))            ; else return

It was quite a struggle; even though I've got plenty of programming experience, Lisp is something of a paradigm shift. Among the things learned: Even though I can read the book, type in the code, and think I understand it, being able to write my own Lisp code is quite another thing. But it's fun; after a little more than half an hour I finally got the function to work, and felt like running into the street shouting "Eureka!"

EDIT: "untabified" the code (sorry!)

FKeeL wrote: The a tried doing the same with the stairs example, but failed miserably. However, it got me thinking - I realised that all of my approaches would give me a reversed list of my desired answer. So I figured, just to see if my thinking is right, I would create a function which gives back a reverse list.

Instead, you can use REVERSE or NREVERSE. (nreverse is allowed to use destructive operations, which can make it faster, but it also might modify its arguments.) The idiom you are using (consing up a list "backwards" as you recurse down the argument list(s)) is actually pretty common.

Also: whenever you have

(append (list x) other-list)

You can instead do

(cons x other-list)

I would assume this is more efficient, but that is not at all my area of expertise.

(Disclaimer: I am a bit of a newbie too. So if someone contradicts me, I am wrong.)

@jstoddard: glad that this thread is helping other people as well as me . we seem to be pretty much exactly in the same boat in regards to lisp...

What intreagues me about your solution is that you somehow manage to recurse with only one list - I wish I could figure out how to do that. On the other hand the if and return-from are very procedural programming and I am trying to get a purely functional solution.

Anyway, if you, or anyone else is interested here are some more problems I have to solve:

(2) Write a recursiveLISP function deep‐reversewhich reverses all elements of all lists found within its argument. Do not use the system function reverse. So:

> (deep‐reverse '(a b c)
(c b a)
> (deep‐reverse '(a (b c) d))
(d (c b) a)
> (deep‐reverse '((a b (c d) (e f)) (g (h i(j k)))))
((((k j) i h) g)((f e) (d c) b a))

EDIT: My solution to this problem

(defun deep-reverse (lst &optional(result (list)))
	(cond
		((null (cdr lst)) 													;when the rest of the list is null
			(cons (car lst) result))										;output result
		((listp (car lst)) 													;when the first element of the list is a list					
			(deep-reverse (cdr lst)										;deep reverse the rest of the list
				(append (list(deep-reverse (car lst))) result))) 			;add the deep reverse of this specific list to result
		((not (null lst)) 													;when the first element of the list is neither null nor a list (as all lists have already been taken care of)
		(deep-reverse (cdr lst) 											;deep reverse the rest of the list
			(cons (car lst) result)))))										;add the the element to the result

(3) Write a recursiveLISP function called big‐and‐littlewhich takes a list of numbers as its argument and returns the sum of the largest and smallest number in the list. Note: The largest and smallest could be the same number, even the same element.
So:

> (big‐and‐little '(4 9 2 3))
11
> (big‐and‐little '(5 5 5))
10
> (big‐and‐little '(8))
16

Edit: My solution to this problem (i am not happy with using variables, it would be nice to avoid that, but i cant wrap my head around it)

(defun largest-smallest (lst &optional (small (car lst)) (large (car lst)))
	(cond
		((null lst) (+ small large))
		((< (car lst) small) (largest-smallest (cdr lst) (set 'small (car lst) ) large))
		((> (car lst) large) (largest-smallest (cdr lst) small(set 'large (car lst) )))
		(t (largest-smallest (cdr lst) small large ))))

(4) Write a recursiveLISP function non‐nilthat returns 1 where each element of a list is non‐nil, and 0 where the elements are nil.
So:

> (non‐nil '(a nil (b) (nil) 2))
(1 0 1 1 1)

I will post the solutions (or my solution attempts) here as I arrive at them. If anyone can give me a tip how to solve problem 3 using recursion in purely functional programming I would apreceate that. The only methods I can think of involve declaring variables.

cheers

p.

trillioneyes wrote:

Also: whenever you have

(append (list x) other-list)

You can instead do

(cons x other-list)

I would assume this is more efficient, but that is not at all my area of expertise.

...hm my compiler doesnt work like that.

CG-USER(13): (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
CG-USER(14): (cons '(1 2 3) '(4 5 6))
((1 2 3) 4 5 6)

See the difference? Or did I misunderstand you?

Yeah, I'm a hopelessly procedural programmer. Anyway, here's your code modified for only one list. Any better?

(defun add-to-odd (input-list)
  (cond
    ((equalp input-list nil) nil)
    ((evenp (car input-list)) (append (list (car input-list)) (add-to-odd (cdr input-list))))
    ((oddp (car input-list)) (append (list (+ (car input-list) 1)) (add-to-odd (cdr input-list))))))

nice. I think the code you just posted is pretty much as good as it gets. Its recursive, 100% functional has (as far as I can tell) nothing which isnt necesary ... and I am actually beginning to understand this.
though I probably should just get some sleep, right now its like behind a gray mist, I hope when I wake up tomorrow things will be clearer.

Anyway, I solved the second problem.

FKeeL wrote:

(2) Write a recursiveLISP function deep‐reversewhich reverses all elements of all lists found within its argument. Do not use the system function reverse. So:

> (deep‐reverse '(a b c)
(c b a)
> (deep‐reverse '(a (b c) d))
(d (c b) a)
> (deep‐reverse '((a b (c d) (e f)) (g (h i(j k)))))
((((k j) i h) g)((f e) (d c) b a))

EDIT: My solution to this problem

(defun deep-reverse (lst &optional(result (list)))
	(cond
		((null (cdr lst)) 													;when the rest of the list is null
			(cons (car lst) result))										;output result
		((listp (car lst)) 													;when the first element of the list is a list					
			(deep-reverse (cdr lst)										;deep reverse the rest of the list
				(append (list(deep-reverse (car lst))) result))) 			;add the deep reverse of this specific list to result
		((not (null lst)) 													;when the first element of the list is neither null nor a list (as all lists have already been taken care of)
			(deep-reverse (cdr lst) 										;deep reverse the rest of the list
				(cons (car lst) result)))))									;add the the element to the result

any thoughts on this code? alternat solutions?

oh, and if anyone has ideas on how to tackle this here I would like to hear them:

FKeeL wrote: (3) Write a recursiveLISP function called big‐and‐littlewhich takes a list of numbers as its argument and returns the sum of the largest and smallest number in the list. Note: The largest and smallest could be the same number, even the same element.
So:

 Select all
        > (big‐and‐little '(4 9 2 3))
        11
        > (big‐and‐little '(5 5 5))
        10
        > (big‐and‐little '(8))
        16

FKeeL wrote:See the difference? Or did I misunderstand you?

You did misunderstand. What CONS does is to add one element on the front of the list. Append merges two lists. In most of your functions you are adding only one element. Lists in CL are singly linked list, which means that adding an element on the front is constant time operation, but adding an element at the end, as well as appending two lists, is linear in time in the length of the first list.

That means that you probably never want to call APPEND in a loop, since this adds an additional linear factor to algorithmic complexity. This is bad. What you want to do is attach elements at the front of the list and then reverse the list at the end, which, since it is outside the loop, only adds a linear term, not multiplies by it.

FKeeL wrote:What intreagues me about your solution is that you somehow manage to recurse with only one list - I wish I could figure out how to do that. On the other hand the if and return-from are very procedural programming and I am trying to get a purely functional solution.

I did explain this before:

Ramarren wrote:or don't use accumulator and built the result directly, that is, by consing a new element on the result of recursive call

English is not my primary language so sorry if that wasn't clear. Using accumulators is usually done for efficiency, since it allows tail call optimization. If you don't know what that is, you probably shouldn't worry about this, since that straight construction of the list is usually simpler conceptually.

Your solution to problem 2 is mostly good. Some minor cleanups would give:

(defun deep-reverse (lst &optional (result (list)))
  (cond
    ((null lst)  
     result)     
    ((listp (car lst))
     (deep-reverse (cdr lst)
                   (cons (deep-reverse (car lst)) result)))
    (t
     (deep-reverse (cdr lst)
                   (cons (car lst) result)))))

It is best for the base condition to be as simple as possible. Your base case is correct, but adds more complexity and only saves a single function call, so it is probably not worth it.

Never use (append (list ...) ...) since it is exactly equivalent to CONS, as explained in the post before, but more complex and expensive.

The final branch, if reached at all, is always true, so there is not reason to have a condition there.

FKeeL wrote:oh, and if anyone has ideas on how to tackle this here I would like to hear them:

This is best approached with two functions. In the case of recursive functions you often want to use the "wrapper" function, which exposes the interface, checks preconditions, and initializes conditions for recursion by calling the proper recursive function. In this case the precondition is that the list has to have at least one element and they must be numbers, although depending on the requirements of the task it might be assumed and not require checking.

Creating conditions for recursion means putting items of the problem into arguments. In this case it a list of remaining numbers, the largest number so far, and the smallest number so far. So your actual recursive functions has to have three arguments. Then you just recurse in the inner function similarly like before. Remember that the core of recursion is to, on every step, reduced the problem to a similar one, but simpler.

Hi Ramarren. When I seem dense, its not because of your english (which appears close to flawless to me anyway) its rather that your understanding of lisp is so much higher than mine that you take concepts for granted, which I can hardly even wrap my head around. Usually when I read your post the first time, I have no idea what you mean by it. After I have figured it out, it begins to dawn on me.

For example while this appeared completely cryptic when you first said it, it is now obvious. But I somehow had to experience it myself before I understood it.

You need to CONS a head (that is, a CAR) of list, appropriately modified, onto a tail (CDR) created by a recursive call to the tail of the argument.

-----

I thought reversing the result at the end was less elegent, as it seemed like "cheating". I get what you are saying about efficiancy though. Also, using t as the last condition makes sense. Anyway. I believe I have now understood everything you said until your last post. Your last post, again, is cryptic to me. I am confident, that I will understand it, as soon as I have figured out, but you are assuming that I know much more about programming in lisp (or programming in general) than I do. Sadly, at times I really need baby-talk it seems.

However I apreceate your help a whole lot. I just wrote a solution, which completely disregards your input - however, I think you are hinting at a more elegent solution, which I would like to figure out. I will try the last example and then come back to your input and give it another try.

Here is my solution

(defun largest-smallest (lst &optional (small (car lst)) (large (car lst)))
	(cond
		((null lst) (+ small large))
		((< (car lst) small) (largest-smallest (cdr lst) (set 'small (car lst) ) large))
		((> (car lst) large) (largest-smallest (cdr lst) small(set 'large (car lst) )))
		(t (largest-smallest (cdr lst) small large ))))

cheers

p.

Well, it is supposed to be a bit cryptic, since the point is to help you understand yourself rather than just give an answer. Alas, it is hard to strike a proper balance, especially with relatively long latency communication medium like a forum.

Your solution is actually very close. The things I had written about the wrapper function are I suppose not necessary, since you can, as you did, do the initialization in default arguments. I would have thought a second function to be simpler, but it does the same thing.

Why would you use SET here? For one thing, SET is a very rarely used form in CL, and I am not sure where you learnt it. It sets a value globally associated with the given symbol, which is very much not what you want, considering the solution is supposed to be functional-recursive. Also, you do not need it all, since your function doesn't see the global value cell anyway, and the values of the arguments are established by the recursive call itself. Just call the function with the values you want the argument variables to have on the next call. That is the point of recursive functions.

*duh* of course. (where I learnt it? dont remember, but google is my friend. The reason I come here is that someone stops me when I begin doing stupid things like this. thanks.)
p
(who now needs to do some lisp-unrelated stuff for a while)

Hey good work FKeel, I was going to mention using functions like 'null' and 'zerop', but you seem to have found them yourself.

I was looking at this:

(defun largest-smallest (lst &optional (small (car lst)) (large (car lst)))
   (cond
      ((null lst) (+ small large))
      ((< (car lst) small) (largest-smallest (cdr lst) (set 'small (car lst) ) large))
      ((> (car lst) large) (largest-smallest (cdr lst) small(set 'large (car lst) )))
      (t (largest-smallest (cdr lst) small large ))))

Do you know C? When you call a function in C do you call it like this?

void example(list* l, int small, int big) {
   example(l->next, small=l->value, big); 
}

Or this?

void example(list* l, int small, int big) {
   example(l->next, l->value, big);           ;; Changed small=l->value to just l->value.
}

Tail Recursion

In your add-to-odd solution, you're using tail recursion.

(defun add-to-odd (lst &optional  (result (list)))
   (cond
      ((null lst) result)
      ((evenp (car lst)) (add-to-odd (cdr lst) (append result (list(car lst)))))
      ((oddp (car lst)) (add-to-odd (cdr lst) (append result (list (+ 1 (car lst))))))))

What is tail recursion --- well compare these (the second one is the tail call)

(defun mult-abit  (a) (* a 4))
(defun add-some (a)  (+ a 4 (mult-abit a)))

(defun mult-abit  (a too-add) (+ (* a 4) too-add))
(defun add-some (a)  (mult-abit a (+ a 4)))

The difference is, in the first example once we call mult-abit, add-some still needs to add a and 4 to the result. In the second case, once add-some calls mult-abit, there is nothing left for add-some to do. This distinction can effect performance in some cases (but this assignment isn't one of those cases, so don't worry).


(I think) every recursive function can be written tail recursively and vis versa. Sometimes the tail recursive way is simpler, sometimes not.

Examples

I don't want to do you're homework for you, so I'll write a tail recursive routine called keep-multiples-of-4. Then I'll show you the plain recursive form.

(defun keep-fours-trec (list result)
  (cond ((null list) (nreverse result))
	((zerop (mod (car list) 4)) (keep-fours-trec (cdr list) (cons (car list) result)))
	(t (keep-fours-trec (cdr list) result))))

CL-USER> (keep-fours-trec '(5 4 5 2 7 8 5 4 57 12 57 16 18) nil)
(4 8 4 12 16)

(defun keep-fours-rec (list)
  (cond ((null list) nil)
	((zerop (mod (car list) 4)) (cons (car list) (keep-fours-rec (cdr list))))
	(t (keep-fours-rec (cdr list)))))

CL-USER> (keep-fours-rec '(5 4 5 2 7 8 5 4 57 12 57 16 18))
(4 8 4 12 16)


One More Example

This time I'll show you a tail recursive function that keeps a running sum and count of positive numbers. At the end it gives back the average of those numbers (sum / count).

(defun pos-avg-trec (list sum count)
  (cond ((null list) (if (zerop count) nil (/ sum count)))
	((< (car list) 0) (pos-avg-trec (cdr list) sum count))
	(t (pos-avg-trec (cdr list) (+ sum (car list)) (1+ count)))))

(defun pos-avg-rec (list)
  (cond ((null list) (values 0 0))
	((< (car list) 0) (pos-avg-rec (cdr list)))
	(t (multiple-value-bind (sum count) (pos-avg-rec (cdr list))
	     (values (+ sum (car list)) (1+ count))))))

(defun pos-avg-start (list)
  (multiple-value-bind (sum count) (pos-avg-rec list)
    (if (zerop count) nil (/ sum count))))

CL-USER> (pos-avg-trec '(0 2 7 -5 -5 -3 -1) 0 0)
3
CL-USER> (pos-avg-start '(0 2 7 -5 -5 -3 -1))
3