1

プロローグにクイックソートのコードがあります：

gt(X,Y):- X @> Y.
conc([], List, List).
conc([Head|Tail], List1, [Head|List2]):- conc(Tail, List1, List2).

quicksort([], []).
quicksort([X|Tail], Sorted):-
    split(X,Tail,Small,Big),
    quicksort(Small,SortedSmall),
    quicksort(Big, SortedBig),
    conc(SortedSmall, [X|SortedBig], Sorted).

split(X,[],[],[]).
split(X,[Y|Tail],[Y|Small],Big):-
    gt(X,Y),!,
    split(X,Tail,Small, Big).
split(X,[Y|Tail],Small,[Y|Big]):-
    split(X,Tail,Small,Big).

例はquicksort([3,2,4,1,5], Sorted)です。私はこれをほとんど描きましたが、 のリストのトレースしか見つけられず、番号Small=[2, 1]のリストに対して同じことを行うことができませんでしたBig。このコードの図を描くのを手伝ってくれる人はいますか? プログラムの実行中のトレースを理解したい。本当に感謝します！

4

1 に答える 1

2

証明木の描画は魅力的なテーマであり、完全に解決されたわけではありません。

証明木にはデバッグ中に不可欠な情報が含まれていますが、各ステップがアクティベーション番号でマークされているため、トレースから形状を推測することは容易ではありません。そして、プルーフ ツリーが明らかにする膨大な量の情報に邪魔されて、私たちの注意力は限られています。

ただし、形状は復元できます。たとえば、トレースを解析して (たとえば) Graphviz に変換する DCG...

しばらくお待ちください。コードを投稿してみます。あなたの質問は、私の小さな Prolog IDE ( loqt )への素晴らしい追加と思われるものを実装する機会を与えてくれます。

(ここで SW を使用してツリーをレンダリングします)

于 2014-10-31T17:03:20.063 に答える