Akkumulátorok, listák akkumulálása elölről ill. hátulról

• fejezetek: 4.3.2, 4.3.3

4.3.2. Akkumulátorok

Az imperatív nyelvekben gyakran előfordul, hogy egy ciklusban meg kell változtani egy változó értékét. Prologban a behelyettesített változók nem kaphatnak új értéket, ezért akkumulátor (gyűjtőargumentum) használatával lehet azonos működést elérni. Példa:

% fact(+N, -NF): NF = N! (n faktoriális)
fact(0, 1).
fact(N, NF) :-
	 N>0,
	 N1 is N-1,
	 fact(N1, NF1),
	 NF is N*NF1.

Az algoritmus ebben a formájában nem jobbrekurzív, de gyűjtőargumentum használatával azzá tehető.

% fact(+N, -NF): NF = N! (n faktoriális)
fact(N, NF) :-
	 fact(N, 1, NF).

% fact(+N, +NF0, -NF): NF = N!*NF0
fact(0, K, K).
fact(N, NF0, NF) :-
	 N>0,
	 N1 is N-1,
	 NF1 is N*NF0,
	 fact(N1, NF1, NF).

Az akkumulátorpár (fent: NF0, NF) első tagja a ténylegesen változó mennyiség belépéskori állapotát jelenti, míg a második az adott eljárás szempontjából végső állapotot tartalmazza.

Egy gyűjtőargumentum természetesen nem csak számokat tárolhat, hanem tetszőleges Prolog kifejezéseket. A lényeg az, hogy a pár első tagja egy ténylegesen változó mennyiség belépéskori állapotát jelenti, míg a második az adott eljárás szempontjából végső állapotot tartalmazza. Az akkumulátor-változók jelölésére azt a konvenciót alkalmazzuk, hogy a fejben az akkumulátor-párt mindig Vált0, Vált formában írjuk, ahol Vált egy tetszőleges változónév. A klóz törzsében az ideiglenes értékeket rendre Vált1, Vált2, ... jelöli.

4.3.3. Listák gyűjtése

Elölről

Az akkumulátor nem csak egyszerű kifejezéseket, hanem listát is tartalmazhat. Egy lista megfordítása például úgy hatékony, ha a lista már megfordított elejét gyűjtőargumentumban tároljuk, és ehhez fűzzük hozzá elölről a további elemeket.

% reverse(R, L): Az R lista az L megfordítása.
reverse(R, L) :-
	 revapp(L, [], R).

% revapp(L1, L2, R): L1 megfordítását L2 elé fűzve kapjuk R-t.
revapp([], R, R).
revapp([X|L1], L2, R) :-
	 revapp(L1, [X|L2], R).

Hátulról

Az akkumulátor lista elemeinek sorrendje megegyezik a berakási sorrenddel, a lista nem fordul meg. Pl. append/3:

append([], L, L).
append([X|L1], L2, [X|L3]) :-
	 append(L1, L2, L3).