Listák megfordítása (naiv és hatékony megoldás)

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

• fejezetek: 3.3.3.

Naiv megfordítás

% nrev(L, R): Az R lista az L megfordítása.
nrev([], []).
nrev([X|L], R) :-
	 nrev(L, RL),
	 append(RL, [X], R).

A megoldás O(n²) költségű, mivel az n darab append hívást igényel, ami rendre n redukciós lépésből áll.

Lineáris időben R lista az L megfordítottja

% 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).

Gyűjtőargumentum (ún. akkumulátor) segítségével írunk segédeljárást revapp/3 néven. Ez az első paraméterében megkapott lista elemeit fűzi a második paraméterhez, végül a 3. argumentumot szolgáltatja az eredményt. Az első klóz állítja le a rekurziót, amikor is az első argumentum kiürült.