I'm just getting started learning Lisp and I've written a simple
Quicksort implementation as practice. It runs and seems to be fairly
efficient, but I'm curious if there are more concise/idiomatic ways to
do what I've done. For instance, I assume there must be a builtin
equivalent to the partition function I've written.
Here is the code:
(defun partition (pred list)
(labels
((part-helper (pred list in out)
(cond ((null list)
(values in out))
((funcall pred (car list))
(part-helper pred (cdr list)
(cons (car list) in)
out))
(t
(part-helper pred (cdr list)
in
(cons (car list) out))))))
(part-helper pred list '() '())))
(defun qsort (list)
(cond ((null list) '())
(t
(multiple-value-bind (lt gteq)
(partition (Lambda (x) (< x (car list))) (cdr list))
(append
(qsort lt)
(list (car list))
(qsort gteq))))))
A syntax-highlighted version is available at:
http://paste.lisp.org/display/10610
Thanks,
Bill
·········@gmail.com wrote:
> I'm just getting started learning Lisp and I've written a simple
> Quicksort implementation as practice. It runs and seems to be fairly
> efficient, but I'm curious if there are more concise/idiomatic ways to
> do what I've done. For instance, I assume there must be a builtin
> equivalent to the partition function I've written.
But there is a built-in equivalent to the entire sorting function
you've written, so your concern is misplaced. ;)
Heh. Indeed there is. But (sort '(3 4 2 1)) is not very educational.
In any case, what is the name of the built-in function that does
partitioning?
Are loops preferred to recursion in Common Lisp? My Lisp background is
mostly Scheme, so I used recursion without giving it much thought.
Does the Common Lisp standard require tail call optimizations?
Thanks,
Bill
·········@gmail.com writes:
>
> Heh. Indeed there is. But (sort '(3 4 2 1)) is not very educational.
I agree.
It is also, in Common Lisp, also a subtly bad example. SORT is a
destructive function and should not be given constants as arguments.
But I understand the point in clarity of presentation.
> In any case, what is the name of the built-in function that does
> partitioning?
There is none, since the CL standard doesn't mandate any particular
implementation of the SORT algorithm. So there is not necessarily any
partitioning going on during the sort. Now, many implementations will
use the quicksort algorithm, at least for problems over a certain size
and sometimes based on the datatype of sequence being sorted. The
implementation freedom allows vendors to come up with their own clever
ways of handling sorting efficiently.
By the way, although there is no built-in partitioning operator, there
is a MERGE function that will merge sequences maintaining order
specified by a comparison function.
> Are loops preferred to recursion in Common Lisp? My Lisp background is
> mostly Scheme, so I used recursion without giving it much thought.
It varies with the task and the preferences of the programmer. I,
personally, like to use iteration and am a fan of the LOOP macros.
Others have different opinions, but for naturally iterative operations
it seems to me most natural to use loops.
The general CL design philosphy is to provide a rich set of programming
tools and then let the programmer choose which ones are most appropriate
to the problem at hand. The language tries not to get in the way.
> Does the Common Lisp standard require tail call optimizations?
No.
It is not required, which is why some people prefer iteration. Many of
the leading implementations perform this optimization, but it is not
guaranteed, so portable programs cannot rely on it being performed.
There are some other portability limitations, such as potentially small
limits on the number of arguments to function calls, which will
sometimes lead one to use REDUCE or one of the other MAPping functions
instead of APPLYing a function to a long argument list.
--
Thomas A. Russ, USC/Information Sciences Institute
·········@gmail.com writes:
> Heh. Indeed there is. But (sort '(3 4 2 1)) is not very educational.
> In any case, what is the name of the built-in function that does
> partitioning?
>
> Are loops preferred to recursion in Common Lisp? My Lisp background is
> mostly Scheme, so I used recursion without giving it much thought.
> Does the Common Lisp standard require tail call optimizations?
No, it does not. So, loop when that is natural, and recurse
when that is natural (and when you know the bounds are acceptable
to your implementation).
·········@gmail.com wrote:
> Heh. Indeed there is. But (sort '(3 4 2 1)) is not very educational.
> In any case, what is the name of the built-in function that does
> partitioning?
None is available. A CL implementation could use Heapsort to implement
SORT.
>
> Are loops preferred to recursion in Common Lisp? My Lisp background is
> mostly Scheme, so I used recursion without giving it much thought.
> Does the Common Lisp standard require tail call optimizations?
No it does not, although most implementations have it.
In any case, it would not help that much to have tail call optimization
in an implementation of quicksort.
Cheers
--
Marco
Marco Antoniotti wrote:
> In any case, it would not help that much to have tail call optimization
> in an implementation of quicksort.
Sure it would -- it would guarantee a stack depth of O(log n)
(recurse on the smaller segment first, and use a tail call on
the larger segment).
Paul
Paul F. Dietz wrote:
> Marco Antoniotti wrote:
>
>> In any case, it would not help that much to have tail call
>> optimization in an implementation of quicksort.
>
>
> Sure it would -- it would guarantee a stack depth of O(log n)
> (recurse on the smaller segment first, and use a tail call on
> the larger segment).
Well, given that quicksort is inherently recursive, you always have an
expected stack length of O(lg n) even in the very simple implementation
(assuming a good choice of the pivot).
Cheers
--
Marco
Marco Antoniotti wrote:
> Paul F. Dietz wrote:
>> Marco Antoniotti wrote:
>>
>>> In any case, it would not help that much to have tail call
>>> optimization in an implementation of quicksort.
>>
>> Sure it would -- it would guarantee a stack depth of O(log n)
>> (recurse on the smaller segment first, and use a tail call on
>> the larger segment).
>
> Well, given that quicksort is inherently recursive, you always have an
> expected stack length of O(lg n) even in the very simple implementation
> (assuming a good choice of the pivot).
But that depends on having a good pivot. If you tail call on the larger
segment, the stack depth is guaranteed to never exceed exactly log_2 n.
-- MJF
Heh. Indeed there is. But (sort '(3 4 2 1)) is not very educational.
In any case, what is the name of the built-in function that does
partitioning?
Are loops preferred to recursion in Common Lisp? My Lisp background is
mostly Scheme, so I used recursion without giving it much thought.
Does the Common Lisp standard require tail call optimizations?
Thanks,
Bill
·········@gmail.com writes:
> Heh. Indeed there is. But (sort '(3 4 2 1)) is not very educational.
> In any case, what is the name of the built-in function that does
> partitioning?
If you want to sort short lists, then other sort algorithms will be
faster than quicksort.
If you want to sort long lists, then it's better to store the list in
a vector, and implement the normal vector quicksort algorithm.
> Are loops preferred to recursion in Common Lisp? My Lisp background is
> mostly Scheme, so I used recursion without giving it much thought.
> Does the Common Lisp standard require tail call optimizations?
CL doesn't require it, but most implementations have it.
Few people would use an implementation without it anyways.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
Pascal Bourguignon <····@mouse-potato.com> writes:
> CL doesn't require it, but most implementations have it.
Is there a summary table somewhere for that?
> Few people would use an implementation without it anyways.
Do you have some statistics on that?
Christopher C. Stacy wrote:
> Pascal Bourguignon <····@mouse-potato.com> writes:
>
>>CL doesn't require it, but most implementations have it.
>
> Is there a summary table somewhere for that?
That would be a good idea. Maybe start a page on lisp.tech.coop, or so,
to collect information about tail call optimizations in Common Lisp
implementations.
Pascal
--
In computer science, we stand on each other's feet. - Brian K. Reid
·········@gmail.com writes:
> I'm just getting started learning Lisp and I've written a simple
> Quicksort implementation as practice. It runs and seems to be fairly
> efficient, but I'm curious if there are more concise/idiomatic ways to
> do what I've done. For instance, I assume there must be a builtin
> equivalent to the partition function I've written.
>
> Here is the code:
>
> (defun partition (pred list)
> (labels
> ((part-helper (pred list in out)
You don't need to pass pred again here.
> (cond ((null list)
> (values in out))
> ((funcall pred (car list))
> (part-helper pred (cdr list)
> (cons (car list) in)
> out))
> (t
> (part-helper pred (cdr list)
> in
> (cons (car list) out))))))
> (part-helper pred list '() '())))
>
> (defun qsort (list)
> (cond ((null list) '())
> (t
> (multiple-value-bind (lt gteq)
> (partition (Lambda (x) (< x (car list))) (cdr list))
> (append
> (qsort lt)
> (list (car list))
> (qsort gteq))))))
I'd say the idiom to quicksort is to use a vector. Also, it might be
useful to parametrize the comparizon operator. So:
(defun qsort (sequence &key test)
(quicksort (etypecase sequence
(list (coerce sequence 'vector))
(vector sequence)) test))
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live
·········@gmail.com writes:
> I'm just getting started learning Lisp and I've written a simple
> Quicksort implementation as practice.
Funny thing: Some days ago i also hacked a quicksort (for some
simple testing). I used arrays and my version may be a bit
buggy, but maybe it could be of interest to you (even if not very
lispish, but i hope with reasonable performance):
,----
| (defun partition (array x)
| (let ((left 0)
| (right (1- (length array))))
| (loop
| (loop while (< (aref array left) x) do
| (incf left))
| (loop while (> (aref array right) x) do
| (decf right))
| (if (>= left right) (return (values array left)))
| (rotatef (aref array left) (aref array right)))))
|
| (defun qsort (array)
| (let* ((x (aref array 0))
| (p (nth-value 1 (partition array x)))
| (array-left (make-array p :displaced-to array))
| (array-right (make-array (- (length array) p 1) :displaced-to array :displaced-index-offset (1+ p))))
| (when (> (length array-left) 1)
| (qsort array-left))
| (when (> (length array-right) 1)
| (qsort array-right))))
`----
--
Stefan.
If you want a quick and dirty quicksort which only works on lists,
here's one:
(defun qsort (list)
(if (consp list)
(destructuring-bind (middle . rest) list
(append (qsort (remove-if-not #'(lambda (x) (< x middle))
rest))
(list middle)
(qsort (remove-if #'(lambda (x) (< x middle)) rest))))
list))
Of course, this is hideously sub-optimal. You should be using Lisp's
built-in sort function. And you should probably use mergesort for
lists.
-Peter
After learning a little more, I've rewritten the code to this:
(defun partition (pred list)
(let (in out)
(loop for item in list do
(if (funcall pred item)
(setf in (cons item in))
(setf out (cons item out))))
(values in out)))
(defun qsort (list)
(if (null list)
()
(destructuring-bind (pivot . rest) list
(multiple-value-bind (lt gteq)
(partition (lambda (x) (< x pivot)) rest)
(append (qsort lt) (list pivot) (qsort gteq)))))))
It's definitely shorter, and a lot less Scheme-ish. Any thoughts on
this latest version?
Bill
·········@gmail.com writes:
> Is there a way to make my solution more functional? For instance, how
> can I get around using setf in partition?
I wouldn't worry too much about the setf in partition. Any efficient
implementation will end up doing the equivalent setf regardless of how
you write it (a pure tail-recursive solution will be reusing the stack
frame, in effect `side-effecting' the memory locations the variables
live in).
But since you ask...
;; Recursive
;; May overflow stack on long lists.
;; element order is preserved.
(defun partition (pred list)
(if (consp list)
(multiple-value-bind (in out)
(partition pred (cdr list))
(let ((item (car list)))
(if (funcall pred item)
(values (cons item in) out)
(values in (cons item out)))))
(values '() '())))
;; Tail recursive form
;; will be iterative if compiler optimizes it.
;; Elements will be reversed.
(defun partition (pred list)
(labels ((helper (scan in out)
(if (consp scan)
(let ((item (car scan)))
(if (funcall pred item)
(helper (cdr scan) (cons item in) out)
(helper (cdr scan) in (cons item out))))
(values in out))))
(helper list '() '())))
You could also simply make two passes using the predicate and its
complement. That seems inefficient, but depending on the application
it may not matter.
·········@gmail.com writes:
>
> Is there a way to make my solution more functional? For instance, how
> can I get around using setf in partition?
>
> (defun partition (pred list)
> (let (in out)
> (loop for item in list do
> (if (funcall pred item)
> (setf in (cons item in))
> (setf out (cons item out))))
> (values in out)))
Well, you can make it more functional with mapping functions, or by
using the LOOP collect clause. (The latter, of course, is not really
functional, it just hides the SETF from surface view).
Note this is certainly less efficient:
(defun partition (pred list)
(values (mapcan (lambda (x) (if (funcall pred x) (list x) nil)))
(mapcan (lambda (x) (if (funcall pred x) nil (list x))))))
--
Thomas A. Russ, USC/Information Sciences Institute
·········@gmail.com writes:
| After learning a little more, I've rewritten the code to this:
|
| (defun partition (pred list)
| (let (in out)
| (loop for item in list do
| (if (funcall pred item)
| (setf in (cons item in))
| (setf out (cons item out))))
| (values in out)))
More idiomatic would be
(defun partition (pred list)
(let (in out)
(dolist (item list)
(if (funcall pred item)
(push item in)
(push item out)))
(values in out)))
or even
(defun partition-2 (pred list)
(let (in out)
(dolist (item list)
(push item (if (funcall pred item) in out)))
(values in out)))
| Is there a way to make my solution more functional? For instance, how
| can I get around using setf in partition?
I'm not a loop wizard but there's
(defun partition-4 (pred list)
(loop for item in list
if (funcall pred item)
collect item into in
else
collect item into out
finally return (values in out)))
but personally, if I wanted to avoid setfs or pushes, I'd recurse.
Another method for partitioning, similar to your loop method, is this
one using cl-utilities <http://www.cliki.net/cl-utilities>:
(defun partition-5 (pred list)
(with-collectors (in out)
(dolist (item list)
(if (funcall pred item)
(in item)
(out item)))))
The WITH-COLLECTORS macro establishes some local functions (in this
case IN and OUT) which, when called, accumulate an argument onto a
list. WITH-COLLECTORS then returns the collected lists with VALUES in
the order in which they were specified.
This collection is done by destructively adding to the end of lists,
which is usually a little more efficient than the PUSH/NREVERSE idiom
except on CLISP (on which any built-in function is going to be faster
than Lisp code).
This has been a shameless and informative plug. Cheers!
-Peter
Since this is for newbies.
Dan Schmidt <····@dfan.org> writes:
> or even
>
> (defun partition-2 (pred list)
> (let (in out)
> (dolist (item list)
> (push item (if (funcall pred item) in out)))
> (values in out)))
Although Clisp seems to handle this, every other lisp it tried
complains about a missing (SETF IF). I don't think that there is any
requirement that IF has a setf expander or ever returns a place.
> I'm not a loop wizard but there's
>
> (defun partition-4 (pred list)
> (loop for item in list
> if (funcall pred item)
> collect item into in
> else
> collect item into out
> finally return (values in out)))
I think you need 'finally (return (values in out))' since I don't see a
way using a 'return' construct within a 'finally' clause.
--
Barry Fishman