Implementing a tree parsing function

Question

I've solved an assignment a week ago, which is my first assignment using Lisp.

---

Tasks:

Task 1:

a. Given a tree as recursive lists, print the tree in breadth first order.

b. Given a tree like in task 1a, print it in child-successor order.

Input for Tasks 1a and 1b: (A (B (C (D))(E (F) (G (H)))) (J (K (L (M) (N (P))))))

Output for Task 1a:

A B J C E K D F G L H M N P 

Output for Task 1b:

A, B J B, C E J, K C, D E, F G K, L D, F, G, H L, M N H, M, N, P P, 

---

Task 2:

Tasks 2a and 2b are the same as in task 1, but now the nodes of the tree have costs. The cost represents the cost from the node parent to this node. When printing, cost should be accumulated starting from the root (2a, 2b are using styles defined by 1a, 1b accordingly).

Input for Task 2: ((A 0) ((B 5) ((C 3) ((D 4))) ((E 2) ((F 1)) ((G 7) ((H 9))))) ((J 1) ((K 3) ((L 1) ((M 7)) ((N 1) ((P 2)))))))

Output for Task 2a:

B,5 J,1 C,8 E,7 K,4 D,12 F,8 G,14 L,5 H,23 M,12 N,6 P,8 

Output for Task 2b:

A,0; B,5 J,1 B,5; C,3 E,2 J,1; K,3 C,8; D,4 E,7; F,1 G,7 K,4; L,1 D,12; F,8; G,14 H,9 L,5; M,7 N,1 H,23; M,12; N,6; P,2 P,8; 

---

Solution

I implemented my solution using an iterative approach - taking and printing cdr's of each childs (tasks are marked using comments):

 ;; Task 1a ;; This function takes a list of lists and ;; prints (car) for every sublist then repeats ;; for accumulated (cdr)'s of those sublists if not empty (defun breadth-print (node) (loop while (not (eq nil node)) do (setq temp nil) (loop for i in node do (progn (format t "~a " (car i)) (mapcar #'(lambda (j) (if (null temp) (setq temp (list j)) (setq temp (append temp (list j))))) (cdr i)))) (setq node temp) (format t "~%"))) ;; Task 1b ;; This function utilizes the same principle ;; as breadth-print, however each node is printed ;; on a new line with its children (defun breadth-print-childs (node) (loop while (not (eq nil node)) do (setq temp nil) (loop for i in node do (progn (format t "~a, " (car i)) (loop for beta in (cdr i) do (format t "~d " (car beta))) (format t "~%") (mapcar #'(lambda (j) (if (null temp) (setq temp (list j)) (setq temp (append temp (list j))))) (cdr i)))) (setq node temp))) ;; Task 2a ;; This function is based on breadth-print and ;; the only difference is that the costs are ;; updated for every element in (cdr) of sublists, ;; and formatting is a bit different (defun breadth-print-costs (node) (loop while (not (eq nil node)) do (setq temp nil) (loop for i in node do (progn (format t "~{~a,~a~} " (car i)) (mapcar #'(lambda (j) (progn (setf (nth 1 (car j)) (+ (nth 1 (car j)) (nth 1 (car i)))) (if (null temp) (setq temp (list j)) (setq temp (append temp (list j)))))) (cdr i)))) (setq node temp) (format t "~%"))) ;; Task 2b ;; This function utilizes the same principle ;; as breadth-print-childs, with only addition ;; is the calclulations of cost (similar fasion is used in breadth-print-costs), ;; which is modified according to the already passed path (defun breadth-print-childs-costs (node) (loop while (not (eq nil node)) do (setq temp nil) (loop for i in node do (progn (format t "~{~a,~a~}; " (car i)) (loop for beta in (cdr i) do (format t "~{~a,~a~} " (car beta))) (format t "~%") (mapcar #'(lambda (j) (progn (setf (nth 1 (car j)) (+ (nth 1 (car j)) (nth 1 (car i)))) (if (null temp) (setq temp (list j)) (setq temp (append temp (list j)))))) (cdr i)))) (setq node temp))) (format t "Task 1a provide input: ") (defparameter *inpa* (list (read))) (format t "~%Input 1a is ~a~%Part 1a:~%" *inpa*) (breadth-print *inpa*) (format t "Task 1b provide input: ") (defparameter *inpb* (list (read))) (format t "~%Input 1b is ~a~%Part 1b:~%" *inpb*) (breadth-print-childs *inpb*) (format t "Task 2a provide input: ") (defparameter *inpc* (list (read))) (format t "~%Input 2a is ~a~%Part 2a:~%" *inpc*) (breadth-print-costs *inpc*) (format t "Task 2b provide input: ") (defparameter *inpd* (list (read))) (format t "Input 2b is ~a~%Part 2b:~%" *inpd*) (breadth-print-childs-costs *inpd*) 

---

Concerns

What I would like to improve:

• Does it fit the Lisp coding style?
• Performance (is my iterative approach viable?)
• Function choice and general structure of the code (I'm sure that there should be a better way to do the temp checks or completely avoid them)

Answer 1

A few considerations about the style of the code.

Generalized booleans

In Common Lisp the only value “false” is NIL, every other value is considered “true”. So, if you want to check if node is different from NIL, you can simply write:

while node 

Introduction of variables

It is wrong to introduce (and assign) a variable with setq. In fact if you compile the function an error like undeclared free variable temp should be produced.

Local variables can be introduced by several constructs. The simplest one is let, like in:

(let ((new-variable1 initial-value1) (new-variable2 initial-value2)) body-where-the-new-variables-can-be-used) 

Then, to assign a variable, as well as any part of a modifiable data structure, the primitive setf should be used instead of setq.

Properties of append

It is easy to prove that the following equalities hold:

(append NIL x) ≡ (append x NIL) ≡ x 

so the expression:

(if (null temp) (setq temp (list j)) (setq temp (append temp (list j)))) 

is simply equal to:

(setf temp (append temp (list j))) 

So a correct and simplified version of the function (with more conventional indentation) could be:

(defun breadth-print (node) "breadth first printing of a list of trees" (loop while node do (let ((temp nil)) (loop for i in node do (format t "~a " (car i)) (mapcar #'(lambda (j) (setf temp (append temp (list j)))) (cdr i))) (setf node temp) (format t "~%")))) 

Note the initial comment that explains the meaning of the function: it specifies that the function accepts a list of trees (so the initial tree should be given as argument as an element inside a list).

The inner loop has two objectives: printing the “cars” of the elements of node, and appending all their “cdrs” (as lists) to produce the new list for the next top-level iteration, through the variable temp.

If decoupled, these tasks can be performed in a more compact (and simplified) way.

Printing lists

An entire list of elements separated by space can be printed in a single format expression with the "~{~a ~}" string parameter. For instance, to print all the cars of a list l, one could write:

(format t "~{~a ~}~%" (mapcar #'car l)) 

Concatenating lists obtained by mapping a function

In Common Lisp there is a primitive function to map a list-returning function to a list, and concatenating (“appending”) the results. It is mapcan (see reference). For instance, if you want to concatenate all cdrs of a list l of lists:

(mapcan #'cdr l) 

A compact definition of breadth-print

We can now give a more simplified version of the function:

(defun breadth-print (node) "breadth first printing of a list of trees" (loop for n = node then (mapcan #'cdr n) while n do (format t "~{~a ~}~%" (mapcar #'car n)))) 

Note the use of for variable = expression1 then expression2, that initializes variable to expression1 the first time the loop is executed, and then assigns the value of expression2 in the subsequent steps of the loop.

If we change the function to accept a single tree, as per the comments, this could become:

(defun breadth-print (node) "breadth first printing of a tree" (loop for n = (list node) then (mapcan #'cdr n) while n do (format t "~{~a ~}~%" (mapcar #'car n)))) 

With similar considerations, we could define a simplified version of breadth-print-childs (again with a parameter that is a tree, not a list of trees):

(defun breadth-print-childs (node) (loop for n = (list node) then (mapcan #'cdr n) while n do (loop for i in n do (format t "~a, ~{~a ~}~%" (car i) (mapcar #'car (cdr i)))))) 

As a final note, since mapcan modifies the argument, unless the argument is a fresh tree created every time the function is called, it is preferable to copy the argument at the beginning of the function, like in:

(defun breadth-print (node) "breadth first printing of a tree" (loop for n = (list (copy-tree node)) then (mapcan #'cdr n) ... (defun breadth-print-childs (node) (loop for n = (list (copy-tree node)) then (mapcan #'cdr n) ... 

I'll stop here, for now, since I do not have time to discuss about the other functions. Take this as an exercise for you to rewrite them in a similar way.