Sort a list of dotted pairs
Basti...@yahoo.de
I have a list of dotted pairs that may look something like this:
((4 . something) (2 . maybe ) (3 . this ) (7 . last ) (5 . some))
I want it to be sorted after the car of each dotted pair starting with
the lowest number...
((2 . maybe) (3 . this) (4 . something) (5 . some) (7 . last))
Only thing I have done so far is the sort function which does not seem
to help in that case... How could this be done? Thanks.
Grant Rettke
for a list like this:
'(4 2 3 7 5)
but that sort won't work for the list you presented above.
Suppose that you rewrote your sort function so that before you
performed your comparison operation, you passed the two elements to be
compared to another function to "extract the key" on which you want to
sort.
Said function would probably look like this for your existing sort,
identity:
(lambda (x) x)
Update your existing sort to allow for the user to supply a function
for which would extract the keys and pass in the list of numbers.
Then, how would you sort the list of improper lists?
Pascal J. Bourguignon
It depends on how you made this sort function.
If you made it like Common Lisp sort, then you can just write:
(sort a-list < 'key car)
But if you made it like the sort we usually find in scheme libraries,
then you will have to write:
(define (identity x)
x)
(define (get plist key . default)
(cond
((or (null? plist) (null? (cdr plist)))
(if (pair? default)
(car default)
#f))
((eqv? key (car plist))
(cadr plist))
(else
(get (cddr plist) key (if (pair? default)
(car default)
#f)))))
(define (cl-sort list less? . options)
(if (null? options)
(scheme-sort list less?)
(let ((key (get options 'key identity)))
(scheme-sort list (lambda (a b) (less? (key a) (key b)))))))
(cl-sort '((4 . something) (2 . maybe ) (3 . this ) (7 . last ) (5 . some))
<
'key car)
--> ((2 . maybe) (3 . this) (4 . something) (5 . some) (7 . last))
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live.
Abdulaziz Ghuloum
compare elements of the list. So,
(list-sort < '(5 4 3 1 2))
=>
(1 2 3 4 5).
Now expand this a bit by making < an explicit lambda:
(list-sort (lambda (x y) (< x y)) '(5 4 3 1 2))
=>
(1 2 3 4 5)
So, how do we sort a list of strings by their lengths?
(list-sort
(lambda (x y) (< (string-length x) (string-length y)))
'("bbb" "ddddd" "ccc" "a"))
=>
("a" "bbb" "ccc" "ddddd")
So, how do we sort a list of pairs by the numeric values of their
cars?
Kjetil S. Matheussen
Unless efficiency is very important, you can use assv to build
a list of pairs by using your sorted number-list:
(assv 3 '((4 . something) (2 . maybe ) (3 . this ) (7 . last ) (5 . some)))
=> (3 . this)
Kjetil S. Matheussen
> Basti...@yahoo.de writes:
>
> > Dear group,
> >
> > I have a list of dotted pairs that may look something like this:
> > ((4 . something) (2 . maybe ) (3 . this ) (7 . last ) (5 . some))
> >
> > I want it to be sorted after the car of each dotted pair starting with
> > the lowest number...
> >
> > ((2 . maybe) (3 . this) (4 . something) (5 . some) (7 . last))
> >
> > Only thing I have done so far is the sort function which does not seem
> > to help in that case... How could this be done? Thanks.
>
> It depends on how you made this sort function.
> If you made it like Common Lisp sort, then you can just write:
>
> (sort a-list < 'key car)
>
> But if you made it like the sort we usually find in scheme libraries,
> then you will have to write:
>
Not really:
(sort a-list function-which-compares-cars)
Pascal J. Bourguignon
How many gazillons of function-which-compares-such-and-such will you write?
With (sort a-list < 'key car) if we have 20 ways of comparing stuff
(<, string<, symbol<, etc) and 100 ways of extracting keys (100
getters), we can sort 2000 different way.
With (sort a-list function-which-compares-cars) you would have to
write 2000 function-which-compares-some-key-some-way before.
--
__Pascal Bourguignon__
leppie
<k.s.matheus...@notam02.no> wrote:
> Not really:
>
> (sort a-list function-which-compares-cars)
Not really:
(sort function-which-compares-cars a-list)
;-)
leppie
pretty much gave 99% of the answer), but here goes:
(list-sort (lambda (a b) (< (car a) (car b))) '((1 . a)(4 . d)(2 . b)
(5 . e)(3 . c)))
Grant Rettke
> pretty much gave 99% of the answer), but here goes:
Leppie don't get too frustrated! :)
Kjetil S. Matheussen
What?
Sure, common lisp is more convenient than scheme
in most ways, but reimplementing sort just because
you wan't to write "< :key car" instead of
"(lambda (a b) (< (car a) (car b)))" seems silly.
Kjetil S. Matheussen
I've never seen that syntax before.
Pascal J. Bourguignon
Of course, that's why that's not what I did. cl-sort is a wrapper
over scheme-sort that builds that lambda automatically.
--
__Pascal Bourguignon__
leppie
wrote:
>
> > Not really:
>
> > (sort function-which-compares-cars a-list)
>
> I've never seen that syntax before.
Sorry I was thinking of list-sort :)
leppie
wrote:
>
> Sure, common lisp is more convenient than scheme
> in most ways, but reimplementing sort just because
> you wan't to write "< :key car" instead of
> "(lambda (a b) (< (car a) (car b)))" seems silly.
A simple macro could simply do that :)
(define-syntax sort
(syntax-rules (:key)
[(_ lst pred :key key)
(list-sort (lambda (a b) (pred (key a) (key b))) lst)]))
Grant Rettke
> > in most ways, but reimplementing sort just because
> > you wan't to write "< :key car" instead of
> > "(lambda (a b) (< (car a) (car b)))" seems silly.
>
> A simple macro could simply do that :)
Or you could use a Scheme that supports keyword arguments, like PLT :)
Kjetil S. Matheussen
> "Kjetil S. Matheussen" <k.s.mat...@notam02.no> writes:
>
> > On Thu, 24 Jul 2008, Pascal J. Bourguignon wrote:
> >
> >> With (sort a-list function-which-compares-cars) you would have to
> >> write 2000 function-which-compares-some-key-some-way before.
> >>
> >
> > What?
> >
> > Sure, common lisp is more convenient than scheme
> > in most ways, but reimplementing sort just because
> > you wan't to write "< :key car" instead of
> > "(lambda (a b) (< (car a) (car b)))" seems silly.
> >
>
> Of course, that's why that's not what I did. cl-sort is a wrapper
> over scheme-sort that builds that lambda automatically.
>
Oh, okay, sorry, I didn't read closely enough.
Scheme is not scheme though. In Guile, for example, you
could implement cl-sort like this:
(define* (cl-sort alist less? :key (key (lambda (x) x)))
(sort alist (lambda (a b) (less? (key a) (key b)))))