Simple issue Trees in Lisp

Discussion of Common Lisp
Post Reply
NickNatra
Posts: 8
Joined: Mon Dec 05, 2011 10:18 am

Simple issue Trees in Lisp

Post by NickNatra » Mon Dec 05, 2011 10:28 am

Hello,
The subject says "simple", but is not really a piece of cake for me :?
Please help me( I started learning LISP 5 days ago ).

Code: Select all

   A
  / \
 B   C
    / \
   D   E
A tree can be represented in two ways
(A 2 B 0 C 2 D 0 E 0) (1)
(A (B) (C (D) (E))) (2)

->Convert a tree of type (2) to type (1).

This is my function:
____________________________________________________

Code: Select all

(defun  conv2to1(l)
	(cond
		((atom (car l)) (cons (car l) (length (cdr l))))
		(T  (append (conv2to1(car l)) (conv2to1 (cdr l))))
	)
) 
___________________________________________________
I'm not sure where I'm wrong, but i think I'm very close to the result
Last edited by ramarren on Mon Dec 05, 2011 11:55 am, edited 1 time in total.
Reason: Added code tags

NickNatra
Posts: 8
Joined: Mon Dec 05, 2011 10:18 am

Re: Simple issue Trees in Lisp

Post by NickNatra » Mon Dec 05, 2011 11:54 am

...A
../. \
.B ..C
..../ \
...D. E

The tree looks like this (corrected).
Hurry please :(

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

Re: Simple issue Trees in Lisp

Post by ramarren » Mon Dec 05, 2011 12:10 pm

Please use code tags in the future. There is a Code button above the editing are which can be used to display preformatted text like ascii-trees and code. I have also moved the topic to Common Lisp subforum, since I am assuming Common Lisp from the presence of DEFUN. If it is a different dialect of Lisp please specify.

Your function is not properly recursive, as the non-recursive case is not a base case. In this case a base case is an empty list representing lack of leaf nodes. Consider the non-base, recursive, case first. You need to collect a node value, a number of leaves, and then append to that a representation of leaves. A non-existent leaf does not appear in this representation, which means that the base case can return NIL, which in Common Lisp is equivalent to an empty list, which will be ignored when appending.

To generate leaf representation you need to call the function recursively on the second and third element of the list, which can be accessed with SECOND and THIRD functions, or the old fashioned CADR and CADDR, and then append the results.
Last edited by ramarren on Mon Dec 05, 2011 12:12 pm, edited 1 time in total.
Reason: explain the topic move

NickNatra
Posts: 8
Joined: Mon Dec 05, 2011 10:18 am

Re: Simple issue Trees in Lisp

Post by NickNatra » Tue Dec 06, 2011 1:07 am

Yes i'm using common lisp.
Tahks for the help.

Any tips here :

Code: Select all

(defun convert(l)
	(cond
		((null l) nil)
		((atom (car l)) (cons (car l) (length (cdr l))) )
		(T (cons (convert(cadr l)) (convert (caddr l))))
	)
)
:roll: English is not my native language so sorry my bad understanding

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

Re: Simple issue Trees in Lisp

Post by ramarren » Tue Dec 06, 2011 5:41 am

You have to think what is being passed to the function. It is either a NIL, representing an non-existent leaf, or a list of one, two or three elements. This are the only two possibilities, which means that the conditional only needs two branches, not three as in your attempt.

A convenient fact about CADR and CADDR in this case is that since both CAR and CDR are defined to return NIL when called on NIL, they will return NIL even if the list is too short, which means you don't have to check length of the list when making the recursive call.

CONS constructs a list only if the second argument is a list or NIL (which is an empty list in CL), and it adds the first argument as an element, whatever the first argument is. To merge two lists you should use APPEND. In your case you want to add both the node and the number of leaves to the front of leaf representation, which means you have to use CONS nested.

NickNatra
Posts: 8
Joined: Mon Dec 05, 2011 10:18 am

Re: Simple issue Trees in Lisp

Post by NickNatra » Tue Dec 06, 2011 8:28 am

i guess this is 90% correct

Code: Select all

(defun convert(l)
   (cond
		((null l) nil)
		(T (cons (car l)  (cons (cons(length(cdr l))(convert (cadr l)))(convert (caddr l)))))
   )
)
exept the fact that
for this

Code: Select all

> (convert '(A (B) (C (D) (E))))
the result is

Code: Select all

(A (2 B (0)) C (2 D (0)) E (0))
and not

Code: Select all

(A 2 B 0 C 2 D 0 E 0)

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

Re: Simple issue Trees in Lisp

Post by ramarren » Tue Dec 06, 2011 9:07 am

The return value of your function is a list. You have two recursive calls, which means two lists. As I said, you need APPEND to append those two lists together. And then use CONS twice nested to add the number of leaves and the node to the result of that.

NickNatra
Posts: 8
Joined: Mon Dec 05, 2011 10:18 am

Re: Simple issue Trees in Lisp

Post by NickNatra » Tue Dec 06, 2011 10:58 am

After a long struggle i got the expected result.

Code: Select all

(defun convert(l)
   (cond
		((null l) nil)
		(T (cons (car l)  (cons (length(cdr l)) (append (convert (cadr l))(convert (caddr l))))))
   )
)
Thank you for your time.
Your help means a lot to me .

Post Reply