[plt-scheme] Quicksort in Scheme

From: Greg Woodhouse (gregory.woodhouse at sbcglobal.net)
Date: Wed Jan 4 15:36:01 EST 2006

--- Doug Orleans <dougorleans at gmail.com> wrote:
> 
> SRFI 1 has xcons:
> 
>   xcons d a -> pair 
> 
>     (lambda (d a) (cons a d))
> 
>     Of utility only as a value to be conveniently passed to
>     higher-order procedures.
> 
>       (xcons '(b c) 'a) => (a b c)
> 
>     The name stands for "eXchanged CONS."
> 

Maybe something like this

> (define snoc
    (lambda (l m)
      (if (null? l) (list m)
          (append (list (car l)) (snoc (cdr l) m)))))
> (snoc '() 1)
(1)
> (snoc '(1 2 3) 4)
(1 2 3 4)


That kind of gets back to something I posted awhile ago (maybe one of
my first here) where I was thinking about using data structures other
than lists. Presumably, it would be possible to use two-ended lists
like this, so long as both cons and snoc had inverses. I.e., something
equivalent to the invariants

(equal? a (car (cons a b)))

and

(equal? b (cdr (cons a b)))


===
Gregory Woodhouse  <gregory.woodhouse at sbcglobal.net>
"If you give someone Fortran, he has Fortran.
If you give someone Lisp, he has any language he pleases."
--Guy L. Steele, Jr. 


Posted on the users mailing list.