Deklaratív programozás pótzárthelyi Budapest, 2005. május 3. ======================== SML megoldások, V1.0, dp05s-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 statikus szemantikai hiba van. Melyek ezek? (a) [(1.3 = 2), op^("a", #"b") = "ab", [] = [4*1]] - real és int nem hasonlítható össze - op^ mindkét paraméterének string típusúnak kell lennie (b) (ord "B", 2-4 = 4-2, ~3.4) = (65, true, ~3-4) - ord char típusú paramétert vár - real és int nem hasonlítható össze (c) foldl (fn (a,b) => explode a @ b) #" " ["egy", "ketto", #"3"] - a lista harmadik elemének is string típusúnak kell lennie - foldl második paraméterének char list típusúnak kell lennie Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Minden hiba megtalálása 1 pontot ér, kivéve az 5.c második hibáját ("foldl második paramétere"), ahol hibátlan válaszra 2 pontot, kishibás válaszra 1 pontot adunk. 6. Mi a t értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::_::t::_) = explode "ab" @ tl(rev(explode "cde")) t = #"d" (b) val (s::t) = List.filter (fn (a,b) => (a<=b)) [(4+0,2*2), (2,2-1), (2-1,2)] t = [(1, 2)] (c) val t = map length [explode "1a2b3c4d", [#"Q"], [], explode ""] t = [8, 1, 0, 0] Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. Hibákért 1-1 pont levonás. 7. Tekintsük a következő függvénydefiníciót! (* g : int list -> int -> int list f : int list * int list -> int list *) fun g n xs = let fun f (a::b::c::cs, zs) = if a+b>n then f(b::c::cs, 10*n+c::zs) else f(b::c::cs, zs) | f (_, zs) = rev zs in f(xs, []) end; Mi az x értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val x = g 7 [1,2,3,4,5,6] x = [76] (b) val x = g 9 [1,2,3,4,5,6] x = [] (c) val x = g 4 [1,~2,3,4,~5,6,7,8,9] x = [35, 48, 49] (d) val x = g 9 [1,~2,3,4,~5,6,7,8,9] x = [98, 99] Fejezze be a fejkommentet! (e) (* g 0 xs = az xs összes olyan eleméből álló lista, amelyek ... *) ... amelyeket közvetlenül megelőző két elem összege pozitív Pontozás (összesen max. 8 pont): 7.a-7.b-re helyes válaszért 1-1, 7.c-7.e-re 2-2 pont jár. 8. Tekintsük az alábbi adattípus-deklarációt: datatype 'a H = A of 'a | B of 'a H list Farnehéznek nevezzük az olyan (a, b, c, d) négyest, amelyre a + b + c <= d. Írjon olyan függvényt farnehezek néven, amely egy (int*int*int*int) H típusú adatstruktúrában található farnehezek eredeti sorrendet megőrző listáját adja eredményül. Törekedjék hatékony megoldásra és magasabbrendű függvény alkalmazására. Segédfüggvényt definiálhat, ha ír hozzá fejkommentet. (* farnehezek : (int * int * int * int) H -> (int * int * int * int) list farnehezek t = a t-beli farnehezek eredeti sorrendet megőrző listája *) Példák: farnehezek(A(6,4,~3,3)) = []; farnehezek(A(4,3,0,8)) = [(4,3,0,8)]; farnehezek(A(4,3,~7,0)) = [(4,3,~7,0)]; farnehezek(B[]) = []; farnehezek(B[B[],B[],A(6,4,~2,9)]) = [(6,4,~2,9)]; farnehezek(B[B[A(1,2,4,8),A(6,3,0,9),B[A(0,1,3,2),B[A(8,~7,0,0)]]], B[],A(4,3,1,9)]) = [(1,2,4,8), (6,3,0,9), (4,3,1,9)]; Néhány megvalósítása: fun farnehezek (A(h as (a,b,c,d))) = if d >= a+b+c then [h] else [] | farnehezek (B[]) = [] | farnehezek (B(z::zs)) = farnehezek z @ farnehezek(B zs); fun farnehezek t = let fun fnagyok (A(h as (a,b,c,d)), ws) = if d>=a+b+c then h::ws else ws | fnagyok (B[], ws) = ws | fnagyok (B(z::zs), ws) = fnagyok(B zs, fnagyok(z, ws)) in rev(fnagyok (t, [])) end; fun farnehezek (A(h as (a,b,c,d))) = if d >= a+b+c then [h] else [] | farnehezek (B zs) = foldr (fn (h, ws) => farnehezek h @ ws) [] zs; fun farnehezek (A(h as (a,b,c,d))) = if d >= a+b+c then [h] else [] | farnehezek (B zs) = rev(foldl (fn (h, ws) => rev(farnehezek h) @ ws) [] zs); (* Pallinger Péter megoldása *) fun farnehezek (A(h as (a,b,c,d))) = if d >= a+b+c then [h] else [] | farnehezek (B zs) = List.concat(map farnehezek zs); Pontozás (összesen max. 8 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). Fejkomment hiánya: -2 pont, de nem követelmény a fejkommentben a függvény típusának specifikálása. Ha nagyon rossz a program hatékonysága, -2 pont a levonás. ------------------- B csoport ------------------- 5. Az alábbi, egymástól független, szintaktikailag helyes SML-kifejezésekben kifejezésenként két-két statikus szemantikai hiba van. Melyek ezek? (a) [1.0 > 2, op=(#"a", "b") = false, [7-3] = []] - real és int nem hasonlítható össze - char és string nem hasonlítható össze (b) (93, 0, ~12) = (ord "b", 2+1 = 4-1, ~7-7) - ord char típusú paramétert vár - int és bool nem hasonlítható össze (c)foldr (fn (a,b) => implode a ^ b) #"i" [[#"a", #"z"], "abc", [#"3"]] - a lista második elemének is char list típusúnak kell lennie - foldr második paraméterének string típusúnak kell lennie Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Minden hiba megtalálása 1 pontot ér, kivéve az 5.c második hibáját ("foldr második paramétere"), ahol hibátlan válaszra 2 pontot, kishibás válaszra 1 pontot adunk. 6. Mi a t értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::_::t::_) = rev(tl(explode "abc")) @ explode "de" t = #"d" (b) val (s::t) = List.filter (fn (a,b) => (a>=b)) [(4+0,2*2), (2,2-1), (2-1,2)] t = [(2, 1)] (c) val t = map length [explode "", explode "d4c3b2a1", [], [#"R", #"S"]] t = [0, 8, 0, 2] Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. Hibákért 1-1 pont levonás. 7. Tekintsük a következő függvénydefiníciót! (* g : int list -> int -> int list f : int list * int list -> int list *) fun g n xs = let fun f (a::b::c::cs, zs) = if a+b y + z. Írjon olyan függvényt fejenagyok néven, amely egy (int*int*int) G típusú adatstruktúrában található fejenagyok eredeti sorrendet megőrző listáját adja eredményül. Törekedjék hatékony megoldásra és magasabbrendű függvény alkalmazására. Segédfüggvényt definiálhat, ha ír hozzá fejkommentet. (* fejenagyok : (int * int * int) G -> (int * int * int) list fejenagyok t = a t-beli fejenagyok eredeti sorrendet megőrző listája *) Példák: fejenagyok(A(6,4,3)) = []; fejenagyok(A(4,3,0)) = [(4,3,0)]; fejenagyok(A(4,3,1)) = []; fejenagyok(B[]) = []; fejenagyok(B[B[],B[],A(6,4,1)]) = [(6,4,1)]; fejenagyok(B[B[A(8,2,4),A(6,9,4),B[A(7,5,1),B[A(8,7,1)],A(~1,7,~9)]], B[],A(4,3,0)]) = [(8,2,4), (7,5,1), (~1,7,~9), (4,3,0)]; Néhány megvalósítása: fun fejenagyok (A(h as (x,y,z))) = if x > y+z then [h] else [] | fejenagyok (B[]) = [] | fejenagyok (B(z::zs)) = fejenagyok z @ fejenagyok(B zs); fun fejenagyok t = let fun fnagyok (A(h as (x,y,z)), ws) = if x>y+z then h::ws else ws | fnagyok (B[], ws) = ws | fnagyok (B(z::zs), ws) = fnagyok(B zs, fnagyok(z, ws)) in rev(fnagyok (t, [])) end; fun fejenagyok (A(h as (x,y,z))) = if x > y+z then [h] else [] | fejenagyok (B zs) = foldr (fn (h, ws) => fejenagyok h @ ws) [] zs; fun fejenagyok (A(h as (x,y,z))) = if x > y+z then [h] else [] | fejenagyok (B zs) = rev(foldl (fn (h, ws) => rev(fejenagyok h) @ ws) [] zs); (* Pallinger Péter megoldása *) fun fejenagyok (A(h as (x,y,z))) = if x > y+z then [h] else [] | fejenagyok (B zs) = List.concat(map fejenagyok zs); Pontozás (összesen max. 8 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). Fejkomment hiánya: -2 pont, de nem követelmény a fejkommentben a függvény típusának specifikálása. Ha nagyon rossz a program hatékonysága, -2 pont a levonás.