2

I am trying to write a program in Common Lisp using GNU ClISP to compile it. I would like to enter a list such as (A(B (C) ()) (D (E) (F (G) ()))) and depending on the first word print out the pre-, in-, or post-order traversal. Example: 

(pre '(A(B (C)... etc))

I am having trouble putting my logic into Clisp notation. I currently have the following code:

(defun leftchild (L)(cadr L))

(defun rightchild (L)(caddr L))

(defun data (L)(car L))

(defun pre (L)(if (null L) '()((data L)(pre(leftchild L))(pre(rightchild L)))))

... similar in and post functions

I get compiling errors saying that I should use a lambda in my pre function. I think this is due to the double (( infront of data because it is expecting a command, but I am not sure what I should put there. I don't think cond would work, because that would hinder the recursive loop. Also, will data L print as it is now? The compiler did not recognize (print (data L)).

I have been working on this code for over a week now, trying to troubleshoot it myself, but I am at a loss. I would greatly appreciate it if someone could explain what I am doing incorrectly.

Another question that I have is how can I make the program prompt a line to the user to enter the (pre '(A... etc)) so that when I run the compiled file the program will run instead of giving a funcall error?

Thank you for your time.

Improve this question

1 Answer 1

Reset to default
1

Short answer: If you want to use if, note that you'll need a progn in order to have more than one form in the consequent and alternative cases.

Long answer – also explains how to traverse accumulating the visited nodes in a list:

I guess this is homework, so I won't give you a full solution, but your question shows that you have basically the right idea, so I'll show you an easy, idiomatic way to do this.

First, you're right: The car of an unquoted form should be a function, so basically anything like (foo ...), where foo is not a function (or macro, special form ...), and the whole thing is to be evaluated, will be an error. Note that this does not hold inside special forms and macros (like cond, for example). These can change the evaluation rules, and not everything that looks like (foo bar) has to be a form that is to be evaluated by the normal evaluation rules. The easiest example would be quote, which simply returns its argument unevaluated, so (quote (foo bar)) will not be an error.

Now, about your problem:

An easy solution would be to have an accumulator and a recursive helper function that traverses the tree, and pushes the values in the accumulator. Something like this:

(defun pre (node)
  (let ((result (list)))
    (labels ((rec (node)
               (cond (...
                      ...
                      ...))))
      (rec node)
      (nreverse result))))

The labels just introduces a local helper function, which will do the actual recursion, and the outer let gives you an accumulator to collect the node values. This solution will return the result as a list. If you just want to print each nodes value, you don't need the accumulator or the helper function. Just print instead of pushing, and make the helper your toplevel function.

Remember, that you'll need a base case where the recursion stops. You should check for that in the cond. Then, you'll need the recursive steps for each subtree and you'll need to push the node's value to the results. The order in which you do these steps decides whether you're doing pre-, in-, or post-order traversal. Your code shows that you already understand this principle, so you'll just have to make it work in Lisp-code. You can use push to push values to result, and consp to check whether a node is a non-empty list. Since there's nothing to do for empty lists, you'll basically only need one test in the cond, but you can also explicitly check whether the node is null, as you did in your code.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Sorry, I skimmed your question a bit too fast. :) Your problem is just your use of if without progn for multiple forms (see the last sentence of my answer). I.e., your pre should look like this: (defun pre (n) (if (null n) '() (progn (print (data n)) (pre (leftchild n)) (pre (rightchild n))))). In this case, you can also use when with consp, without progn. I will leave the answer as it is, because I think it will be useful for people searching for "[lisp] binary tree". Btw., why do you think that cond "would hinder the recursive loop"?
Thank you for your response. I thought that cond might hinder the loop because it would require you to set all the conditions to true for the program to run through all the "else" cases, but now I think it could have worked because of the initial if statement that checks for null. I added the progn you suggested and it traverses the loop and prints out like it should. How can I keep it from printing nil at the end of the list?
I fixed it. It is no longer printing nil. The only problem I am having now is trying to print to a file, but I will keep trying. :)
About cond: It is nice if you have multiple tests, and it doesn't need a progn for multiple forms in one branch. Everything you can do with if, you can also do with cond. You can even write your own if with it: (defmacro my-if (condition consequent alternative) `(cond (,condition ,consequent) (t ,alternative))) (untested).
To surpress the nil (which is just the return value, it is not actually printed, if you don't use the code at the REPL) you can insert (values) as the last form in your progn.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.