プロローグ リストは単純なデータ構造です。./2
- 空のリストはアトム
[]です。
- 1 つの要素のリスト は
[a]、実際には次の構造です.(a,[])。
- 2 つの要素のリストは、
[a,b]実際には次の構造です。.(a,.(b,[]))
- 3 つの要素のリストは、
[a,b,c]実際には次の構造です。.(a,.(b,.(c,[])))
- 等々。
角括弧表記は、丸括弧の入力に時間を費やさないようにするための構文糖衣です。目に優しいことは言うまでもありません。
これから、リストの先頭(最も外側の./2構造のデータ) とリストの末尾(その最も外側の./2データ構造に含まれるサブリスト) の概念を取得します。
これは基本的に、C の古典的な片方向リストで見られるのと同じデータ構造です。
struct list_node
{
char payload ;
struct list_node *next ;
}
ここで、nextポインターは NULL または別のリスト構造です。
したがって、そこから、reverse/2 の単純な [単純な] 実装を取得します。
reverse( [] , [] ) . % the empty list is already reversed.
reverse[ [X] , [X] ) . % a list of 1 item is already reversed. This special case is, strictly speaking, optional, as it will be handled by the general case.
reverse( [X|Xs] , R ) :- % The general case, a list of length >= 1 , is reversed by
reverse(Xs,T) , % - reversing its tail, and
append( T , [X] , R ) % - appending its head to the now-reversed tail
. %
この同じアルゴリズムは、従来のプログラミング言語で片方向リストを逆にする場合にも機能します。
ただし、このアルゴリズムはあまり効率的ではありません。まず、O(n 2 ) の動作を示します。また、末尾再帰ではありません。つまり、十分な長さのリストはスタック オーバーフローを引き起こします。
プロローグ リストにアイテムを追加するには、リスト全体をトラバースする必要があることに注意してください。プロローグ リストの構造により、先頭に追加するのは簡単な操作です。次のように、既存のリストにアイテムを簡単に追加できます。
prepend( X , Xs , [X|Xs] ) .
プロローグの一般的なイディオムは、アキュムレータでワーカー述語を使用することです。これにより、実装がはるかに効率的になり、(おそらく) 理解しやすくなります。ここでは、アキュムレータを空のリストとしてシードすることにより、リストを逆にします。ソースリストを反復処理します。ソース リストでアイテムに遭遇すると、それを反転リストの先頭に追加し、その結果、反転リストを生成します。reverse/2
reverse(Xs,Ys) :- % to reverse a list of any length, simply invoke the
reverse_worker(Xs,[],Ys) . % worker predicate with the accumulator seeded as the empty list
reverse_worker( [] , R , R ). % if the list is empty, the accumulator contains the reversed list
reverse_worker( [X|Xs] , T , R ) :- % if the list is non-empty, we reverse the list
reverse_worker( Xs , [X|T] , R ) % by recursing down with the head of the list prepended to the accumulator
.
これreverse/2で、O(n) 時間で実行される実装ができました。また、末尾再帰です。つまり、スタックを使い果たすことなく、任意の長さのリストを処理できます。