Deklaratív programozás nagyzárthelyi, 2001. május 7. ==================================================== Javítási kulcsok ================ A csoport --------- 1. Döntse el, mi lesz az alábbi Prolog kérdések eredménye (hiba, meghiúsulás, siker)! Siker esetén adja meg a keletkező valtozó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1.a | ?- [a,b,c] = [X|Y]. siker: X = a, Y = [b,c] 1.b | ?- X = 1+2, X = 3. meghiúsulás 1.c | ?- X = 4, \+ 2+2 = X. siker: X = 4 1.d | ?- 3+4 is X. hiba 1.e | ?- X*Y = 2*2*3. siker X = 2*2, Y = 3 Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. 2. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus édesítőszerek nélküli formáját), vagy rajzolja fel a hozzájuk tartozó fastruktúrákat! 2.a 3+6-z/x ==> -(+(3,6),/(z,x)) 2.b [f(3,4),X|L] ==> .(f(3,4),.(X,L)) 2.c [g(1,2,(a-b)*3),[]] ==> .(g(1,2,*(-(a,b),3)),.([],[])) Pontozás: 2.a 1 pont 2.b 2 pont 2.c 3 pont 3. Milyen változó-behelyettesítéseket eredményeznek az alábbi egyesítések? 3.a f(a*b*c,[1,2]) = f(A*B,[C|D]). ==> A = a*b, B = c, C = 1, D = [2] 3.b [.(1,E),F,F] = [[X],Y*Z,X*2]. ==> E = [], F = 1*2, X = 1, Y = 1, Z = 2 3.c f(G/H,[3/G-b|J])=f(P,[P-Q,Q]). ==> G = 3, H = 3, J = [b], P = 3/3, Q = b Pontozás: 3.a 2 pont 3.b 3 pont 3.c 4 pont 4. Tekintse a p/1 eljárást és az azt hívó alábbi célsorozatot! p(B) :- member(A, B), ( A =< 0'6 -> put_code(A) ; put_code(0'.) ), fail. p(_). | ?- write(ÉÉHHNN), nl, p("ÉÉHHNN"), nl. Mit ír ki az fenti célsorozat, ha abban az ÉÉHHNN karaktersorozat helyén az ön születési dátuma (pl. 811231) szerepel? Fogalmazza meg általánosan, hogy a p/1 által kiírt szöveg hogyan függ a paraméter-füzérben szereplő dátumtól! (Futtatáskor a lists könyvtár be van töltve.) Válasz: | ?- write(811231), nl, p("811231"), nl. 811231 .11231 Általánosan: A hat számjegyet sorra veszi, a 6-nál nagyobb számjegyek helyére .-ot ír, a többiek helyére magát a számjegyet. Pontozás: a kiirt karaktersorozat helyes => 2 pont az általános megfogalmazás jó => 3 pont 5. Írjon olyan Prolog eljárást, amely megfelel az alábbi fejkommentnek! % kozep(+L, -A): A egy olyan eleme az L listának, amely a bal- és % jobb-szomszédjának számtani közepe. Megoldások: % 1. megoldás: kozep(L, A) :- append(_, [B,A,J|_], L), A =:= (B+J)/2. % 2. megoldás: kozep([B,A,J|_], A) :- A =:= (B+J)/2. kozep([_|L], A) :- kozep(L, A). Pontérték: 5 pont 6. Mi az f típusa az alábbi (egymástól független) deklarációkban? 6.a fun f x y z = x z y f : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c 6.b fun f (x, y) = y (x+1, 2.0) f : int * (int * real -> 'a) -> 'a 6.c fun f x y = y (x y) f : (('a -> 'b) -> 'a) -> ('a -> 'b) -> 'b Pontozás: 6.a 3 pont 6.b 2 pont 6.c 3 pont 7. Mi az x értéke és típusa az alábbi (egymástól független) deklarációkban? 7.a val x = implode(#"z" :: #"y" :: [#"x"]) x = "zyx" : string 7.b val x = List.filter (fn x => x <= 2) [1,2,3] x = [1, 2] : int list 7.c val x = map (fn i => i div 2) [3,4,6,9] x = [1, 2, 3, 4] : int list Pontozás: 7.a-7.c Helyes válasz 1 pont, helytelen 0 pont 8. Mit kap eredményül, ha az alábbi f függvényt a hat számjegyből álló, ééhhnn alakban füzérként megadott születési dátumára alkalmazza (pl. f "811231")? Válaszát indokolja! fun f x = let fun g (x::xs) ys = x :: g ys xs | g _ _ = [] val y = explode x in implode (g y (rev y)) end Válasz: Pl. f "811231" = "811312213118" Általánosan: Az explode a bemenő füzért (string) karakterek listájává alakítja, ez lesz y értéke. A g függvény mind az egyenes sorrendű, mind a megfordított karakterlistát (char list) megkapja argumentumként, és alternálva egymáshoz fűzi e két lista karaktereit (char list). A g eredménye tehát olyan karakterlista, amelyben az eredeti füzér karakterei elölről, ill. hátulról kezdve váltogatják egymást. Az f eredménye az ebből a karakterlistából az implode alkalmazásával előállított füzér. Pontérték: 6 pont 9. Írja meg az alábbi f függvény egy ekvivalens változatát a foldl, map, op+ és ord függvények alkalmazásával! fun f [] = 0 | f (x::xs) = ord x + f xs Válasz: Ekvivalens változata foldl, map, op+ és ord alkalmazásával: fun f xs = foldl op+ 0 (map ord xs) Pontérték: 6 pont 10.Írjon olyan SML-függvényt front néven, amely az alább deklarált adattípus adatkonstruktoraival létrehozott adatszerkezet ,,elejét'' listává alakítja az adatok sorrendjének megőrzésével! Az adatszerkezet ,,eleje'': a << adatkonstruktorral az adatszerkezetbe illesztett értékek sorozata. Megoldás: infixr 5 <<; infix 5 >>; datatype 'a que = Nil | << of 'a * 'a que | >> of 'a que * 'a (* front : 'a que -> 'a list front xq = az xq-ba a << adatkonstruktorfüggvénnyel berakott értékek listája az eredetivel megegyező sorrendben *) fun front (x << xq) = x :: front xq | front (xq >> x) = front xq | front Nil = [] Pontérték: 7 pont B csoport --------- 1. Döntse el, mi lesz az alábbi Prolog kérdések eredménye (hiba, meghiúsulás, siker)! Siker esetén adja meg a keletkező valtozó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1.a | ?- X is 3+4, X = 3+4. meghiúsulás 1.b | ?- [u,v,w] = [X,Y|Z]. siker: X = u, Y = v, Z = [w] 1.c | ?- X is X+1. hiba 1.d | ?- 4+2+3 = X+Y. siker: X = 4+2, Y = 3 1.e | ?- X = a, \+ a = X. meghiúsulás Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. 2. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus édesítőszerek nélküli formáját), vagy rajzolja fel a hozzájuk tartozó fastruktúrákat! 2.a 1*2*3/x ==> /(*(*(1,2),3),x) 2.b h(3,4,[1,X|L]) ==> h(3,4,.(1,.(X,L))) 2.c [u/(1-a),[],h(1,2)] ==> .(/(u,-(1,a)),.([],.(h(1,2),[]))) Pontozás: 2.a 1 pont 2.b 2 pont 2.c 3 pont 3. Milyen változó-behelyettesítéseket eredményeznek az alábbi egyesítések? 3.a [A+B, C|D] = [1+2+3, 4+5]. ==> A = 1+2, B = 3, C = 4+5, D = [] 3.b [E+b*c, F+G|E] = .(X, [X,1]). ==> E = [1], F = [1], G = b*c, X = [1]+b*c 3.c h([H,G],H*G)=h([Q/1|R],P/Q*3).==> G = 3, H = 1/1, P = 1, Q = 1, R = [3] Pontozás: 3.a 2 pont 3.b 3 pont 3.c 4 pont 4. Tekintse a p/1 eljárást és az azt hívó alábbi célsorozatot! p([]). p([A|B]) :- member(A, "56789"), !, p(B), put_code(A). p([_|B]) :- p(B), put_code(0'x). | ?- write(ÉÉHHNN), nl, p("ÉÉHHNN"), nl. Mit ír ki az fenti célsorozat, ha abban az ÉÉHHNN karaktersorozat helyén az ön születési dátuma (pl. 811231) szerepel? Fogalmazza meg általánosan, hogy a p/1 által kiírt szöveg hogyan függ a paraméter-füzérben szereplő dátumtól! (Futtatáskor a lists könyvtár be van töltve.) | ?- write(811231), nl, p("811231"), nl. 811231 xxxxx8 Általánosan: A hat számjegyet fordított sorrendben sorra veszi, az 5-nél nagyobb egyenlő számjegyeket kiírja, a többiek helyére az x karaktert írja. Pontozás: a kiirt karaktersorozat helyes => 2 pont az általános megfogalmazás jó => 3 pont 5. Írjon olyan Prolog eljárást, amely megfelel az alábbi fejkommentnek! % nullpar(+L, -NL): NL egy olyan kételemű (folytonos) részlistája L-nek, % amelynek összege 0. Megoldások: % 1. megoldás: nullpar(L, [A,B]) :- append(_, [A,B|_], L), A =:= -B. % 2. megoldás: nullpar([A,B|_], NL) :- A =:= -B, NL = [A,B]. nullpar([_|L], NL) :- nullpar(L, NL). Pontozás: helyes megoldás => 5 pont 6. Mi az f típusa az alábbi (egymástól független) deklarációkban? 6.a fun f x y z = z y x f : 'a -> 'b -> ('b -> 'a -> 'c) -> 'c 6.b fun f (x, y) = x(1.0, y div 2) f : (real * int -> 'a) * int -> 'a 6.c fun f x y = (y, (x y)) f : ('a -> 'b) -> 'a -> 'a * 'b Pontozás: 6.a 3 pont 6.b 2 pont 6.c 3 pont 7. Mi az x értéke és típusa az alábbi (egymástól független) deklarációkban? 7.a val x = implode(#"z" :: #"y" :: [#"x"]) x="zyx" : string 7.b val x = List.filter (fn x => x <= 2) [1,2,3] x=[1, 2] : int list 7.c val x = map (fn i => i div 2) [3,4,6,9] x=[1, 2, 3, 4] : int list Pontozás: 7.a-7.c Helyes válasz 1 pont, helytelen 0 pont 8. Mit kap eredményül, ha az alábbi f függvényt a hat számjegyből álló, ééhhnn alakban füzérként megadott születési dátumára alkalmazza (pl. f "801128")? Válaszát indokolja! fun f x = let fun g (x::xs) ys = str x ^ g ys xs | g _ _ = "" val y = explode x in g (rev y) y end Válasz: Pl. f "801128" = "882011110288" Általánosan: Az explode a bemenő füzért (string) karakterek listájává alakítja, ez lesz y értéke. A g függvény mind a megfordított, mind az egyenes sorrendű karakterlistát (char list) megkapja argumentumként, és alternálva egymáshoz fűzi e két lista egykarakteres füzérré alakított karaktereit. A g és ezzel az f eredménye tehát olyan füzér (string) lesz, amelyben az eredeti füzér karakterei hátulról, ill. elölről kezdve váltogatják egymást. Pontérték: 6 pont 9. Írja meg az alábbi f függvény egy ekvivalens változatát a foldl, map, op^ és str függvények alkalmazásával! fun f [] = "" | f (x :: xs) = str x \^ f xs Válasz: Ekvivalens változata foldr, map, op^ és str alkalmazásával: fun f xs = foldr op^ "" (map str xs) Pontérték: 6 pont 10.Írjon olyan SML-függvényt revRear néven, amely az alább deklarált adattípus adatkonstruktoraival létrehozott adatszerkezet ,,végét'' listává alakítja az adatok sorrendjének megfordításával! Az adatszerkezet ,,vége'': a >> adatkonstruktorral az adatszerkezetbe illesztett értékek sorozata. Megoldás: infixr 5 <<; infix 5 >>; datatype 'a que = Nil | << of 'a * 'a que | >> of 'a que * 'a (* revRear : 'a que -> 'a list revRear xq = az xq-ba a >> adatkonstruktorfüggvénnyel berakott értékek listája az eredetihez képest fordított sorrendben *) fun revRear (x << xq) = revRear xq | revRear (xq >> x) = x :: revRear xq | revRear Nil = []; Pontérték: 7 pont