• Showing Page History #35723

Show page source of ExList #34611

[FrontPage ← 先頭のページに戻る]


== デカルト言語のプログラム:リストの操作


リストの操作を行うプログラムについて説明しましょう。

デカルト言語では、リストの操作をとても簡潔に行えます。

以下のリストの操作のプログラムは、デカルト言語と同様に1階述語論理をベースにしたprolog言語のプログラムから持ってきたものです。
(prologの持つ機能は、ほぼデカルト言語のサブセットの位置付けとなっています。)


以下のリスト操作のプログラムは、デカルト言語のリリースパッケージのexampleディレクトリの中のlistファイルにもありますので参照してみてください。


=== 1. リストの追加

形式:<append #out #in1 #in2>


#in1と#in2のリストを連結して、#outに設定します。

他の文書でも、説明に使用していますが、実に便利なプログラムです。


プログラム:

 <append #X () #X >;

 <append (#A : #Z) (#A : #X)  #Y>

    <append #Z #X #Y >;


実行例:

 ?<append #out (a b c) (d e f)>;

 result --

    <append (a b c d e f) (a b c) (d e f)>

 -- true


[[BR]]
このappendでおもしろいのは、逆に入力の片方を変数にして、出力に結果のリストを設定すると、リストの差分が求められることです。

以下をご覧ください。

  ? <append (a b c d e f) (a b c) #x>;

  result --

    <append (a b c d e f) (a b c) (d e f)>

  -- true


[[BR]]
#xに(a b c d e f) から (a b c)を除いた(d e f)が結果として出力されます。


[[BR]]
反対の入力を変数にしても同様です。

  ? <append (a b c d e f) #x (e f)>

  result --

     <append (a b c d e f) (a b c d) (e f)>

  -- true



=== 2. リストの逆転

形式:<reverse #out #in>

リスト#inを逆の順に変換して#outに設定します。

プログラム:

 <reverse () ()>;

 <reverse #r (#x: #l) >	

    <reverse #r1 #l >

    <append #r #r1 (#x) >;


実行例:

 ?<reverse #out ( a b c)>;

 result --

    <reverse (c b a) (a b c)>

 -- true


reverseの場合もappendと同様に、出力に値を設定すると、逆に入力に結果が得られます。

 ?<reverse  ( a b c) #in>;

 result --

    <reverse (a b c) (c b a)>

 -- true


=== 3. リストの最後を獲得

形式:<last #out #list>

リスト#listの最後の要素を、#outに設定します。


プログラム:

 <last #x (#x)>;

 <last #x (_:#list)>

    <last #x #list>;


実行例:

 ?<last #out (a b (c d))>;

 result --

    <last (c d) (a b (c d))>

 -- true


lastの場合は、入出力を逆にして出力にデータを入れても、appednやリバースのようにはいきません。最後の値が分かってもリスト全体がどのようなものになるのかは無限の可能性があるからです。

さて、lastの場合はどのような結果になるかというと、実は以下のような結果となります。

 ? <last (c d) #x>;

 result --
 
    <last (c d) ((c d))>

 -- true



=== 4. リストの中のメンバーの確認

形式: <member #mem #list>

#listの中に#memが含まれているか判定します。

結果は述語の実行結果で判定します。

メンバーに含まれていればtrueとなり、含まれていなければunknownとなります。




プログラム:

 <member #x (#x : #rest)>;

 <member #x (#y : #rest)>

    <member #x #rest>;

実行例:

 ?<member a (a b c)>;

 result --

    <member a (a b c)>

 -- true


[[BR]]
 ?<member d (a b c)>;

 result --

    <member d (a b c)>

 -- unknown



=== 5. リストの平坦化

形式:<flatten #out #in>


リスト#inの中の入れ子状のリストを、平坦なリストに変換して#outに設定します。

たとえば、複雑なリスト(a (b c (d e) f)) は、単純な(a b c d e f)とフラットなリストに変換されます。

このようなリストの複雑な操作を、わずか9行で実現できてしまいます。


プログラム:

 <flatten () ()>;

 <flatten #list (#x:#l)>

    ::sys <isList #x>

    <flatten #list1 #x>

    <flatten #list2 #l>

    <append #list #list1 #list2>;

 <flatten #list (#x:#l) >

    <flatten #list2 #l>

    <append #list (#x) #list2>;


実行例:

 ?<flatten #out (a (b (c d) e (f (g)) h i) j k)>;

 result --

    <flatten (a b c d e f g h i j k) (a (b (c d) e (f (g)) h i) j k)>

 -- true


=== 6. リストの要素の差分

形式:<difference #out #in1 #in2>


リスト#in1と#in2のリストの要素の中の共通でない要素を差分として、#in1にあるが#in2にない要素のリストを#outに設定します。

リストの要素の順番には関わらずに含まれている要素だけに着目して差分を抽出します。


プログラム:

 <difference () () _ >;

 <difference #diff (#x:#set1) #set2 >

    <member #x #set2> 

    <difference #diff #set1 #set2>;

 <difference (#x : #diff) (#x:#set1) #set2>

    <difference #diff #set1 #set2>;


実行例:

 ?<difference #out (a b c d e f g h i j ) (1 2 3 b c l i m j a)>;

 result --

    <difference (d e f g h) (a b c d e f g h i j) (1 2 3 b c l i m j a)>

 -- true


=== 7. リストの要素がすべて等しいか判定


形式:<equal_sets #set1 #set2>

リスト#set1と#set2の要素がすべて等しいか判定します。

リストの中の要素の順番に関わらず、含まれている要素が等しいかのみを判定します。


プログラム:

 <equal_sets #set1 #set2>

    <difference () #set1 #set2>

    <difference () #set2 #set1>;


 ?<equal_sets (a b c d e f g h i j ) (d e f a b c g h i j )>;

 result --

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

 -- true


=== 8. リストの積集合

形式: <intersect #out #in1 #in2>

リスト#in1と#in2の要素を比較し、共通な要素のリストを#outに設定します。

要素の順番に関わらず、共通の要素が抽出されます。


プログラム:

 <intersect () () _ >;

 <intersect (#x:#int) (#x:#set1) #set2>

    <member #x #set2>

    <intersect #int #set1 #set2>;

 <intersect #int (_:#set1) #set2>

    <intersect #int #set1 #set2>;


実行例:

 ?<intersect #out (i j k l m) (n m l k)>;

 result --

    <intersect (k l m) (i j k l m) (n m l k)>

 -- true

=== 9. リストの和集合

形式:  <union #out #in1 #in2>

リスト#in1と#in2の要素を併せ、共通する要素は重複しないように一つにして、すべての要素を#outに設定します。


プログラム:

 <union #out () #out>;

 <union #out (#x : #in1) #in2>

     <member #x #in2>

     <union #out #in1 #in2>

     ;

 <union (#x : #out) (#x : #in1) #in2>

     <union #out #in1 #in2>

     ;

実行例:

 ?<union #x (c b a) (a d c e f)>;

 result --

    <union (b a d c e f) (c b a) (a d c e f)>

 -- true


=== 10. リストの要素

形式: <subset #subset #set>

#subsetが#setのサブセットであるときtrueになります。

プログラム:

 <subset () #set>;

 <subset (#x : #subset) #set>

    <member #x #set>

    <subset #subset #set>;

実行例:

 ?<subset (a b c) (f g b h d c i a)>;

 result --

    <subset (a b c) (f g b h d c i a)>

 -- true


=== 11. リストの併合

形式: <join #out #in1 #in2>

#in1と#in2を併合したリストを#outに設定します。併合は#in1と#in2の対応する順番の要素ごとに行われます。つまり、#in1の1番目と#in2の1番目が#outに追加され、次は2番目同士の要素が並び、これをリストの最後の要素まで繰り返して#outに設定していきます。


プログラム:

 <join () () ()>;

 <join (#x #y : #out) (#x : #in1) (#y : #in2)>

    <join #out #in1 #in2>;

実行例:

 ?<join #x (a b c) (1 2 3)>;

 result --

    <join (a 1 b 2 c 3) (a b c) (1 2 3)>

 -- true