Quicksort?

Discussion of Common Lisp

Quicksort?

Postby Cass » Thu Oct 24, 2013 9:21 am

Hello,

Could anyone help me with kinda my kinda clueless fumbling? ^_^; (I'm kinda new to the whole programming thing.)

I was thinking that it'd be kinda neat to be able to take the data from my school work and run correlation tests on everything against everything. I'm trying to implement quicksort as the first step in doing that.

Anyway, first I tried writing it out like this:

Code: Select all
(defun test (lst)
  (let ((pivot (car lst))
   (smaller-than (remove-if (< pivot) lst) )
   (larger-than (remove-if (> pivot) lst) ))
    (setf pivot (cons (test smaller-than) pivot))
    (cons pivot (test larger-than))))


However SBCL is complained that pivot isn't defined yet:

Code: Select all
 warning:
    undefined variable: PIVOT
    --> PROGN
    ==>
      (THE REAL PIVOT)


Which was kinda confusing me because I told it what pivot was as the first thing.

I did think maybe you weren't allowed have one definition in let dependent on something else in the let. Which seems supported by a quick test in the REPL:

Code: Select all
(let (
          (x 1)
          (y (+ x 1))))
; in: LET ((X 1) (Y (+ X 1)))
;     (LET ((X 1) (Y (+ X 1)))
;       )
;
; caught STYLE-WARNING:
;   The variable X is defined but never used.
;
; caught STYLE-WARNING:
;   The variable Y is defined but never used.

; in: LET ((X 1) (Y (+ X 1)))
;     (+ X 1)
;
; caught WARNING:
;   undefined variable: X


Anyway, then I tried this:

Code: Select all
(defun test (lst)
  (defvar pivot (car lst))
  (defvar smaller-than (remove-if (< pivot) lst) )
  (defvar larger-than (remove-if (> pivot) lst) )

    (setf pivot (cons (test smaller-than) pivot))
    (cons pivot (test larger-than))))


Which among other things said -

Code: Select all
  warning:
    undefined variable: PIVOT
    --> PROGN
    ==>
      (THE REAL PIVOT)
   
  warning: undefined variable: SMALLER-THAN


I suppose it makes sense that smaller-than wouldn't be defined if pivot wasn't. But then why's larger-than not throwing its own warning?

Did think I might not understand how defvar was used but this works:

Code: Select all
(defvar x (car '(1 2)))

=> X

X

=> 1


So, yeah, I'm just kinda really confused now.

SBCL if that's relevant.

Thanks! Apologies if this is in the wrong place ^_^
Cass
 
Posts: 5
Joined: Thu Oct 24, 2013 8:14 am

Re: Quicksort?

Postby saulgoode » Thu Oct 24, 2013 5:58 pm

The bindings in a let block are not guaranteed to be handled in sequence. They might be evaluated in a different order than specified, or evaluated in parallel on a multi-threaded implementation.

If you wish to have the bindings evaluated in a specific order (so later bindings can reference earlier ones) then you should use let*.
Code: Select all
  (let* ((x 10)
   (y 20)
   (z (+ x y)) )
    (print z) )
saulgoode
 
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Quicksort?

Postby Cass » Sat Oct 26, 2013 4:35 pm

Ah, excellent. Thank you! :D
Cass
 
Posts: 5
Joined: Thu Oct 24, 2013 8:14 am


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 5 guests