Deklaratív programozás pózárthelyi Budapest, 2004. május 6. ================================== SML megoldások, V1.0, dp04s-zh2-mlmegol.txt ------------------- A csoport ------------------- 5. Az alábbi, egymástól független, szintaktikailag helyes SML-kifejezésekben kifejezésenként két-két hiba van. Mik ezek? (a) let val (a, b, c, d) = (4, 5.0, #"A") in [a+b, ord c] end - négyeshez nem köthető hármas - int (a=4) és real (b=5.0) nem adható össze (b) (#"0", 33::[], fn x => x) = ("0", [3+3], fn y => 2*y) - char és string egyenlősége nem vizsgálható - függvények egyenlősége nem vizsgálható (c) foldr op+ [(1,0),(2,1),(3,4)] 0 - foldr 2. és 3. paramétere fel van cserélve - foldr op+ 0 egészek (nem egészpárok) listáját várja Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Minden hiba megtalálása 1 pontot, az 5.c esetben az 'egészpárok listája helyett egészek listája kell' felismerés 2 pontot ér. 6. Mi a z értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::_::z::_) = tl(explode "Mara") @ explode "Maros" z = #"a" : char (b) val z = map (fn (x,y) => x<>y) [(1,2), (2,2), (ord #"A",ord #"a")] z = [true, false, true] : bool list (c) val (_::z) = List.filter (fn (x,y) => x<>y) [(ord #"A",ord #"a"), (2,2), (1,2)] z = [(1, 2)] : (int * int) list Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. A feladatokban csak a kifejezések értékét kérdezzük, a típusukat nem! 7. Nézzük a következő függvények definícióját! fun f (x::y::ys) = (x,y) :: f ((x+y)::ys) | f _ = [] fun g zs = map (fn (a,b) => b-a) (f zs) (a) Mi az x értéke az alábbi, egymástól független deklarációk kiértékelése után? (a1) val x = g [1,2,3,4,5] x = [1, 0, ~2, ~5] : int list (a2) val x = g [~1] x = [] : int list (a3) val x = g [~1,1] x = [2] : int list (a4) val x = g [] x = [] : int list (b) Mutassa be az f([1,2,3,4,5]) függvényalkalmazás egyszerűsítési lépéseit, mohó kiértékelést feltételezve! f [1,2,3,4,5] --> (1,2) :: f [3,3,4,5] --> (1,2) :: (3,3) :: f [6,4,5] --> (1,2) :: (3,3) :: (6,4) :: f [10,5] --> (1,2) :: (3,3) :: (6,4) :: (10,5) f [15] --> (1,2) :: (3,3) :: (6,4) :: (10,5) :: [] --> (1,2) :: (3,3) :: (6,4) :: [(10,5)] --> (1,2) :: (3,3) :: [(6,4), (10,5)] --> ... --> [(1,2), (3,3), (6,4), (10,5)] Pontozás (összesen max. 7 pont): 7.a Minden helyes válaszért 1-1 pont. A feladatokban csak a kifejezések értékét kérdezzük, a típusukat nem! 7.b Helyes válaszért 3 pont. Nem elvárás az ennyire részletes kifejtés. 8. Futamhármasnak nevezzük egy egészlista három szomszédos elemét, ha monoton növekvő vagy monoton csökkenő sorozatot alkotnak. Írjon olyan SML-függvényt futamok néven, amelynek eredménye egy egészlistában lévő futamhármasok száma. Segédfüggvényt definiálhat (fejkommenttel!). (* futamok : int list -> int futamok zs = a zs-beli futamhármasok száma *) Példák: futamok [1,2,5] = 1; futamok [1,2,2,8,7] = 2; futamok [~1,~2,~3,1,2,3] = 3; futamok [1,2,3,~1,~2,~3] = 3; futamok [1,2,1] = 0; futamok [1,2] = 0; Egy megvalósítása: fun futamok (x::(yzzs as y::z::zs)) = (if x<=y andalso y<=z orelse x>=y andalso y>=z then 1 else 0) + futamok yzzs | futamok _ = 0 Pontozás (összesen max. 9 pont): Minden kisebb hibáért 1-1 pont, minden súlyos hibáért 2 vagy 3 pont levonás. Súlyos hibának számít pl. az else ág elhagyása (-2 pont) vagy a végtelen rekurzió (-3 pont). Nem követelmény a hatékony program. ------------------- B csoport ------------------- 5. Az alábbi, egymástól független, szintaktikailag helyes SML-kifejezésekben kifejezésenként két-két hiba van. Mik ezek? (a) let val (x, y, z) = (#"x", "y", 5, 4.0) in [ord x + ord y, z] end - hármashoz nem köthető négyes - ord paramétere nem lehet string (y="y") (b) (["0"], 6, fn x => 2*x) = (["0"::[]], 3+3, fn y => 2*y) - string list és string list list egyenlősége nem vizsgálható - függvények egyenlősége nem vizsgálható (c) foldr 1.0 [(1.2,0.3),(2.4,1.2),(3.6,4.0)] op/ - foldr paramétereinek hibás a sorrendje (balra vannak rotálva) - foldr op/ 0 valósak (nem valóspárok) listáját várja Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Minden hiba megtalálása 1 pontot, az 5.c esetben a 'valóspárok listája helyett valósak listája kell' felismerés 2 pontot ér. 6. Mi a z értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::_::_::z::_) = rev(explode "Mara") @ explode "Maros" z = #"M" : char (b) val z = map (fn (a,b) => a=b) [(4,2*2), (1,2), (ord #"9",ord #"9")] z = [true, false, true] : bool list (c) val (_::z) = List.filter (fn (a,b) => a=b) [(ord #"9",ord #"9"), (1,2), (4,2*2)] z = [(4, 4)] : (int * int) list Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. A feladatokban csak a kifejezések értékét kérdezzük, a típusukat nem! 7. Nézzük a következő függvények definícióját! fun f (x::y::ys) = (x,y) :: f ((y-x)::ys) | f _ = [] fun g zs = map (fn (a,b) => b-a) (f zs) (a) Mi az x értéke az alábbi, egymástól független deklarációk kiértékelése után? (a1) val x = g [1,2,3,4,5] x = [1, 2, 2, 3] : int list (a2) val x = g [~1] x = [] : int list (a3) val x = g [~1,1] x = [2] : int list (a4) val x = g [] x = [] : int list (b) Mutassa be az f([1,2,3,4,5]) függvényalkalmazás egyszerűsítési lépéseit mohó kiértékelést feltételezve! f [1,2,3,4,5] --> (1,2) :: f [1,3,4,5] --> (1,2) :: (1,3) :: f [2,4,5] --> (1,2) :: (1,3) :: (2,4) :: f [2,5] --> (1,2) :: (1,3) :: (2,4) :: (2,5) f [3] --> (1,2) :: (1,3) :: (2,4) :: (2,5) :: [] --> (1,2) :: (1,3) :: (2,4) :: [(2,5)] --> (1,2) :: (1,3) :: [(2,4), (2,5)] --> ... --> [(1,2), (1,3), (2,4), (2,5)] Pontozás (összesen max. 7 pont): 7.a Minden helyes válaszért 1-1 pont. A feladatokban csak a kifejezések értékét kérdezzük, a típusukat nem! 7.b Helyes válaszért 3 pont. Nem elvárás az ennyire részletes kifejtés. 8. Pozneghármasnak nevezzük egy egészlista három szomszédos elemét, ha az elsô és második, illetve a második és harmadik elem különbsége azonos előjelű. Írjon olyan SML-függvényt poznegek néven, amelynek eredménye egy egészlistában lévő pozneghármasok száma. Segédfüggvényt definiálhat (fejkommenttel!). (* poznegek : int list -> int poznegek zs = a zs-beli pozneghármasok száma *) Példák: poznegek [1,2,5] = 1; poznegek [1,2,2,8,7] = 2; poznegek [~1,~2,~3,1,2,3] = 3; poznegek [1,2,3,~1,~2,~3] = 3; poznegek [1,2,1] = 0; poznegek [1,2] = 0; poznegek [] = 0; Néhány megvalósítása: (* 0-t negatívnak és pozitívnak egyaránt elfogadó megoldások *) fun poznegek (x::(yzzs as y::z::zs)) = (if (x-y) * (y-z) >= 0 then 1 else 0) + poznegek yzzs | poznegek _ = 0; fun poznegek (x::(yzzs as y::z::zs)) = (if x<=y andalso y<=z orelse x>=y andalso y>=z then 1 else 0) + poznegek yzzs | poznegek _ = 0; (* 0-t pozitívnak elfogadó megoldás *) fun poznegek (x::(yzzs as y::z::zs)) = (if x=y andalso y>=z then 1 else 0) + poznegek yzzs | poznegek _ = 0; Megjegyzés: A 2. példa hibás, helyesen pl. ennek kellett volna lennie: poznegek [1,2,4,8,7] = 2. poznegek [1,2,2,8,7] = 2 akkor igaz, ha a 0-t negatívnak (is) tekintjük. A hiányos specifikáció és a hibás példa miatt jó a megoldás, ha valaki a 0-t (1) sem pozitívnak, sem negatívnak, (2) pozitívnak vagy negatívnak, (3) csak pozitívnak, (4) csak negatívnak veszi. Pontozás (összesen max. 9 pont): Minden kisebb hibáért 1-1 pont, minden súlyos hibáért 2 vagy 3 pont levonás. Súlyos hibának számít pl. az else ág elhagyása (-2 pont) vagy a végtelen rekurzió (-3 pont). Nem követelmény a hatékony program.