Re: (dsssl) sorting a node list

[Jean-Marie Kubek <kubek@xxxxxxxxxxxxxxxxxx>]

Jany Quintard <jany.quintard@xxxxxxx> writes:

> I am looking in the spec and the archive (general archive is broken?) to
> find a way to sort a node list.
> Does anyone know a simple way to do it?
> 

Yes, take a 'basic' quicksort procedure on lists, abstract it in order
to create a generic factory procedure for 'quicksorting' collections
and call this generic procedure using the basic functions on
node-lists. You'll find an example at the end of this message :)

But I found the node-list-sort procedure defined below rather
inefficient (because of the constructor node-list ?) and preferred to
do the following :

        (define (node-list-sort nl)
           (list->node-list
               (list-sort 
                  (node-list->list nl))))




;  1- quicksort-maker : a generic quicksort procedure factory on abstract collections :

(define (quicksort-maker cons null? car cdr  append empty)
  ; cons --> add an element to a collection
  ; null? --> empty collection predicate
  ; car --> head of the collection
  ; cdr --> rest of the collection
  ; append --> concat two collections
  ; empty --> the empty collection
  (letrec
    ((collect
       (lambda (pivot ls lgroup rgroup less?)
         (if (null? ls)
             (append (quicksort lgroup less?) 
		     (cons pivot (quicksort rgroup less?)))
             (if (less? pivot (car ls))
                 (collect pivot (cdr ls) lgroup (cons (car ls) rgroup) less?)
                 (collect pivot (cdr ls) (cons (car ls) lgroup) rgroup less?)))))
     (quicksort
      (lambda (ls less?)
	(if (or (null? ls) (null? (cdr ls)))
	    ls
	    (collect (car ls) (cdr ls)  empty empty less?)))))
    quicksort))
        
; 2- a list sorting procedure :

   (define list-sort (quicksort-maker cons 
				   null? 
				   car 
				   cdr 
				   append 
				   '()))
; 3- a node-list sorting procedure :

   (define node-list-sort (quicksort-maker node-list
					node-list-empty? 
					node-list-first 
					node-list-rest
					node-list 
					(empty-node-list)))

Jean-Marie.

                               --------

Jean-Marie Kubek
Institut National des Sciences Appliquées
Toulouse
France

 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist