Deklaratív programozás

A feladat

Egy C tömör listát ciklusnak nevezünk, ha nincs két azonos (egyesíthető) eleme. Például [z,e,n] és az üres lista ciklusok, de [z,e,n,e] nem az, mert az e elem ismétlődik, és [z,e,n,E] sem az, ha az E behelyettesítetlen változó. (Tömörnek nevezzük az adatstruktúrát, ha nincs benne behelyettesítetlen változó.)

Egy X tömör érték C ciklus szerinti forgatottjának azt az értéket nevezzük, amely a C listában közvetlenül az X után áll, vagy ha az X a C utolsó eleme, akkor a C első elemét, vagy ha az X nem szerepel C-ben, akkor magát az X-et. Például az e forgatottja [t,r,u,e] szerint t, [z,e,n] szerint viszont n.

Egy L tömör lista C ciklus szerinti körbeforgatottjának azt a listát nevezzük, amely az L elemeinek a C szerinti forgatottjaiból áll (az eredeti sorrendben). Például a [t,r,u,e] lista [z,e,n] szerinti körbeforgatottja [t,r,u,n], mert csak az e szerepel mindkét listában, és e forgatottja n; a [z,e,n] lista [t,r,u,e] szerinti körbeforgatottja pedig [z,t,n].

Írjon olyan Prolog-programot, amely egy L lista C ciklus szerinti körbeforgatottját állítja elő. A program tartalmazza a korbe/3 eljárást a következő jelentéssel:

% korbe(+L,+C,?M) pontosan akkor igaz, ha  az L lista
% C ciklus szerinti körbeforgatottja az M lista. Csak akkor kell
% helyesen működnie, ha a hívás pillanatában L és C tömör.

Egy példamegoldás, amely csak kételemű C-kre működik:

korbe([], _, []).
korbe([A|L], [A,B], [B|M]) :- korbe(L, [A,B], M). 
korbe([B|L], [A,B], [A|M]) :- korbe(L, [A,B], M). 
korbe([X|L], [A,B], [X|M]) :- X \= A, X \= B, korbe(L, [A,B], M). 

A jobbrekurzív eljárások kevesebb memóriát igényelnek, mint az egyéb rekurzív eljárások, ezért a feladat megoldása során jobbrekurzív eljárások írása ajánlott, ám ez nem kötelező, a pontozásba nem számít bele.

A feladat megoldása során a gyorsítás érdekében szabad vágót és feltételes szerkezetet használni, ám ez nem kötelező, a pontozásba nem számít bele.

Példák

| ?- set_prolog_flag(toplevel_print_options,
     [quoted(true),numbervars(true),portrayed(true),max_depth(20)]).
yes /* a listák mutatása 20 hosszúságig */

| ?- korbe([a,b,r,a,c,a,d,a,b,r,a], [a,b], M)
M = [b,a,r,b,c,b,d,b,a,r,b] ? ;   /* a és b felcsélődik */
no

| ?- korbe([a,b,r,a,c,a,d,a,b,r,a], [a,b,c,d], M).
M = [b,c,r,b,d,b,a,b,c,r,b] ? ;  /* az r nem változott, a többi forogtak */
no

| ?- korbe([a,b,r,a,c,a,d,a,b,r,a], [r], M).
M = [a,b,r,a,c,a,d,a,b,r,a] ? ;  /* ha C egyelemű, akkor L=M */
no

| ?- korbe([a,b,r,a,c,a,d,a,b,r,a], [], M).
M = [a,b,r,a,c,a,d,a,b,r,a] ? ;  /* ha C üres, akkor L=M */
no

| ?- korbe([p,r,o,1,2,3],[p,1,r,2], M).
M = [1,2,o,r,p,3] ? ;  /* számok és betűk is lehetnek vegyesen */
no

Otthoni tesztkörnyezet

:- consult('khf-pl2').
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[a,b,c,d],M), S),
   S==[[b,c,r,b,d,b,a,b,c,r,b]].
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[a,b,c],  M), S),
   S==[[b,c,r,b,a,b,d,b,c,r,b]].
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[b,a,c],  M), S),
   S==[[c,a,r,c,b,c,d,c,a,r,c]].
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[b,a],    M), S),
   S==[[b,a,r,b,c,b,d,b,a,r,b]].
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[a,b],    M), S),
   S==[[b,a,r,b,c,b,d,b,a,r,b]].
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[r],      M), S),
   S==[[a,b,r,a,c,a,d,a,b,r,a]].
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[u],      M), S),
   S==[[a,b,r,a,c,a,d,a,b,r,a]].
:- findall(M, korbe([a,b,r,a,c,a,d,a,b,r,a],[],       M), S),
   S==[[a,b,r,a,c,a,d,a,b,r,a]].
:- findall(M, korbe([],[p,r,o,l,g], M), S), S==[[]].
:- findall(M, korbe([],[], M), S), S==[[]].
:- findall(M, korbe([p,r,o,1,2,3],[p,1,r,2], M), S), S==[[1,2,o,r,p,3]].
:- findall(M, korbe([f,a,l,s,e],[t,r,u,e], M), S), S==[[f,a,l,s,t]].    
:- findall(M, korbe([t,r,u,e],[z,e,n], M), S), S==[[t,r,u,n]].      
:- findall(M, korbe([z,e,n],[t,r,u,e], M), S), S==[[z,t,n]].

Ha ezt a programot a környezet hiba nélkül betölti (pl. a sicstus -l teszt2.pl vagy az swipl -s teszt2.pl parancs hatására), akkor a khf-pl2.pl-ben nincs szintaktikai hiba, és a teszt2.pl-ben leírt tesztesetek is hibátlanul futottak le.

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéd segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a második Prolog kis házi feladat; a megoldást khf-pl2.pl néven kell beküldeni. A névben meg kell különböztetni a kis- és nagybetűket. A beadási határidő 2006. március 31., péntek 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár.