sortの続き

id:maoe:20060201:1138822944

ああ、そうか。partitionを使えば良かったんだ。というわけで、partitionを使って書き直すとこうなった。

(define (sort lst cmpfn)
  (let rec ((lst lst))
    (cond ((null? lst) '())
          ((null? (cdr lst)) lst)
          ((null? (cddr lst))
           (if (cmpfn (car lst) (cadr lst))
               lst
               (list (cadr lst) (car lst))))
          (else
           (let ((pibot (car lst)))
             (receive (bigger smaller)
                 (partition (cut cmpfn pibot <>) (cdr lst))
               (append (rec smaller) (list pibot) (rec bigger))))))))

(末尾再帰版は省略)

自分は元々Emacs LispからLispを覚えたんで、多値を使うという発想自体がなかった。

あと、internal define, letrec, named letの違いは自分も気になっていたのですが、なんでもλによると、internal defineとletrecの実行効率は同じで、どちらを使うかは単なるスタイルの問題だそうです(例9のコメント参照)。さらに同ページの脚注3では、named letとletrecは引数を評価するときの環境に関数名が束縛されているかどうかが違うということが書かれていました。