[plt-scheme] Quicksort in Scheme

Joe-

On Jan 4, 2006, at 3:18 PM, Joe Marshall wrote:

> On 1/4/06, Matt Jadud <mcj4 at kent.ac.uk> wrote:
>> I've always wondered: why does Scheme have cons, but not snoc? A  
>> point
>> of history, a point of practicality, neither, or both?
>
> Presumably snoc would work like this?
>
> (snoc '(a b c d e) 'f) =>  '(a b c d e f)
>
> This is trivial to write, and you could write several utilities  
> based on it.

Well, its trivial if you don't care about the semantics of shared  
structure.

It gets tricky if you want set-car! and set-cdr! to behave, um,  
"sensibly" in the presence of snoc.

You might consult Peter Douglass, based on his efforts implementing  
constant-time append/reverse/etc list structures.

-Felix