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 ) 的一个不错的补充。

（我在这里使用我的软件来渲染树）

于 2014-10-31T17:03:20.063 回答