haskellではquicksortがやたらエレガントに書ける。
（[1]を参考にしました）
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = qsort smaller ++ [x] ++ qsort larger
where
smaller = [ a | a <- xs, a <= x]
larger = [ b | b <- xs, b > x ]
これの発想をちょっと真似たらschemeでもなかなかうまくかけた。（気がする）
(use srfi-11)
(define (lefter&righter ord a lst)
(let loop ((rmn lst) (lefter '()) (righter '()))
(cond ((null? rmn) (values lefter righter))
((eq? (car rmn) a) (loop (cdr rmn) lefter righter))
((ord (car rmn) a) (loop (cdr rmn) (cons (car rmn) lefter) righter))
(else (loop (cdr rmn) lefter (cons (car rmn) righter))))))
(define (quicksort ord lst)
(if (null? lst) lst
(let-values (((lefter righter) (lefter&righter ord (car lst) (cdr lst))))
(append (quicksort ord lefter) `(,(car lst)) (quicksort ord righter)))))
初めにHaskell版のwhere以下に相当する関数を作っている。
（これ自体きっと有用だろう。）
あとはHaskell版とほとんどおなじだ。
新しい点としては順序ordを指定できること。
これで文字列間の順序なんかも定め整列させることができる。
あとこのプログラムを作っている過程で多値に目覚めてしまった。
別になくてもいいけどあるととても楽！
[1] プログラミングHaskell Graham Hutton 著 山本和彦 訳
