Deklaratív Programozás 3. gyakorlat
	    Prolog programozás: listák, feltételes szerkezetek
		     
			 2010.10.11 és 2010.10.13.

---------------------------------------------------------------------------
Írjon olyan Prolog eljárást, amely megfelel az adott fejkommentnek. A
feladat megoldásához felhasználhat korábbi sorszámú feladatokban, illetve
előző gyakorlatokon feladott feladatokban szereplő eljárásokat. Ne
használjon beépített és könyvtári eljárásokat, kivéve az alábbi beépített
eljárásokat:

    A <rel> B:
    Az A és B aritmetikai kifejezések értéke között fennáll a <rel> reláció.
    <rel> a következők valamelyike: < > =< >= =:= =\=

    X is A:
    X egyesíthető az A aritmetikai kifejezés értékével.

    X = Y:
    X és Y egyesíthető.

    length(L, I):
    Az I egész az L lista hosszával azonos. Ha L zárt végű lista, vagy I
    adott egész, akkor az eljárás determinisztikus, azaz legfeljebb egy
    megoldást ad.

    var(X):
    Az X argumentum (a var/1 meghívásának pillanatában) egy
    behelyettesítetlen változó.

Ha segédeljárás definiálása szükséges, azt külön jelezzük.

A fejkommentekben használt ún. módjelölések magyarázata:

*: az argumentum tömör bemenő, azaz nem lehet változó, és nem is
   tartalmazhat változót;

+: az argumentum bemenő, azaz nem lehet változó, de tartalmazhat változót
   (természetesen csak akkor, ha az argumentum egy struktúra);

-: az argumentum kimenő, azaz változó;

?: az argumentum lehet kimenő és bemenő is.
---------------------------------------------------------------------------

1.  Beszúrás rendezett listába

    % insert_ord(*RL0, +Elem, RL): Az RL monoton növő számlista úgy áll
    % elő, hogy az RL0 szigorúan növő számlistába beszúrjuk az Elem számot,
    % feltéve hogy Elem nem eleme az RL0 listának; egyébként RL = RL0.
    | ?- insert_ord([1,3,5,8], 6, L).
    L = [1,3,5,6,8] ? ;
    no
    | ?- insert_ord([1,3,5,8], 3, L).
    L = [1,3,5,8] ? ;
    no

    Használjon feltételes szerkezetet!

2.  Lista adott sorszámú eleme

    % nth1_1(+N, ?L, ?E): Az L lista N. eleme E (1-től számozva az
    % elemeket).

    Az eljárás nevében szereplő első 1-es arra utal, hogy 1-től számozzuk
    az elemeket, a második egyes pedig arra, hogy ez az első változata
    egy feladatsornak.
    | ?- nth1_1(3, [a,b,c], E).
    E = c ? ;
    no
    | ?- nth1_1(3, L, E).
    L = [_A,_B,E|_C] ? ;
    no

3.  Adott lista sorszámozott eleme

    % nth1_2(?N, +L, ?E): Az L zárt végű lista N. eleme E (1-től számozva az
    % elemeket).
    | ?- nth1_2(N, [a,b,c], E).
    E = a,
    N = 1 ? ;
    E = b,
    N = 2 ? ;
    E = c,
    N = 3 ? ;
    %
    no

4.  Lista adott hosszú prefixuma

    Egy L n-elemű lista prefixumának nevezünk egy listát, ha az az L
    első k elemét tartalmazza (az L-beli sorrend megtartásával),
    ahol 0 =< k =< n.

    % prefix_length(+Whole, ?Prefix, +Length): A Whole zárt végű lista
    % prefixuma a Prefix lista, amelynek hossza Length.
    | ?- prefix_length([a,b,c,d,e], Prefix, 3).
    Prefix = [a,b,c] ? ;
    no

    Vizsgálja meg, hogy megoldása működik-e nyílt végű listákra, és
    létrehoz-e végtelen választási pontot!

5.  Lista adott helyen kezdődő szuffixuma

    Egy L  lista szuffixumának nevezünk egy listát, ha az az L utolsó 
    valahány elemét tartalmazza, az L-beli sorrend megtartásával.

    % suffix_before(+Whole, ?Suffix, +Before): A Whole zárt végű lista
    % azon szuffixuma a Suffix lista, amelyet megelőző elemek száma
    % Before.
    | ?- suffix_before([a,b,c,d,e], Suffix, 3).
    Suffix = [d,e] ? ;
    no

    Vizsgálja meg, hogy megoldása működik-e nyílt végű listákra, és
    létrehoz-e végtelen választási pontot!

6.  Részlista képzése

    % sublist(+Whole, ?Part, +Before, +Length): A Whole zárt végű
    % lista azon (folytonos) részlistája Part, amely előtt Before
    % számú elem áll és amelynek hossza Length.
    | ?- sublist([a,b,c,d,e], Part, 1, 3).
    Part = [b,c,d] ? ;
    no

7.  Részlisták felsorolása

    % sublist(+Whole, ?Part, ?Before, ?Length, ?After): A Whole zárt
    % végű lista olyan (folytonos) részlistája Part, amely előtt
    % Before és amely után After számú elem áll, és amelynek hossza
    % Length.
    | ?- sublist([a,b], Part, Before, Length, After).
    Part = [], After = 2, Before = 0, Length = 0 ? ;
    Part = [a], After = 1, Before = 0, Length = 1 ? ;
    Part = [a,b], After = 0, Before = 0, Length = 2 ? ;
    Part = [], After = 1, Before = 1, Length = 0 ? ;
    Part = [b], After = 0, Before = 1, Length = 1 ? ;
    Part = [], After = 0, Before = 2, Length = 0 ? ;
    no

===========================================================================
Szorgalmi/otthoni feladatok
===========================================================================

8.  Lista sorszámozott eleme: több irányban működő eljárás
    Gondolja meg, hogy mennyire hatékony a 3. feladatra adott
    megoldása abban az esetben ha N egy adott szám.

    A var/1 beépített eljárás és a feltételes szerkezet használatával
    készítse el a (2, és 3. feladatbeli) nth1_1 és nth1_2 eljárások
    egy olyan nth1_3 kombinációját, amely minden input-output módban
    helyesen és hatékonyan működik (ha az első két argumentum
    behelyettesítetlen, akkor -- jogosan -- végtelen sok megoldást
    adjon vissza).

9.  Beszúrás listába adott helyre

    % insert_nth(+N, ?L0, ?E, ?L): Az L lista N. eleme E, ezt megelőző
    % elemei azonosak L0 1., 2., ... N-1. elemével, ezt követő elemei
    % azonosak L0 N., N+1., ... elemeivel.
    | ?- insert_nth(3, [a,b,c,d,e], i, L).
    L = [a,b,i,c,d,e] ? ;
    no
    | ?- insert_nth(3, [a,b,c,d,e], X, L).
    L = [a,b,X,c,d,e] ? ;
    no
    | ?- insert_nth(3, [1], 2, L).
    no
    | ?- insert_nth(3, L0, X, L).             % (*)
    L = [_A,_B,X|_C],
    L0 = [_A,_B|_C] ? ;
    no

    Először oldja meg a feladatot feltételes szerkezet használata
    nélkül!  Adjon olyan megoldást is amely feltételes szerkezetet
    használ (a megoldásban ez insert_nth_2 néven szerepel).

10. Beszúrás adott listába

    % insert_nth_3(?N, +L0, ?E, ?L):
    Az insert_nth_3 eljárás ugyanazt az eredményt adja mint az
    insert_nth az utóbbinál felsorolt példák esetén, kivéve a (*)-gal
    jelöltet, és müködik az alábbi példákra is:
    | ?- insert_nth_3(N, [1], 2, L).
    L = [2,1],
    N = 1 ? ;
    L = [1,2],
    N = 2 ? ;
    no
    | ?- insert_nth_3(N, [1], X, L).
    L = [X,1],
    N = 1 ? ;
    L = [1,X],
    N = 2 ? ;
    no

    Segédeljárás definiálása szükséges lehet.


    A 10. feladatot kihagyhatja ha helyette megoldja az alábbi
    11. feladatot, amely ennek egy általánosítása.

11. Beszúrás adott listába vagy adott lista-eredménnyel

    Az insert_nth_4 eljárás jelentése (és fejkommentje) ugyanaz mint
    az 9. és 10. feladatbeli eljárásé, de működnie kell akkor is, ha
    zárt végű az a lista, amelybe beszúrunk, és akkor is ha a beszúrás
    eredménye adott.

    A 9. és 10. feladatokban felsorolt összes példa esetén a megadott
    eredményt adja, kivéve a (*)-gal jelöltet, és müködik az alábbi
    példára is:
    | ?- insert_nth_4(N, L0, X, [a,b]).
    N = 1,
    X = a,
    L0 = [b] ? ;
    N = 2,
    X = b,
    L0 = [a] ? ;
    no

    Vizsgálja meg, hogy mennyire hatékony ez a megoldás abban az
    esetben ha N egy megadott szám.

    A var/1 beépített eljárás és feltételes szerkezet használatával
    készítsen egy olyan insert_nth/4 változatot, amely hatékonyan
    működik ha az 1., 2. és 4. argumentumok közül legalább az egyik
    adott (szám ill. zárt végű lista). A megoldásban ez a változat
    insert_nth_5 néven szerepel.

    Segédeljárás definiálása szükséges lehet.

===========================================================================
Tippek:

3.  feladat 
    A member/2 eljárás két argumentumát cserélje meg, és egészítse ki
    egy első N argumentummal, amely a beszúrás helyét számlálja. Mivel
    N lehet behelyettesítetlen változó is, ezért tekintse kimenő
    argumentumnak. (Nem baj, ha az eljárás nem jobbrekurzív.)

10. feladat    
    A select/3 eljárás argumentumainak átrendezesével készítsen egy
    insert/3 ejárást:

    % insert(L0, E, L): L az L0 listából az E elem beszúrásával jön létre.

    Ezt az eljárást egészítse ki egy N első argumentummal, és kövesse a
    3. feladathoz adott tippet.