Page 1 of 1

Need some help thx

Posted: Mon Nov 02, 2009 12:40 pm
by gymac
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 ]

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.

Re: Need some help thx

Posted: Tue Nov 03, 2009 11:08 pm
by findinglisp
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 ")" -> "]".

;)

Re: Need some help thx

Posted: Wed Nov 04, 2009 8:17 am
by methusala
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.

Re: Need some help thx

Posted: Wed Nov 04, 2009 5:50 pm
by gymac
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.

Re: Need some help thx

Posted: Wed Nov 04, 2009 6:11 pm
by findinglisp
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

Re: Need some help thx

Posted: Wed Nov 04, 2009 9:23 pm
by methusala
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?

Re: Need some help thx

Posted: Thu Nov 05, 2009 5:35 am
by gugamilare
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).