LispForum • Newbie questions - and yes, its homework :-(

Page 1 of 3

Newbie questions - and yes, its homework :-(

Posted: Thu Jan 27, 2011 1:45 pm

by FKeeL

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:

Code: Select all

;; 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?)

Re: Newbie questions - and yes, its homework :-(

Posted: Thu Jan 27, 2011 3:12 pm

by ramarren

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.

Re: Newbie questions - and yes, its homework :-(

Posted: Thu Jan 27, 2011 4:25 pm

by JamesF

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:

Code: Select all

;; 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:

Code: Select all

(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

Re: Newbie questions - and yes, its homework :-(

Posted: Thu Jan 27, 2011 8:04 pm

by FKeeL

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

Code: Select all

(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++)

Re: Newbie questions - and yes, its homework :-(

Posted: Thu Jan 27, 2011 8:31 pm

by Vivitron

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

Re: Newbie questions - and yes, its homework :-(

Posted: Fri Jan 28, 2011 12:01 am

by ramarren

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:

Code: Select all

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

Re: Newbie questions - and yes, its homework :-(

Posted: Fri Jan 28, 2011 2:23 pm

by Warren Wilkinson

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.

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Re: Newbie questions - and yes, its homework :-(

Posted: Fri Jan 28, 2011 6:47 pm

by FKeeL

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)

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Re: Newbie questions - and yes, its homework :-(

Posted: Fri Jan 28, 2011 7:15 pm

by FKeeL

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

Re: Newbie questions - and yes, its homework :-(

Posted: Fri Jan 28, 2011 9:08 pm

by jstoddard

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.

Code: Select all

(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!)