5 Replies - 332 Views - Last Post: 24 October 2013 - 09:29 AM

#1 jjallenjj  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 46
  • Joined: 07-May 11

Rest function adding parentheses?

Posted 23 October 2013 - 04:45 PM

I currently have a assignment to introduce us to clisp. We have to find the min and a max of a BST represented in a list. I have the min function working but I have spent hours trying to figure out the max. For some reason the list gets an extra set of parentheses after the first call.

The numbers we were given are (19 (13 (10 () 12) 15) (24 (22 20 ()) (31 27 39))). This represent a BST as
19

13 24

10 15 22 31

nil 12 nilnil 20nil 27 39

Any insight to what is going wrong with my Find_max function? Also the start function will intiialize the above list to the variable a.

;Data for the BST
(defun start() (setq a   '(19 (13 (10 ()  12) 15) (24 (22 20 ()) (31 27 39)))     ))

; Return Base Node
(defun get_value (x) (first x))

; Return Left Subtree
(defun left_subtree(x) (first (rest x)))

;Return Right Subtree
(defun right_subtree(x) (rest (rest x)))

;Finds min value recursively
(defun find_min (x)
   (print x)
   (cond
    ;Return Atom if found, Will be min
    ((atom x)                             x                      )
    ;Empty List
    ((null  x)                           nil                     )
    ;Return Min List
    ((null  (first( rest  x)))        (first x)                  )
    ;Continue Left
    (  t                        (find_min(first(rest x)))        )
   )
)

;Finds max value recursviely
(defun find_max (x)
   (print x)
   (cond
     ;Return Atom if found, Will be max
     ((atom x)                                x                     )
     ;Empty List
     ((null  x)                              nil                    )
     ;Return Max (last element)
     ((null (rest x))                         x                     )
     ; Continue Right
     ( t                              (find_max(rest(rest  x)))         )
   )
)

;Inorder
(defun inorder (x)
   (cond
     ;Root = NULL
     ((atom x)                           x       )
     ((null (rest x))                    x       )
     ;Left
     ( t              (inorder (rest(first  x)))    )
     ;Print/Store
     ( t                     (print x)              )
     ;Right
     ( t              (inorder (rest (rest x)))     )
   )
)




Is This A Good Question/Topic? 0
  • +

Replies To: Rest function adding parentheses?

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7804
  • View blog
  • Posts: 13,198
  • Joined: 19-March 11

Re: Rest function adding parentheses?

Posted 23 October 2013 - 07:46 PM

View Postjjallenjj, on 23 October 2013 - 06:45 PM, said:

I currently have a assignment to introduce us to clisp. We have to find the min and a max of a BST represented in a list. I have the min function working but I have spent hours trying to figure out the max. For some reason the list gets an extra set of parentheses after the first call.



Can you post the output you're getting, so we're all on the same page?
Was This Post Helpful? 1
  • +
  • -

#3 jjallenjj  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 46
  • Joined: 07-May 11

Re: Rest function adding parentheses?

Posted 23 October 2013 - 08:36 PM

The output I get is this. I think the extra set of parentheses are what is messing up the function.
((24 (22 20 NIL) (31 27 39)))

If I add a print statement to trace the calls I get
(19 (13 (10 NIL 12) 15) (24 (22 20 NIL) (31 27 39)))
((24 (22 20 NIL) (31 27 39)))
((24 (22 20 NIL) (31 27 39)))



If I trace the find_min function I get
(19 (13 (10 NIL 12) 15) (24 (22 20 NIL) (31 27 39)))
(13 (10 NIL 12) 15)
(10 NIL 12)
10
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7804
  • View blog
  • Posts: 13,198
  • Joined: 19-March 11

Re: Rest function adding parentheses?

Posted 23 October 2013 - 09:08 PM

Well, that's exactly what your function asks for. The first recursive call does not find an atom, and it doesn't find a null, and it doesn't find a single-item list, so it returns
(find_max (cdr (cdr '(19 (13 (10 NIL 12) 15) (24 (22 20 NIL) (31 27 39))))))

which is

(find_max (cdr '((13 (10 NIL 12) 15) (24 (22 20 NIL) (31 27 39)))))

which is

(find_max '((24 (22 20 NIL) (31 27 39))))


And when find_max gets a list consisting of a single thing, it returns that single thing.

I think what's got you confused is that cdr returns a list, while car returns an element. I would suggest you use that thought to fix your right subtree function, and then start using that function, since it'll make your function a lot more readable. (presumably, that's why you defined that function in the first place)

This post has been edited by jon.kiparsky: 23 October 2013 - 10:03 PM

Was This Post Helpful? 2
  • +
  • -

#5 jjallenjj  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 46
  • Joined: 07-May 11

Re: Rest function adding parentheses?

Posted 24 October 2013 - 08:11 AM

Is there a function opposite of car? That will return the last element? I'm having trouble figuring out how to go to the right of the list without repeatedly using cdr. I dont see how I could fit car into the function for right_subtree, which is what I think I'm missing.

Edit: Nevermind I got it! Thanks alot

This the the line I found to work

(t           (first   (rest  (rest x )))             )


This post has been edited by jjallenjj: 24 October 2013 - 08:23 AM

Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7804
  • View blog
  • Posts: 13,198
  • Joined: 19-March 11

Re: Rest function adding parentheses?

Posted 24 October 2013 - 09:29 AM

View Postjjallenjj, on 24 October 2013 - 10:11 AM, said:

Is there a function opposite of car? That will return the last element? I'm having trouble figuring out how to go to the right of the list without repeatedly using cdr. I dont see how I could fit car into the function for right_subtree, which is what I think I'm missing.



That function isn't standardly defined in lisp, because that's not how lisp hackers usually treat lists - the last item in the list usually isn't anything particularly interesting, it's just the last one you look at. So since it's computationally expensive to access the last one, you would usually try to avoid storing anything you wanted direct access to in the last element. Since your binary tree is a binary tree, this isn't an issue - "last" is the same as "second". And you have a function to access that. It's even defined correctly now. :)


Quote

Edit: Nevermind I got it! Thanks alot

This the the line I found to work

(t           (first   (rest  (rest x )))             )



That looks like what I was thinking of as well. Good stuff.
Glad I could help!
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1