2006/09/01

いまさら Code Kata をやってみようと思った。といっても Kata 1 はコードを書くわけじゃないのか。というわけで Kata 2 から。うーん、二分木の探索ねえ。めんどくさいので勝手にクイックソートに問題を変更させていだきます。でも4つしか思いつきません。しかも二個目は一個目からコピペしただけのいんちき。ほかにどんな方法があるんだろう。
(use srfi-1)
(define ls '(4 9 2 5 8 7 3 1 6 4))

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

(define (quicksort2 ls)
(call/cc
(lambda (k)
(if (null? ls)
k
(append (filter (lambda (x) (> (car ls) x)) (quicksort2 (cdr ls)))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (quicksort2 (cdr ls))))))))
(quicksort2 ls)

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

(define (quicksort/cps2 ls k)
(if (null? ls)
(k '())
(quicksort/cps2
(filter (lambda (x) (> (car ls) x)) (cdr ls))
(lambda (ls-lower)
(quicksort/cps2 (filter (lambda (x) (<= (car ls) x)) (cdr ls))
(lambda (ls-upper)
(k (append ls-lower
(list (car ls))
ls-upper))))))))
(quicksort/cps2 ls (lambda (k) k))
Code Kata というより Scheme Kata?
どれも基本となる部分は filter で、芸がなくって本当にがっかりだ。いろんなバリエーションを考えるのが Kata 2 の目的な気がするんだけど。なんかもうこう完全にびっくりするぐらい違うのが思いつきたい。

0 件のコメント: