[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)
> (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)))


(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.