Größe Vorgehen in Prolog Sprache

Question

Ich bin neu in Prolog und bin nicht so groß, wenn es um rekursive Algorithmen kommt wie es ist, so bin ich mit den folgenden zwei Klauseln verwirrt:

size([], 0). 
size([H|T], N) :- size(T, N1), N is N1+1. 

Ich habe Probleme, diese Verfolgung Problem für:

?- size([a,b,c,d], N). 

das mit der zweiten Klausel Form vereinigen wird:

size([a,b,c,d], N) :- size([b,c,d], N1), N is N1+1. 

Aber ich bin verwechselt mit der N ist N1+1, da diese Variablen nie vereinheitlicht sind. Welche Werte haben diese Variablen?

Jede Hilfe zu dieser Frage oder eine einfache Spur dieses Algorithmus würde sehr geschätzt werden.

Answer 1

das N ist N1 + 1, da diese Variablen nie einheitlich sind.

Ich denke, Sie meinen, dass sie nie instanziiert werden, d. H. Sie erhalten nie einen Wert. Die Vereinheitlichung von zwei Variablen kann sie instanziieren, aber es ist nicht notwendig. Zum Beispiel könnten Sie dies in einem Prolog REPL laufen:

?- N = N1. 
N = N1. 

während N und N1 keinen Wert (noch) nicht haben, sie vereinigt sind; Wenn N1 später instanziiert wird, wird N ebenfalls mit dem gleichen Wert instanziiert. Ein anderes, weniger trivial, Beispiel:

?- [H|T] = L, L = [1|M], writeln(H). 
1 
H = 1, 
T = M, 
L = [1|M]. 

Es ist jedoch wahr, dass N nie mit N1+1 vereinigt! is wertet N1+1 und so aus, dass der Wert mit N vereinheitlicht wird. Dies geschieht, nachdem der innere size([b,c,d],N1) ausgewertet wurde, so dass die Variable N1 instanziiert wurde.

Im Wesentlichen wird die Ausführung so aussehen:

size([a,b,c,d],N). 
      size([b,c,d],N1) 
       size([c,d],N1) 
        size([d],N1) 
         size([],0) 
         N is 0+1. 
        N is 1+1. 
       N is 2+1. 
      N is 3+1. 

die ein bisschen ist ineffizient, da wir alle Funktionsaufrufe im Speicher halten müssen; in Tail-Rekursion und Akkumulatoren schauen, um das zu beheben.

Beachten Sie auch, dass N1 nur instanziiert werden muss, weil is den Ausdruck auswerten wird. Man könnte so etwas schreiben:

size([],0). 
size([_|T], 1+ N1):-size(T,N1). 

und wenn Sie es nennen:

?- size([1,2],N). 
N = 0+1+1. 

Spaß, ist es nicht? Vielleicht möchten Sie das letzte N, z. nennen Sie es als size([1,2],N), Result is N. Ein Problem ist jedoch, dass wir eine Kette von 0+1+1+1+1+...... im Speicher halten, die sehr schnell sehr groß werden kann. Es ist also am besten, diesen Trick für Dinge zu verwenden, die nicht wachsen werden, z. Ausdrucksvorlagen