いっかい掴みかけた継続引き渡しの概念を失いそうだったので脳内を保守。お題は、"A Gentle Introduction to Haskell" で紹介されている Haskell の quicksort を Scheme に移して、さらに末尾再帰に書き直すこと。そもそもの Haskell のコードはこれ。

quicksort  []           =  []
quicksort (x:xs)        =  quicksort [y | y <- xs, y<x ]
                        ++ [x]
                        ++ quicksort [y | y <- xs, y>=x]

まずは同じものをSchemeで。

(define (quicksort ls)
  (if (null? ls)
      '()
      (append (quicksort (filter (lambda (x) (> (car ls) x)) (cdr ls)))
              (list (car ls))
              (quicksort (filter (lambda (x) (<= (car ls) x)) (cdr ls))))))

Haskell の表記に比べると filter とか出てくる辺りが痒い。けど仕方ない。とにかくこれを末尾再帰にしてみる。

(define (quicksort/cps ls k)
  (if (null? ls)
      (k '())
      (quicksort/cps (filter (lambda (x) (> (car ls) x)) (cdr ls))
        (lambda (ls-lower)
          (quicksort/cps (filter (lambda (x) (<= (car ls) x)) (cdr ls))
            (lambda (ls-upper) (k (append ls-lower (list (car ls)) ls-upper))))))))

Haskell では継続を安直に捕まえられないのだろうか？
やっぱり集合を扱う際には最初の Haskell のコードが一番しっくりくる。集合論のノリで問題を解きたい場合は Haskell の考え方のほうが扱いやすいのかもしれない。Scheme でも Haskell チックに集合を定義できるマクロを用意すれば同じなのかな。でも、可算無限集合が出てくるたびに delay で関数を定義し直すのはいやだな。