Prolog Rekursion funktioniert nicht in die andere Richtung

Question

ich Prolog lerne und ich habe in den Code stecken, wo die Wissensbasis und Grundregeln sind:

rectangle(a1, 3, 5). %Name,Width,Height 
    rectangle(a2, 1, 2). 
    rectangle(a3, 4, 3). 

    calcWH(T,C) :- 
     rectangle(T,W,_), C is W. % finds the width of the rect. 

Der rekursive Teil ist:

calcWTH([],0). % Base case 
calcWTH([H | T ] ,K) :- 
    length([H|T],L), 
    L =< 3, 
    calcWTH(T,M), 
    calcWH(H,O), 
    K is O+M. 

Was ich mit diesem Code machen möchte, ist, mit calcWTH möchte ich die Gesamtbreite der Liste der Rechtecke berechnen. Zum Beispiel

calcWTH([a1,a2,a3],A) 

gibt 8 zurück, wie erwartet. Die Sache, die mich irritiert, ist, dass dieser Code nur für den einen Weg funktioniert, nicht für den anderen. Zum Beispiel, wenn ich mache eine Abfrage wie

calcWTH(A,3) 

Es findet zunächst A = [A1], dann A = [a2, a2, a2] und danach erwarte ich das Programm wegen des Teils zu stoppen length([H|T],L), L =< 3 Aber es gerät auf unbestimmte Zeit in eine Schleife. Was fehlt mir hier?

Answer 1

Überlegen Sie, was dies zu tun ist:

length([H|T],L), L =< 3 

1. Machen Sie eine Liste
2. seine Länge überprüfen weniger als 3, wenn es - dann Erfolg, andere weise zurück Spur Länge/2 und eine weitere Liste versuchen zu machen und dann prüfen, ob die Listenlänge ist kleiner als 3.

Aber wir wissen, dass die Liste/2-Listen in der Reihenfolge der größeren Größe zu schaffen, so wissen wir, dass, wenn die Liste der Länge 3 schlägt fehl, dann wird die nächste Liste erstellt auf Rückverfolgung größer sein und alle anderen Listen .. aber Prolog weiß das nicht. Sie können sich vorstellen, eine Länge Prädikat schreiben, die nach Listen in einer anderen Reihenfolge, vielleicht nach dem Zufallsprinzip oder aus einer vordefinierten großen Größe zu immer kleineren Listen sucht. Dann würden wir wollen, dass das Backtracking wie es ist.

Jedenfalls, warum Sie unendliche Rekursion bekommen, wird es immer neue Listen von immer größer werdender Größe versuchen.

Sie könnten das Hinzufügen Einschränkungen finden ist eine gute Möglichkeit, Ihr Problem zu lösen:

Using a constrained variable with `length/2`