|
|
 |
 |
 |
 |
Scheme Programming Language
|
 |
 |
 |
 |
|
|
|
|
newbie: sort ...?
Hi,
I'm playing with the sort procedure in DrScheme. I can't seem to make it
work - (because I don't know how to use it :)
(sort list less-than?)
The info from the DrScheme help is below. As far as I can tell, there is no
built-in procedure less-than? I'm assuming the built-in sort uses the
evaluation procedure (less-than?) to sort list elements so that the
less-than? procedure evaluates as #t then it sorts in ascending order (by
ASCII value??) and #f, descending order.
(a) What would the less-than? procedure look like? Or am I looking in the
wrong place?
(b) I can write a quicksort procedure based on the algorithm but it would be
nice to know how to use the built-in sort routine. If anyone happens to
have the code for this Scheme sort procedure (the code that created the
procedure sort), I'd appreciate a look.
Kindest regards,
Mike
Help says:
(sort list less-than?) PROCEDURE
Sorts list using the comparison procedure less-than?. This implementation is
stable (i.e., if two elements in the input are ``equal,'' their relative
positions in the output will be the same).
Mike <mcu87 @bigpond.net.au> wrote: > (a) What would the less-than? procedure look like? [...]
(sort '(3 1 4 2 5) <=) => (1 2 3 4 5)
(sort '("world" "hello") string<=?) => ("hello" "world")
(sort '(#\o #\o #\f) char<=?) => (#\f #\o #\o)
(sort '((2 second) (1 first))
(lambda (x y)
(< (car x) (car y)))) => ((1 first) (2 second))
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Mike writes: > I'm playing with the sort procedure in DrScheme. I can't seem to > make it work - (because I don't know how to use it :) > (sort list less-than?)
> The info from the DrScheme help is below. As far as I can tell,
> there is no built-in procedure less-than? I'm assuming the built-in
> sort uses the evaluation procedure (less-than?) to sort list
> elements so that the less-than? procedure evaluates as #t then it
> sorts in ascending order (by ASCII value??) and #f, descending
> order.
kind of thing you can use in that argument position. Note that the
value of the built-in variable with the name "list" is not a list,
either. (It's a procedure.)
You provide the comparison operator for the elements of the list when
calling sort. For strings, I suppose a kind of default case is
string<?, or string>? if you want the other order. For numbers, use <
or >.
(The documentation, which I snipped, does not make it quite clear that
string<? is meant instead of string<=?. I think it is, though.)
> (a) What would the less-than? procedure look like? Or am I looking
> in the wrong place?
To sort your strings by length,
(define (shorter? s t)
(< (string-length s)
(string-length t)))
and I hope you know now what to do with shorter?. This one is good for
illustrating the stability of a sort.
> (b) I can write a quicksort procedure based on the algorithm but it
I'd suggest a merge sort for lists.
Jussi Piitulainen <jpiit @ling.helsinki.fi> wrote: > (The documentation, which I snipped, does not make it quite clear that > string<? is meant instead of string<=?. I think it is, though.)
not think that it is accurate, because
(apply < (sort '(2 1 2) <)) => #f
but using <= yields:
(apply <= (sort '(2 1 2) <=)) => #t
IMO
(sort '(2 1 2) <) => undefined
would be a perfectly reasonable result.
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Doh! Of course ...
Hard to type with a bucket over my head :)
Thanks Nils.
"Nils M Holm" <before-2007-07@online.de> wrote in message
news:f1d7al$v32$1@online.de...
> Mike <mcu87 @bigpond.net.au> wrote: >> (a) What would the less-than? procedure look like? [...] > That depends on the type of data you want to sort:
> (sort '(3 1 4 2 5) <=) => (1 2 3 4 5)
> (sort '("world" "hello") string<=?) => ("hello" "world")
> (sort '(#\o #\o #\f) char<=?) => (#\f #\o #\o)
> (sort '((2 second) (1 first))
> (lambda (x y)
> (< (car x) (car y)))) => ((1 first) (2 second))
> --
> Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Nils M Holm writes: > Jussi Piitulainen wrote: >> (The documentation, which I snipped, does not make it quite clear >> that string<? is meant instead of string<=?. I think it is, >> though.) > Although this probably is what the documentation meant, I do
> not think that it is accurate, because
> (apply < (sort '(2 1 2) <)) => #f
> but using <= yields:
> (apply <= (sort '(2 1 2) <=)) => #t
Testing with string-length and either < or <= should show the
difference.
The name less-than?, rather than less-than-or-equal?, suggests
strictness to me, and so does my recollection of Richard O'Keefe's
merge sort that definitely used a <-type test.
The two predicates <? and <=?, if total, are inter-definable anyway,
so I think we can assume the existence of the other and accept
(apply <=? (sort '(2 1 2) <?)) => #t
as the relevant invariant.
Hi Jussi,
Doh and double damn - it never occurred to me that I could roll my own
sorting process.
Of course the less-then? wasn't anything other than a procedure to compare
two values and so <= or your shorter? would work perfectly. I can do
interesting damage with this ...
About to play with the merge sorts ... BTW, it's 4.30 am in Brisbane where I
am. I used to have a life - swear to god.
Thank you.
Mike
"Jussi Piitulainen" <jpiit @ling.helsinki.fi> wrote in message
> To sort your strings by length,
> (define (shorter? s t)
> (< (string-length s)
> (string-length t)))
> and I hope you know now what to do with shorter?. This one is good for
> illustrating the stability of a sort.
>> (b) I can write a quicksort procedure based on the algorithm but it
> I'd suggest a merge sort for lists.
Hi,
Not trying to answer my own question but here is a link to this document and
the source code for a Scheme sorted? procedure - most of you may already
know of it.
http://www.engin.umd.umich.edu/CIS/course.des/cis400/scheme/sorts.htm...
The code itself is very interesting to examine for anyone interested in such
things.
Kindest regards,
Mike
__________________
Quote from the webpage:
Many Scheme systems provide some kind of sorting functions. They do not,
however, always provide the same sorting functions. Because sort and sort!
are not in the standard, there is very little agreement about what these
functions look like. Each of the five functions has a required *last*
parameter which is a comparison function. A comparison function f is a
function of 2 arguments which acts like <. For example, (not (f x x)) (and
(f x y) (f y z)) => (f x z) The standard functions <, >, char?, char-ci?,
string?, string-ci? are suitable for use as comparison functions. Think of
(less? x y) as saying when x must *not* precede y. (sorted? sequence less?)
returns #t when the sequence argument is in non-decreasing order according
to less? (that is, there is no adjacent pair ... x y ... for which (less? y
x)) returns #f when the sequence contains at least one out-of-order pair. It
is an error if the sequence is neither a list nor a vector. (merge list1
list2 less?) This merges two lists, producing a completely new list as
result. (merge! list1 list2 less?) merges two lists, re-using the pairs of
list1 and list2 to build the result. If the code is compiled, and less?
constructs no new pairs, no pairs at all will be allocated. The first pair
of the result will be either the first pair of list1 or the first pair of
list2, but you can't predict which. (sort sequence less?) accepts either a
list or a vector, and returns a new sequence which is sorted. The new
sequence is the same type as the input. Always (sorted? (sort sequence
less?) less?). The original sequence is not altered in any way. The new
sequence shares its _elements_ with the old one; no elements are copied.
(sort! sequence less?) returns its sorted result in the original boxes. If
the original sequence is a list, no new storage is allocated at all. If the
original sequence is a vector, the sorted elements are put back in the same
vector. Note that these functions do NOT accept a CL-style ":key" argument.
A simple device for obtaining the same expressiveness is to define (define
(keyed less? key) (lambda (x y) (less? (key x) (key y)))) and then, when you
would have written (sort a-sequence #'my-less :key #'my-key) in Common Lisp,
just write (sort! a-sequence (keyed my-less? my-key)) in Scheme.
Ya, that's the O'Keefe document that I mentioned. Glad to see it's
still alive. Do be sure to use < with it, not <=.
Interestingly, the document states:
| Think of (less? x y) as saying when x must *not* precede y.
which effectively describes a non-strict operator, while the rest
of the document explicitly deals with strict operators.
Is there any good reason to prefer strict operators? Why should I
introduce invariants to explain something that non-strict operators
can do perfectly well?
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Nils M Holm writes: > Jussi Piitulainen wrote: >> Mike writes: >>> http://www.engin.umd.umich.edu/CIS/course.des/cis400/scheme/sorts.htm... >> Ya, that's the O'Keefe document that I mentioned. Glad to see it's
>> still alive. Do be sure to use < with it, not <=.
> Interestingly, the document states:
> | Think of (less? x y) as saying when x must *not* precede y.
> which effectively describes a non-strict operator, while the rest
> of the document explicitly deals with strict operators.
*must* precede y, or y must *not* precede x. Or else "precede" does
not mean what I think it does.
> Is there any good reason to prefer strict operators?
I think you can write a sort algorithm either way, but when it's
written one way, it should be used that way. The failure to do so
affects stability: whether equivalent elements get swapped.
> Why should I introduce invariants to explain something that
> non-strict operators can do perfectly well?
"Invariant" was not the right term. "Post-condition", true afterwards.
The post-condition that you used, (apply <= (sort ... <=)), is nice in
its use of the same predicate for sorting and checking. O'Keefe's
(sorted? (sort ... <) <) is the same for a strict predicate.
Nils M Holm writes:
> Is there any good reason to prefer strict [snip]
Getting more and more confused and not liking it, I
invented a setting for experimenting with the
different possibilities: two sort procedures that
only sort two values and take the two different kinds
of order predicates.
(define (sort/si x y <?) ; strictly increasing
(if (<? y x)
(list y x)
(list x y)))
(define (sort/nd x y <=?) ; non-decreasing
(if (<=? x y)
(list x y)
(list y x)))
(define (by o k)
(lambda (x y)
(o (k x) (k y))))
These show non-stable behaviour when values compare
equal and the wrong kind of predicate is used:
(sort/si "foo" "bar" (by <= string-length))
(sort/nd "foo" "bar" (by < string-length))
Correct calls work stably:
(sort/si "foo" "bar" (by < string-length))
(sort/nd "foo" "bar" (by <= string-length))
Non-ties come right either way.
|
|
|
|
|
|
Add to del.icio.us |
Digg this |
Stumble it |
Powered by Megasolutions Inc