小学校の教員的には順序を付けるのは NG なんだろうけど、数学、とくに集合論では、ある関係によって順序を定義し、集合の要素を整列させたい。ある順序集合が整列できるかどうかは、少なくとも「なんとか伝票のどこに印鑑を押すか」よりは重要な問題なのである。だから邪魔しないでください。

あるリストを集合だと思って、その要素 a と b の関係「a > b」を、「a が b よりもリストの左側にあること」だと考えることにする。そのリストの部分集合（必ずしも降順に並んでいない）を、重複する要素を除外して降順に並べるには、どうやるのが効率的か。つまり、

(a b c d e f g h i j)

というリストがあって、その部分集合、たとえば

(f c a c)

を、もとの親玉のリストと同じ順番

(a c f)

にしたいというはなし。

たぶん、これは、ソートの問題の一般化なんだと思う。順序を定義しているリストをランダムアクセス可能なデータ構造に対応させて、関係「>」を自然数における「>」と同一視してクイックソートかなんかしちゃうのがひとつの解法なのかもしれない。つーか、Cとかで配列を使うなら、自然にそういう方法を選択していることになる。

リストのまま整列させるにはどうするんだろうなあと一時間考えて、ようやくたどり着いた貧相な解法は、ビンソートっぽい方法。

(define (be-same-order ls1 ls2)
  (if (or (null? ls1) (null? ls2))
      '()
      (let C ((ls ls1) 
              (passed '()))
        (cond ((null? ls)
               (be-same-order ls1 (cdr ls2)))
              ((equal? (car ls) (car ls2))
               (cons (car ls)
                     (be-same-order (append passed (cdr ls)) (cdr ls2))))
              (else 
               (C (cdr ls) (cons (car ls) passed)))))))

なんでこんなことを考えているかというと、SICP の ex. 2.84 のせい。2種類の型のどっちがどっちを包含してるか判定する方法を示せっていうんだけど（たとえば有理数と実数はどっちがどっちに含まれるか？）、意味を分離させて機械的に判定するには、あらかじめ数値型のタワー構造を表すリスト (complex real rational integer) を用意しておいて、上の be-same-order みたいなので (type-of x) と (type-of y) を整列させてから car をとればいいじゃん。いいじゃん、とか安直に思って、肝心の be-same-order みたいなのがすぐに用意できない、このどうしようもなさ。