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

A VIK Wikiből
A lap korábbi változatát látod, amilyen Unknown user (vitalap) 2012. október 21., 22:08-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoalap|PrologElm10}} * fejezetek: 3.3.3. ==Naiv megfordítás== <pre> % nrev(L, R): Az R lista az L megfordítása. nrev([], []). nrev([X|L], R) :-…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)

Ez az oldal a korábbi SCH wikiről lett áthozva.

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(n2) 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.