Deklaratív programozás pótzárthelyi, 2001. május 23. ==================================================== Javítási kulcsok ================ Az SML-feladatokban előforduló könyvtári függvények típusa (az aritmetikai függvények kivételével): Char.isDigit : char -> bool Char.isUpper : char -> bool Char.toLower : char -> char List.filter : ('a -> bool) -> 'a list -> 'a list chr : int -> char explode : string -> char list foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b implode : char list -> string map : ('a -> 'b) -> 'a list -> 'b list op:: : 'a * 'a list -> 'a list op^ : string * string -> string ord : char -> int rev : 'a list -> 'a list --------- 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ő változó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1.a | ?- 1+4 = X, \+ X = 5. siker: X = 1+4 1.b | ?- X is Y*3, Y = 2+1. hiba 1.c | ?- [X|Y] = [1,2]. siker: X = 1, Y = [2] 1.d | ?- X is 2+2, 2+2 = X. meghiúsulás 1.e | ?- X/Y = 24/12/3. siker: X = 24/12, 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 2-3+a*b +(-(2,3),*(a,b)) 2.b [3/4,[],X] .(/(3,4),.([],.(X,[]))) 2.c [1,2|[a-b/3|L]] .(1,.(2,.(-(a,/(b,3)),L))) 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 g(1+2+3, [a,b]) = g(X+Y, [U|V]). U = a, V = [b], X = 1+2, Y = 3 3.b [S, T|[T]] = .([1], [A*2, B*A]). A = 2, B = 2, S = [1], T = 2*2 3.c f(G*H, [2*3+b|J]) = f(C, [C+D, D]). C = 2*3, D = b, G = 2, H = 3, J = [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! | ?- write(ÉÉHHNN), nl, p([É,É,H,H,N,N]), nl. Mit ír ki az fenti célsorozat, ha abban az ÉÉHHNN karakterek helyén az ön születési dátumának karakterei (pl. 811231 ill. [8,1,1,2,3,1]) szerepel? Fogalmazza meg általánosan, hogy a p/1 által kiírt szöveg hogyan függ a paramétertől! (Futtatáskor a lists könyvtár be van töltve.) p(B) :- write(!), member(A, B), A =< 3, write(A), fail. p(_). Válasz: | ?- write(811231), nl, p([8,1,1,2,3,1]), nl. 811231 !11231 yes Általánosan: Kiír egy !-jelet, majd a 3-nál kisebb-egyenlő számjegyeket írja ki. 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! % parospoz(+L, -A): A egy pozitív szám, amely páros indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. | ?- parospoz([1,2,4,-2,6,8], P). P = 2 ? ; P = 8 ? ; no Megoldás: % parospoz(+L, -A): A egy pozitív szám, amely páros indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. parospoz([_,X|_], X) :- X > 0. parospoz([_,_|L], X) :- parospoz(L, X). 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 = z(x y) f : ('a -> 'b) -> 'a -> ('b -> 'c) -> 'c 6.b fun f (y, x) = y(ord x, 2.0) f : (int * real -> 'a) * char -> 'a 6.c fun f y x = y(x y) f : ('a -> 'b) -> (('a -> 'b) -> '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 = explode "maj" @ [#"o",#"m"] x = [#"m", #"a", #"j", #"o", #"m"] : char list 7.b val x = List.foldr op+ 10.0 [1.0, ~2.0, 3.0] x = 12.0 : real 7.c val x = map (fn i => if i < 3 then ~i else i) [2,4,3,1] x = [~2, 4, 3, ~1] : 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 SAJÁT születési dátumára alkalmazza (pl. f "720431")? Válaszát indokolja! fun f x = let fun g (x::xs) (y::ys) = x :: y :: g ys xs | g _ _ = [] val zs = explode x in implode(g zs (rev zs)) end Pl. f "720431" = "713204043271" f "123456" = "165234345216" Általánosan: Az explode a bemenő füzért (string) karakterek listájává alakítja (zs : char list). A g függvény mind az egyenes sorrendű, mind a megfordított karakterlistát megkapja argumentumként, és mindkét lista első karakterét (az első argumentummal kezdve) az elé a lista elé fűzi, amelyet úgy kap, hogy a g-t alternálva alkalmazza a két lista maradékára, amíg el nem fogynak. A g eredménye tehát olyan karakterlista, amelyben az eredeti füzér karakterei hol elölről, hol 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 megadott könyvtári függvényekkel! local fun f0 [] zs = rev zs | f0 (y::ys) zs = f0 ys (if #"0" <= y andalso y <= #"9" then ord y::zs else zs) in fun f xs = f0 xs [] end Egy ekvivalens változata List.filter, map, Char.isDigit, ord alkalmazásával: fun f xs = map ord (List.filter Char.isDigit xs) Pl. f(explode "a5b7 8c 2x") = [53, 55, 56, 50] : int list Pontérték: 6 pont 10. Adott egy előjeles egész számokat tartalmazó lista, továbbá az alábbi adattípus-deklaráció: infixr 5 <<; infix 5 >>; datatype 'a que = Nil | << of 'a * 'a que | >> of 'a que * 'a Írjon olyan függvényt negPos néven, amely egy 'a que típusú sort állít elő úgy, hogy a lista negatív elemei a sor elejére, nemnegatív elemei pedig a sor végére kerüljenek (tetszőleges sorrendben). A sor eleje, ill. vége: a <<, ill. >> adatkonstruktorral az adatszerkezetbe illesztett értékek sorozata. (* negPos : int list -> 'a que negPos xs = olyan sor, amelynek az elején az xs negatív, a végén pedig az xs pozitív elemei vannak (tetszőleges sorrendben) *) Példák: negPos [] = Nil negPos [~2, ~3, ~1] = ~2 << ~3 << ~1 << Nil negPos [2, 0, 1] = Nil >> 1 >> 0 >> 2 negPos [~2, 2, ~1, 0, ~3, 1] = ~2 << ~1 << ~3 << (Nil >> 1 >> 0 >> 2) Megoldás: fun negPos [] = Nil | negPos (x::xs) = if x < 0 then x << negPos xs else negPos xs >> x; 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ő változó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1.a | ?- [X|[Y]] = [a,b]. siker: X = a, Y = b 1.b | ?- X is 2*3, \+ X = 6. meghiúsulás 1.c | ?- Y is X+1, X = 1. hiba 1.d | ?- A-B = 10-5-2. siker: A = 10-5, B = 2 1.e | ?- X = 2*3, Y = X+1. siker: X = 2*3, Y = 2*3+1 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 u-v+1-2 -(+(-(u,v),1),2) 2.b [1,a+b*c|X] .(1,.(+(a,*(b,c)),X)) 2.c [a,b-c+d/e,[]] .(a,.(+(-(b,c),/(d,e)),.([],[]))) 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 [X*Y, V|W] = [a*b*c, 4+5]. V = 4+5, W = [], X = a*b, Y = c 3.b [E*2*3, F*G, E] = .(A, [A, 1]). A = 1*2*3, E = 1, F = 1*2, G = 3 3.c g(H-G, [H, G]) = g(U*T-a, [T*2|S]). G = a, H = 2*2, S = [a], T = 2, U = 2 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! | ?- write(ÉÉHHNN), nl, p([É,É,H,H,N,N]), nl. Mit ír ki az fenti célsorozat, ha abban az ÉÉHHNN karakterek helyén az ön születési dátumának karakterei (pl. 811231 ill. [8,1,1,2,3,1]) szerepel? Fogalmazza meg általánosan, hogy a p/1 által kiírt szöveg hogyan függ a paramétertől! (Futtatáskor a lists könyvtár be van töltve.) p(B) :- member(A, B), write(+), A >= 3, write(A), fail. p(_). Válasz: | ?- write(811231), nl, p([8,1,1,2,3,1]), nl. 811231 +8++++3+ yes Általánosan: A hat számjegy mindegyikére: kiír egy + jelet, majd, ha a számjegy nagyobb-egyenlő mint 3, akkor kiírja a számjegyet; egyébként nem ír ki semmit. 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! % parosneg(+L, -A): A egy negatív szám, amely páros indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. | ?- parosneg([1,-2,-4,0,-8,-10], P). P = -2 ? ; P = -10 ? ; no Megoldás: % parosneg(+L, -A): A egy negatív szám, amely páros indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. parosneg([_,X|_], X) :- X < 0. parosneg([_,_|L], X) :- parosneg(L, X). 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 = y(z x) f : 'a -> ('b -> 'c) -> ('a -> 'b) -> 'c 6.b fun f (y, x) = x(1, chr y) f : int * (int * char -> 'a) -> 'a 6.c fun f x y = (y, (x, y)) f : 'a -> 'b -> 'b * ('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 = "zeb" ^ implode [#"r",#"a"] x = "zebra" : string 7.b val x = List.foldl op:: [#"K", #"U", #"K"] [#"A", #"C"] x = [#"C", #"A", #"K", #"U", #"K"] : char list 7.c val x = List.filter (fn i => i >= 3) [2,4,3,1] x = [4, 3] : 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 SAJÁT születési dátumára alkalmazza (pl. f "720431")? Válaszát indokolja! fun f x = let fun g (x::xs) (y::ys) = y :: x :: g ys xs | g _ _ = [] val zs = explode x in implode(g zs (rev zs)) end Pl. f "720431" = "172340402317" f "123456" = "612543432561" Általánosan: Az explode a bemenő füzért (string) karakterek listájává alakítja (zs : char list). A g függvény mind az egyenes sorrendű, mind a megfordított karakterlistát megkapja argumentumként, és mindkét lista első karakterét (a második argumentummal kezdve) az elé a lista elé fűzi, amelyet úgy kap, hogy a g-t alternálva alkalmazza a két lista maradékára, amíg el nem fogynak. A g eredménye tehát olyan karakterlista, amelyben az eredeti füzér karakterei hol hátulról, hol elölrő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 megadott könyvtári függvényekkel! fun f xs = let fun f0 [] zs = rev zs | f0 (y::ys) zs = f0 ys (if #"A" <= y andalso y <= #"Z" then Char.toLower y::zs else zs) in f0 xs [] end Egy ekvivalens változata List.filter, map, Char.toLower, Char.isUpper alkalmazásával: fun f xs = map Char.toLower (List.filter Char.isUpper xs) Pl. f(explode "aZbY cW dX") = [#"z", #"y", #"w", #"x"] : char list Pontérték: 6 pont 10. Adott egy előjeles egész számokat tartalmazó lista, továbbá az alábbi adattípus-deklaráció: infixr 5 <<; infix 5 >>; datatype 'a que = Nil | << of 'a * 'a que | >> of 'a que * 'a Írjon olyan függvényt oddEven néven, amely egy 'a que típusú sort állít elő úgy, hogy a lista páratlan elemei a sor elejére, páros elemei pedig a sor végére kerüljenek (tetszőleges sorrendben). A sor eleje, ill. vége: a <<, ill. >> adatkonstruktorral az adatszerkezetbe illesztett értékek sorozata. Egy szám páros/páratlan voltának meghatározására használhatja a fun even n = n mod 2 = 0 függvényt. (* oddEven : int list -> 'a que oddEven xs = olyan sor, amelynek az elején az xs páratlan, a végén pedig az xs páros elemei vannak (tetszőleges sorrendben) *) Példák: oddEven [] = Nil oddEven [5, ~3, 1] = 5 << ~3 << 1 << Nil oddEven [2, 0, ~4] = Nil >> ~4 >> 0 >> 2 oddEven [5, 1, 2, ~3, ~4, 0] = 5 << 1 << ~3 << (Nil >> 0 >> ~4 >> 2) Megoldás: fun oddEven [] = Nil | oddEven (x::xs) = if x mod 2 = 0 then oddEven xs >> x else x << oddEven xs; Pontérték: 7 pont _________ C 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ő változó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1.a | ?- 2+7 = A, \+ A = 9. siker: A = 2+7 1.b | ?- [U|V] = [a,b]. siker: U = a, V = [b] 1.c | ?- A is 3+1, A = 3+1. meghiúsulás 1.d | ?- X*Y = 2*3+1. meghiúsulás 1.e | ?- U is 2*2, V = U+3. siker: U = 4, V = 4+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 2/3+a+b +(+(/(2,3),a),b) 2.b [3/4,a,X] .(/(3,4),.(a,.(X,[]))) 2.c [u,v|[u-v*3|X]] .(u,.(v,.(-(u,*(v,3)),X))) 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 h(A*B, [C|D]) = h(1*2*3, [u,v]). A = 1*2, B = 3, C = u, D = [v] 3.b .([a], [E+2, F+E]) = [Y, X|[X]]. E = 2, F = 2, X = 2+2, Y = [a] 3.c g(G/H, [2/3+u|J]) = g(U, [U+V, V]). G = 2, H = 3, J = [u], U = 2/3, V = u 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! | ?- write(ÉÉHHNN), nl, p([É,É,H,H,N,N]), nl. Mit ír ki az fenti célsorozat, ha abban az ÉÉHHNN karakterek helyén az ön születési dátumának karakterei (pl. 811231 ill. [8,1,1,2,3,1]) szerepel? Fogalmazza meg általánosan, hogy a p/1 által kiírt szöveg hogyan függ a paramétertől! (Futtatáskor a lists könyvtár be van töltve.) p(B) :- member(A, B), A >= 2, write(-), write(A), fail. p(_). Válasz: | ?- write(811231), nl, p([8,1,1,2,3,1]), nl. 811231 -8-2-3 yes Általánosan: A hat számjegy mindegyikére: ha a számjegy nagyobb-egyenlő mint 2, akkor kiír egy - jelet és a számjegyet, egyébként nem ír ki semmit. 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! % ptlanpoz(+L, -A): A egy pozitív szám, amely páratlan indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. | ?- ptlanpoz([2,4,-2,6,8], P). P = 2 ? ; P = 8 ? ; no Megoldás: % ptlanpoz(+L, -A): A egy pozitív szám, amely páratlan indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. ptlanpoz([X|_], X) :- X > 0. ptlanpoz([_,_|L], X) :- ptlanpoz(L, X). 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(y z) f : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b 6.b fun f (y, x) = y(chr x, #"B") f : (char * char -> '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 = (ord #"1" - ord #"0") :: [0, 1, 2+3] x = [1, 0, 1, 5] : int list 7.b val x = List.foldr op:: [#"K", #"U", #"K"] [#"A", #"C"] x = [#"A", #"C", #"K", #"U", #"K"] : char list 7.c val x = map (fn i => if i >= 3 then (true, i) else (false, i)) [2,4,3,1] x = [(false, 2), (true, 4), (true, 3), (false, 1)] : (bool * 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 SAJÁT születési dátumára alkalmazza (pl. f "720431")? Válaszát indokolja! fun f x = let fun g (x::xs) (y::ys) = y :: x :: g (rev xs) ys | g _ _ = [] val zs = explode x in implode(g zs (rev zs)) end Pl. f "720431" = "173142032074" f "123456" = "615642352314" Általánosan: Az explode a bemenő füzért (string) karakterek listájává alakítja (zs : char list). A g függvény mind az egyenes sorrendű, mind a megfordított karakterlistát megkapja argumentumként, és mindkét lista első karakterét (a második argumentummal kezdve) az elé a lista elé fűzi, amelyet úgy kap, hogy a g-t alkalmazza az első lista maradékának megfordítottjára és a második maradékára, amíg el nem fogynak. A g eredménye tehát olyan karakterlista, amelyben az eredeti füzér karakterei hátulról, ill. alternálva elölről és 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 megadott könyvtári függvényekkel! local fun f0 [] zs = rev zs | f0 (y::ys) zs = f0 ys (if #"0" <= chr y andalso chr y <= #"9" then chr y::zs else zs) in fun f xs = f0 xs [] end Egy ekvivalens változata List.filter, map, Char.isDigit, chr alkalmazásával: fun f xs = List.filter Char.isDigit (map chr xs) Pl. f([45,46,47,48,49,50,56,57,58]) = [#"0", #"1", #"2", #"8", #"9"] : char list Pontérték: 6 pont 10. Adott egy előjeles egész számokat tartalmazó lista, továbbá az alábbi adattípus-deklaráció: infixr 5 <<; infix 5 >>; datatype 'a que = Nil | << of 'a * 'a que | >> of 'a que * 'a Írjon olyan függvényt lowUp néven, amely egy 'a que típusú sort állít elő úgy, hogy a listaelemek közül a kisbetűk a sor elejére, a nagybetűk pedig a sor végére kerüljenek (tetszőleges sorrendben). A sor eleje, ill. vége: a <<, ill. >> adatkonstruktorral az adatszerkezetbe illesztett értékek sorozata. Egy karakter kisbetű/nagybetű voltának meghatározására használhatja a Char.isUpper függvényt. (* lowUp : char list -> 'a que lowUp xs = olyan sor, amelynek az elején az xs-beli kisbetűk, a végén pedig az xs-beli nagybetűk vannak (tetszőleges sorrendben) *) Példák: lowUp [] = Nil lowUp [#"c", #"z", #"e"] = #"c" << #"z" << #"e" << Nil lowUp [#"C", #"Z", #"E"] = Nil >> #"E" >> #"Z" >> #"C" lowUp [#"c", #"C", #"E", #"z", #"e", #"Z"] = #"c" << #"z" << #"e" << (Nil >> #"Z" >> #"E" >> #"C") Megoldás: fun lowUp [] = Nil | lowUp (x::xs) = if Char.isUpper x then lowUp xs >> x else x << lowUp xs; Pontérték: 7 pont _________ D 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ő változó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1.a | ?- X*Y = 2*3*5. siker: X = 2*3, Y = 5 1.b | ?- X is 8+2, \+ X = 10. meghiúsulás 1.c | ?- X = Y+2, Y is 2*2. siker: X = 4+2, Y = 4 1.d | ?- [P|[Q]] = [a,b]. siker: P = a, Q = b 1.e | ?- 9+5+2 is A+B. hiba 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 u/v+1*2 +(/(u,v),*(1,2)) 2.b [1+2+3,4,X] .(+(+(1,2),3),.(4,.(X,[]))) 2.c [u,i*j|[[],d/e]] .(u,.(*(i,j),.([],.(/(d,e),[])))) 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 [p+q+r, 5+8] = [X+Y, Z|V]. V = [], X = p+q, Y = r, Z = 5+8 3.b .(U, [U, 1]) = [E+2+3, F+G, E]. E = 1, F = 1+2, G = 3, U = 1+2+3 3.c f(W/P-a, [P/4|Q]) = f(H-G, [H, G]). G = a, H = 4/4, P = 4, Q = [a], W = 4 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! | ?- write(ÉÉHHNN), nl, p([É,É,H,H,N,N]), nl. Mit ír ki az fenti célsorozat, ha abban az ÉÉHHNN karakterek helyén az ön születési dátumának karakterei (pl. 811231 ill. [8,1,1,2,3,1]) szerepel? Fogalmazza meg általánosan, hogy a p/1 által kiírt szöveg hogyan függ a paramétertől! (Futtatáskor a lists könyvtár be van töltve.) p(B) :- member(A, B), A =< 4, write(A), write(*), fail. p(_). Válasz: | ?- write(811231), nl, p([8,1,1,2,3,1]), nl. 811231 1*1*2*3*1* yes Általánosan: A hat számjegy mindegyikére: ha a számjegy kisebb-egyenlő mint 4, akkor kiírja a számjegyet majd egy * jelet, egyébként nem ír ki semmit. 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! % ptlanneg(+L, -A): A egy negatív szám, amely páratlan indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. | ?- ptlanneg([-2,-4,0,-8,-10], P). P = -2 ? ; P = -10 ? ; no Megoldás: % ptlanneg(+L, -A): A egy negatív szám, amely páratlan indexű eleme az L % számlistának. A listaelemeket 1-től számozzuk. ptlanneg([X|_], X) :- X < 0. ptlanneg([_,_|L], X) :- ptlanneg(L, X). 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 = z(y x) f : 'a -> ('a -> 'b) -> ('b -> 'c) -> 'c 6.b fun f (y, x) = y(rev x, 1) f : ('a list * int -> 'b) * 'a list -> 'b 6.c fun f x y = (y, (y, x)) f : 'a -> 'b -> 'b * ('b * 'a) 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 = [0, 1, 2+3] @ [ord #"5" - ord #"0"] x = [0, 1, 5, 5] : int list 7.b val x = List.foldl op^ ("K"^ "U" ^ "K") ["A", "C"] x = "CAKUK" : string 7.c val x = List.filter (fn c => ord c mod 2 = 0) [chr 48, chr 49, chr 50, chr 51] x = [#"0", #"2"] : char 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 SAJÁT születési dátumára alkalmazza (pl. f "720431")? Válaszát indokolja! fun f x = let fun g (x::xs) (y::ys) = y :: x :: g (rev ys) xs | g _ _ = [] val zs = explode x in implode(g zs zs) end Pl. f "720431" = "772131320044" f "123456" = "112656523344" Általánosan: Az explode a bemenő füzért (string) karakterek listájává alakítja (zs : char list). A g függvény az egyenes sorrendű karakterlistát kétszer is megkapja argumentumként, és mindkét lista első karakterét (a második argumentummal kezdve) az elé a lista elé fűzi, amelyet úgy kap, hogy a g-t alternálva alkalmazza a második lista maradékának megfordítottjára és az első maradékára, amíg el nem fogynak. A g eredménye tehát olyan karakterlista, amelyben az eredeti füzér első karaktere kétszer szerepel, majd a további karakterei hol elölről, hol 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 megadott könyvtári függvényekkel! fun f xs = let fun f0 [] zs = rev zs | f0 (y::ys) zs = f0 ys (if #"A" <= chr y andalso chr y <= #"Z" then chr y::zs else zs) in f0 xs [] end Egy ekvivalens változata List.filter, map, Char.isUpper, chr alkalmazásával: fun f xs = List.filter Char.isUpper (map chr xs) Pl. f([62,63,64,65,66,85,86,87,88,89,90,91,92,93]) = [#"A", #"B", #"U", #"V", #"W", #"X", #"Y", #"Z"] : char list Pontérték: 6 pont 10. Adott egy előjeles egész számokat tartalmazó lista, továbbá az alábbi adattípus-deklaráció: infixr 5 <<; infix 5 >>; datatype 'a que = Nil | << of 'a * 'a que | >> of 'a que * 'a Írjon olyan függvényt digNondig néven, amely egy 'a que típusú sort állít elő úgy, hogy a listaelemek közül a számjegyek a sor elejére, az egyéb karakterek pedig a sor végére kerüljenek (tetszőleges sorrendben). A sor eleje, ill. vége: a <<, ill. >> adatkonstruktorral az adatszerkezetbe illesztett értékek sorozata. Egy karakter számjegy voltának meghatározására használhatja a Char.isDigit függvényt. (* digNondig : char list -> 'a que digNondig xs = olyan sor, amelynek az elején az xs-beli számjegyek, a végén pedig az xs többi karakterei vannak (tetszőleges sorrendben) *) Példák: digNondig [] = Nil digNondig [#"9", #"5", #"4"] = #"9" << #"5" << #"4" << Nil digNondig [#"C", #"?", #":"] = Nil >> #":" >> #"?" >> #"C" digNondig [#"9", #"C", #":", #"4", #"5", #"?"] = #"9" << #"4" << #"5" << (Nil >> #"?" >> #":" >> #"C") Megoldás: fun digNondig [] = Nil | digNondig (x::xs) = if Char.isDigit x then x << digNondig xs else digNondig xs >> x; Pontérték: 7 pont