Newbie questions - and yes, its homework :-(

Discussion of Common Lisp
trillioneyes
Posts: 8
Joined: Sat Nov 20, 2010 10:00 pm

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

Post by trillioneyes » Fri Jan 28, 2011 9:18 pm

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

Code: Select all

(append (list x) other-list)
You can instead do

Code: Select all

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

FKeeL
Posts: 10
Joined: Thu Jan 27, 2011 1:01 pm
Location: Kinston, ON / Maastricht / Vienna

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

Post by FKeeL » Fri Jan 28, 2011 11:02 pm

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

> (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.
Last edited by FKeeL on Sat Jan 29, 2011 11:17 am, edited 3 times in total.

FKeeL
Posts: 10
Joined: Thu Jan 27, 2011 1:01 pm
Location: Kinston, ON / Maastricht / Vienna

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

Post by FKeeL » Fri Jan 28, 2011 11:08 pm

trillioneyes wrote:

Also: whenever you have

Code: Select all

(append (list x) other-list)
You can instead do

Code: Select all

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

Code: Select all

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?

jstoddard
Posts: 20
Joined: Fri Jan 28, 2011 6:13 pm

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

Post by jstoddard » Fri Jan 28, 2011 11:32 pm

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

Code: Select all

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

FKeeL
Posts: 10
Joined: Thu Jan 27, 2011 1:01 pm
Location: Kinston, ON / Maastricht / Vienna

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

Post by FKeeL » Sat Jan 29, 2011 12:02 am

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:

Code: Select all

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

Code: Select all

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

Code: Select all

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

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

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

Post by ramarren » Sat Jan 29, 2011 1:57 am

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.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

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

Post by ramarren » Sat Jan 29, 2011 2:05 am

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

Code: Select all

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

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

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

Post by ramarren » Sat Jan 29, 2011 2:21 am

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.

FKeeL
Posts: 10
Joined: Thu Jan 27, 2011 1:01 pm
Location: Kinston, ON / Maastricht / Vienna

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

Post by FKeeL » Sat Jan 29, 2011 11:32 am

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

Code: Select all

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

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

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

Post by ramarren » Sat Jan 29, 2011 11:51 am

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.

Post Reply