Need some help thx

Discussion of Common Lisp

Need some help thx

Postby gymac » Mon Nov 02, 2009 12:40 pm

Dear all,I have a small and interesting problem,but I cannot come with a perfect solution,I would be grateful if you could help me or give me a hint on this.
The problem is :

given any list ,say like '(a b c),we will convert it to '[a b c]
or '(a (b c)) ,we will convert to '[A [B C]]

In other words,the function should do the same thing as PRINT in LISP,except we change the parentheses to square brackets.But methods like simply printing to a string then replace the parentheses to square brackets don't count.
Please give me some idea,thank you so much.
gymac
 
Posts: 2
Joined: Mon Nov 02, 2009 12:32 pm

Re: Need some help thx

Postby findinglisp » Tue Nov 03, 2009 11:08 pm

Sounds like homework.

I would follow the same algorithm as the PRINT function, but where it would print a "(", instead print a "[", and ditto with ")" -> "]".

;)
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/
findinglisp
 
Posts: 440
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX

Re: Need some help thx

Postby methusala » Wed Nov 04, 2009 8:17 am

First try writing that function for a single none nested list, like (1 2 3) as well as you can. Post it, than I'll post the version I just wrote of that, and perhaps more hints will be forthcoming for the steps after that.
methusala
 
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Need some help thx

Postby gymac » Wed Nov 04, 2009 5:50 pm

Thanks Dave and methusala.
The code that I came up with is :

(defun show-list (lst)
(cond
((and
(atom lst)
(not (null lst)))
(format t "~A " lst))

((and
(atom lst)
(null lst))
(format t "]"))

(t
(format t "[")
(show-list (car lst))

(mapcar #'show-list (cdr lst))
(format t "]")
)
)
)

Definitely it is not very correct,because for '(a b),it outputs '[a b ],while the correct one should be '[a b].
I am now working on it,really need your advice,thanks.
gymac
 
Posts: 2
Joined: Mon Nov 02, 2009 12:32 pm

Re: Need some help thx

Postby findinglisp » Wed Nov 04, 2009 6:11 pm

So note a few things that you're going to have to handle in order to print a list right:

  1. First, whenever you start printing a list, you need to print your staring character (typically "(", but in your case "[").
  2. Next, you're going to have to print your list items themselves.
  3. You also have to correctly handle the spaces between items. You can do this one of two ways. One option is right after printing an item, test the remainder of the list to see if it contains any more items, and then print a space if so. The other option would be to print the first item as a special case, and then print all remaining items with a leading space before them.
  4. Finally, when you detect the end of the list, you need to print a termination character (either ")" or "]").

You have it partially, but you're not using your recursion correctly (you can't use MAPCAR and recursion well together).

-- Dave
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/
findinglisp
 
Posts: 440
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX

Re: Need some help thx

Postby methusala » Wed Nov 04, 2009 9:23 pm

Congratulations on making it print a nested list, a further step than what I had suggested. Complete this, and you will know recursion better than most working programmers.

Below is the code I typed this morning, which also has space formating errors, and also is probably not the best way to do recursion. Despite that, it also prints a nested list, which perhaps is testament to the flexible quick codability of lisp. It's probably not the best way to do recursion because of the &optional switch it uses to print the first "[" character.

Code: Select all
(defun e(x &optional y)
(if (not (eq y 1)) (princ "["))
       (if (eq nil x) (progn (format t  " ]") nil)
     
       (progn (if (atom x) (format t " ~a" x)
       (progn
       (if (listp (car x)) (format t " ["))
       (e (car x ) 1)
       (e (cdr x ) 1))))))


The code you have so far has an additional error of not printing an empty list:

CL-USER> (show-list '(1 2 3))
[1 2 3 ]NIL
CL-USER> (show-list '(1 2 (4) 3))
[1 2 [4 ]3 ]NIL
CL-USER> (show-list '(1 2 () 3))
[1 2 ]3 ]NIL

It's doing that because instead of testing if the car of x is a list and printing "[" based on that, your code is using mapcar to print "[" in front of all none empty list cars by default. If () and null were not the same thing in lisp, this wouldn't have caused that particular error, but probably a different one. This shows the dangers and extra complexity of using mapcar in recursion, instead of final base case testing.

pg explains in 'ansi lisp' that recursion is great for saving time in making loop control code, and the way to do that is to determine the none final base cases and the final base cases. The final base cases is/are where the recursion should 'hit bottom.' The none final base cases is/are where it's still recursing. The reason my code uses an &optional switch and has space formatting errors is because I didn't take the time to list and figure out how to code all my base cases. Doing that will produce optimally elegant code.

How many different types of data pieces and situations of encounter will the code have to deal with when recursing? What should be the code for doing that? How many did I include in my code and which did I leave out? How is the logic badly ordered and how can it be improved on with correct base case usage? Which final base case am I overlooking with the &optional switch hack? (hack in the bad sense)

Here is the output from my code:

CL-USER> (e '(1 2 3))
[ 1 2 3 ]NIL
CL-USER> (e '(1 2 (4) 3))
[ 1 2 [ 4 ] 3 ]NIL
CL-USER> (e '(1 2 () 3))
[ 1 2 [ ] 3 ]NIL

ps-maybe one type of switch or another, or multiple defuns, is needed for the first "[", anybody?
methusala
 
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Need some help thx

Postby gugamilare » Thu Nov 05, 2009 5:35 am

gymac wrote:Thanks Dave and methusala.
The code that I came up with is :

(defun show-list (lst)
(cond
((and
(atom lst)
(not (null lst)))
(format t "~A " lst))

((and
(atom lst)
(null lst))
(format t "]"))

(t
(format t "[")
(show-list (car lst))

(mapcar #'show-list (cdr lst))
(format t "]")
)
)
)

Definitely it is not very correct,because for '(a b),it outputs '[a b ],while the correct one should be '[a b].
I am now working on it,really need your advice,thanks.


I believe your code has a problem. Try testing it with '(nil).
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 2 guests

cron