Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

I would really appreciate it if someone could review my LISP code. I was attempting to write a quicksort implementation. Additionally, I generated my list dynamically and wrote a couple of tests. Of course, I realize that the tests are not complete, but I decided to stop where I was and see if I could get some feedback. Thanks in advance for any help you can offer!

(defun categorize_list(pivot thelist less more)
    (let ((comparee (car thelist)) (therest (cdr thelist)))
      (if (null thelist)
            (list less more)
        (if (< comparee pivot)
          (categorize_list pivot therest (append less (list comparee)) more)
          (categorize_list pivot therest less (append more (list comparee)))
        )
        )
      )
  )

(defun quicksort(thelist)
  (if (null thelist)
    ()
      (let (
            (pivot (car thelist))
            (therest (cdr thelist))
        )
        (let ((categorized_list (categorize_list pivot therest () ())))

            (append (quicksort (nth 0 categorized_list)) (list pivot) (quicksort (nth 1 categorized_list)))
        )
        )
      )
  )


(defun make_list(thelist remaininglength)
  (if (eq remaininglength 0)
    thelist
    (make_list (append (list (random 25)) thelist) (- remaininglength 1))
  )
  )

(defun should_be_least_to_greatest(thelist)
  (if (< (length thelist) 2)
       nil 
      (if (<= (nth 0 thelist) (nth 1 thelist))
        (should_be_least_to_greatest (cdr thelist))
        (error "Out of order: ~d !< ~d ~%" (nth 0 thelist) (nth 1 thelist))
        )
      )
  )

(defun test_should_become_in_order(thelist)
  (let ((sortedList (quicksort thelist)))
    (format t "IN: ~a ~% SD: ~a ~% Testing sort.~%" thelist sortedList)
    (should_be_least_to_greatest sortedList)
    )
  )

(defun test_should_maintain_length(thelist)
  (if (not (eql (length thelist) (length (quicksort thelist))))
    (error "The sorted list is a different length than the original list! ~%")
    )
  )

(let ((thelist (make_list () 10)))
    (test_should_become_in_order thelist)
    (test_should_maintain_length thelist)
)

Thank you very much for your constructive criticism! I have made a revision based on one of the commenters suggestions. If you have any further advice based on this new version, I would really appreciate your help.

(defun categorize-list(pivot the-list less more)
    (let ((comparee (car the-list)) (the-rest (cdr the-list)))
      (if (null the-list)
            (list less more)
        (if (< comparee pivot)
          (categorize-list pivot the-rest (append less (list comparee)) more)
          (categorize-list pivot the-rest less (append more (list comparee)))))))

(defun quicksort(the-list)
  (unless (null the-list)
      (let ((pivot (car the-list)) (the-rest (cdr the-list)))
        (let ((categorized-list (categorize-list pivot the-rest () ())))
            (append (quicksort (nth 0 categorized-list)) (list pivot) (quicksort (nth 1 categorized-list)))))))

(defun generate-random-list(length)
  (let ((the-list ()))
      (loop for l from 1 to length do (setq the-list (append the-list (list (random 25))))) the-list))

(defun should-be-least-to-greatest(the-list)
  (loop for l from 0 to (- (length the-list) 2) do
    (unless (<= (nth l the-list) (nth (+ l 1) the-list)) (error "Out of order: ~d < ~d ~%" (nth l the-list) (nth (+ l 1) the-list)))))

(defun test-should-become-in-order(the-list)
  (let ((sorted-list (quicksort the-list)))
    (format t "IN: ~a ~% SD: ~a ~% Testing sort.~%" the-list sorted-list)
    (should-be-least-to-greatest sorted-list)))

(defun test-should-maintain-length(the-list)
  (unless (= (length the-list) (length (quicksort the-list))) (error "The sorted list is a different length than the original list! ~%")))

(let ((the-list (generate-random-list 10))) (test-should-become-in-order the-list) (test-should-maintain-length the-list))

Ken - thank you very much for continuing to help me improve this code. It is evident that you are quite experienced in this area and I'm sure you're very busy, so it means a lot to me! I adopted your suggestions with respect to loop and read up on the syntax of LET* so I hope that I've made some improvements in that area. I also got rid of nth in favor of using first and second throughout the code. One area which I'm still trying to improve on is managing the width of the code for readability. In this new revision, I have spaced arguments for a particularly long function call onto separate lines to try and make it more readable, but I'm not sure if it is ok because the formatting seems a bit odd. What do you think? Also, if you have any further suggestions, I am all ears. Again, thanks so much! I appreciate your help.

(defun categorize-list (pivot the-list less more)
    (let ((comparee (car the-list)) (the-rest (cdr the-list)))
      (if (null the-list)
            (list less more)
        (if (< comparee pivot)
          (categorize-list pivot 
                   the-rest 
                   (append less (list comparee)) 
                   more)
          (categorize-list pivot 
                   the-rest 
                   less 
                   (append more (list comparee)))))))

(defun quicksort (the-list)
  (unless (null the-list)
      (let (categorized-list (pivot (car the-list)) (the-rest (cdr the-list)))
        (setq categorized-list (categorize-list pivot the-rest () ()))
        (append (quicksort (first categorized-list)) 
            (list pivot) 
            (quicksort (second categorized-list))))))

(defun generate-random-list (length)
  (loop for l from 1 to length collect (random 25)))

(defun should-be-least-to-greatest (the-list)
  (loop for p on the-list while (second p) 
    when (< (second p) (first p))
      do (error "Out of order: ~d < ~d ~%" (first p) (second p))))

(defun test-should-become-in-order (the-list)
  (let ((sorted-list (quicksort the-list)))
    (format t "IN: ~a ~% SD: ~a ~% Testing sort.~%" the-list sorted-list)
    (should-be-least-to-greatest sorted-list)))

(defun test-should-maintain-length (the-list)
  (unless (= (length the-list) (length (quicksort the-list))) 
    (error "The sorted list is a different length than the original list! ~%")))

(let ((the-list (generate-random-list 10))) 
  (test-should-become-in-order the-list) 
  (test-should-maintain-length the-list))
share|improve this question
You should associate your stackoverflow account with your codereview account so the system recognizes that this question was asked by you. – sepp2k♦ Mar 4 '11 at 12:45
Done. Thanks for the heads-up! – jaresty Mar 7 '11 at 6:35

migrated from stackoverflow.com Mar 3 '11 at 4:35

3 Answers

up vote 4 down vote accepted

I don't know what the policy is about where/how to put subsequent code reviews, since the Stackexchange system doesn't really seem well-suited to their threadlike nature. Anyway, here goes.

(let ((pivot (car the-list)) (the-rest (cdr the-list)))
  (let ((categorized-list (categorize-list pivot the-rest () ())))

Look up LET*.

(let ((the-list ()))
    (loop for l from 1 to length do (setq the-list (append the-list (list (random 25))))) the-list))

This seems pretty awkward. It's just:

(loop for l from 1 to length collect (random 25))

And here:

(loop for l from 0 to (- (length the-list) 2) do
  (unless (<= (nth l the-list) (nth (+ l 1) the-list)) (error "Out of order: ~d < ~d ~%" (nth l the-list) (nth (+ l 1) the-list)))))

Every call to LENGTH or NTH has to walk the linked list. You don't want to do that in a loop. (I think you should not often need NTH with lists, and almost never in a loop.)

(loop for p on the-list while (second p)
      when (< (second p) (first p))
      do (error "Out of order: ~d < ~d~%" (second p) (first p)))

If you're going to be writing Common Lisp code, it pays to learn the LOOP DSL (or ITERATE, its spiritual successor).

Other random things:

  • Your code has gotten a lot ... wider. While I appreciate taking fewer lines, there's a limit. I don't often see multiple LET bindings on one line, for example.
  • You sometimes still leave out the space before a paren, like list(pivot, which looks funny to me.
share|improve this answer
Did you have any thoughts about the new formatting? Thanks again for your help. – jaresty Mar 9 '11 at 4:04
up vote 1 down vote

You have several negative conditionals, which is a bad idea in any language.

(if (null thelist)
   ()

I'd change it to:

(defun quicksort(thelist)
   (unless (null thelist)
      ; Sort list
   ) ; Pardon the dangling ), but there's a comment on the last line
share|improve this answer
That doesn't bother me as much: it's making the "return an empty list" case clear. – Ken Mar 5 '11 at 15:42
up vote 7 down vote

Your formatting is weird. It's going to be a lot easier for other programmers to read your code if you use a more standard style. For example, you have lots of lines with nothing but a hanging parenthesis. Your functions have no docstrings. Sometimes you use_underscores and sometimes you use compoundwords but the Lisp style is hypenated-words. Your indentation is inconsistent: learn the command in your text editor to indent your source code for you, and use it.

Instead of:

(if (not (eql (length thelist) (length (quicksort thelist))))

Using EQL for numbers seems odd. I think = would be preferred. An IF with only one branch is strange, too: WHEN or UNLESS tends to be preferred. Thus:

(unless (= (length thelist) (length (quicksort thelist)))

In another place, you do a comparison with:

(eq remaininglength 0)

The behavior of EQ with integers is undefined. You can use = or in this case:

(zerop remaininglength)

You're using recursion a lot even when it's not needed, e.g., in make_list and should_be_least_to_greatest. Common Lisp doesn't require tail-call optimization, and it's not generally common style. LOOP (or ITERATE) would probably be simpler and more efficient here.

You walk a list applying <=. Lisp's <= already takes any number of arguments, so if you don't need to know the specific elements which are out of order, you can just apply it once.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.