ASCII-Ausgabe von Bäumen

Die ASCII-Ausgabe von Bäumen ist relativ unkompliziert, solange man nicht die Äste malen will. Das Problem bei GNUProlog ist allerdings, daß es gewisse Annehmlichkeiten, die SWI-Prolog kennt, nicht implementiert hat, so predsort, dem man ein Prädikat zum Sortieren von Listen übergeben kann.

Das Prädikat print_nodes bekommt eine sortierte Liste, in der die Baumknoten in der Form p(Name, c(X, Y) angegeben sind, außerdem die letzte x- und y-Koordinate. Der Rekursionsabbruch ist trivial. Rekursiv wird dann zunächst das Prädikat print_node für jeden Knoten mit dem Abstand zwischen dieser und dem letzten Knoten aufgerufen. Das Problem ist, wenn eine neue Ebene anfängt - der letzte Parameter wird gebraucht, um das Prädikat nl zu beweisen und X auf 0 zu setzen. print_node muss zunächst den Abstand zum letzten Knoten in ein Atom schreiben, um dann soviele Leerzeichen auszugeben und dann den Knoten.

print_nodes([], _, _).

print_nodes([p(Node, c(X, Y)) | R], LastX, Y) :-
  NewX is X - LastX,
  print_node(Node, NewX),
  print_nodes(R, NewX, Y).

print_nodes([p(Node, c(X, Y)) | R], _, Depth) :-
  Depth \= Y,
  nl,
  print_node(Node, X),
  print_nodes(R, X, Y).

print_node(Node, Width) :-
  format_to_atom(Format, "~~~dc~~a", [Width]),
  format(Format, [" ", Node]), !.

Der Baum muß allerdings sortiert sein, um ihn auszugeben - und zwar ebenenweise von links nach rechts. Hier kommen xy_sort und myorder ins Spiel. xy_sort benutzt predsort, das als SWI-Prolog-Modul in Prolog implementiert ist und deshalb mit einigen Änderungen auch in GNUProlog verfügbar. myorder gibt als ersten Parameter entweder <, > oder = zurück, je nachdem, wie das erste übergebene Element sich zum zweiten verhält. Dabei sind Element in tieferen Ebenen oder weiter rechts im Baum (Ursprung links unten) größer als höhere linke, so daß bei der Sortierung schließlich die Wurzel das Minimum ist.

print_tree(AL) :-
  xy_sort(AL, SL),
  print_nodes(SL, 0, 0).

xy_sort(L, SL) :-
  predsort(myorder, L, SL).

myorder(=, p(N, c(X, Y)), p(N, c(X, Y))).

myorder(>, p(_, c(_, Y1)), p(_, c(_, Y2))) :-
  Y1 < Y2. 

myorder(>, p(_, c(X1, Y1)), p(_, c(X2, Y2))) :-
  X1 > X2,
  Y1 =< Y2.

myorder(<, p(_, c(_, Y1)), p(_, c(_, Y2))) :-
  Y1 > Y2.

myorder(<, p(_, c(X1, Y1)), p(_, c(X2, Y2))) :-
  X1 < X2,
  Y1 >= Y2.