Deklaratív programozás nagyzárthelyi Budapest, 2005. április 22. =========================== SML megoldások, V1.0, dp05s-zh1-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) [op>(1.3, 2), "a" = #"b", true] - real és int nem hasonlítható össze - string és char nem hasonlítható össze (b)(chr 65, 2*4 = 4+4, ~12) = ("B", 8, ~5-7) - char és string nem hasonlítható össze - bool és int nem hasonlítható össze (c) foldl op^ [(1,0),(3,4),(2,1)] ~10 - foldl paramétereinek sorrendje hibás (f xs e), helyesen: f e xs - op^ operátor itt nem használható -- helyette állhatna pl. (fn ((x,y),z) => x*y+z). 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-t, ahol a nem megfelelő operátor használatának felismerésére 2 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 "X" @ tl(explode "mas") t = #"a" (b) val (_::_::t) = List.filter Char.isDigit (explode "1a2b3c4d") t = [#"3", #"4"] (c) val t = map (fn (a,b) => a bool) -> 'a list -> 'a list list *) fun g cmp [] = [] | g cmp (x::xs) = let (* f : 'a * 'a list * 'a list * 'a list list -> 'a list list *) fun f (x, [], zs, zss) = rev(x::zs)::zss | f (x, y::ys, zs, zss) = if cmp(x, y) then f(y, ys, x::zs, zss) else f(y, ys, [], rev(x::zs)::zss) in f(x, 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 op> [4,3] x = [[4, 3]] (b) val x = g op< [4,3] x = [[3], [4]] (c) val x = g op> [3,4,3,4] x = [[4], [4, 3], [3]] (d) val x = g op< [1,2,2,5,6,5,6,0,5,2,2] x = [[2], [2], [0, 5], [5, 6], [2, 5, 6], [1, 2]] (e) val x = map implode (g op< (explode "abcbgefgfh")) x = ["fh", "efg", "bg", "abc"] Végül fejezze be a fejkommentet! (f) (* g cmp xs = olyan listák listája, amelyek az xs lista cmp szerint ... *) "... haladó, az elemek eredeti sorrendjét megőrző futamait tartalmazzák, miközben a futamok az eredetihez képest fordított sorrendben következnek." Pontozás (összesen max. 8 pont): 7.a-7.d-re helyes válaszért 1-1, 7.e-7.f-re 2-2 pont jár. 8. Tekintsük az alábbi adattípus-deklarációt: datatype 'a G = A of 'a | B of 'a G list Fejsúlyosnak nevezzük az olyan (x, y) párokat, amelyekre x > y. Írjon olyan függvényt fejsulyosak néven, amely egy (int * int) G típusú adatstruktúrában található fejsúlyos párok számá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. (* fejsulyosak : (int * int) G -> int fejsulyosak t = a t-beli fejsúlyos párok száma *) Példák: fejsulyosak(A(3,4)) = 0; fejsulyosak(A(4,3)) = 1; fejsulyosak(A(3,3)) = 0; fejsulyosak(B[]) = 0; fejsulyosak(B[B[],B[],A(4,3)]) = 1; fejsulyosak(B[B[A(8,2),A(6,9), B[A(7,5),B[A(8,7)],A(~2,7)]],B[],A(4,3)]) = 4; Egy megvalósítása magasabbrendű függvénnyel: fun fejsulyosak (A(x,y)) = if x > y then 1 else 0 | fejsulyosak (B zs) = foldl (fn (x,y) => fejsulyosak x + y) 0 zs; Segédfüggvénnyel, akkumulátorral: fun fejsulyosak t = let (* fS : (int * int) G * int -> int fS (t, n) = n + a t-beli fejsúlyos párok száma *) fun fS (A(x,y), n) = if x > y then n+1 else n | fS (B[], n) = n | fS (B(z::zs), n) = fS(B zs, fS(z, n)) in fS(t, 0) end; 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"), 7 mod 3] - real és int nem hasonlítható össze - a 7 mod 3 kifejezés nem bool típusú a listában (b) (chr 64, 4, ~12) = (ord #"b", 2+2 = 4 div 1, ~7-7) - a chr 64 kifejezés nem int típusú, chr elhagyandó - a 2+2 = 4 div 1 kifejezés nem int típusú (c) foldr ~10.0 (op div) [(1.4,0.6),(3.4,4.7),(2.1,1.9)] - foldr paramétereinek sorrendje hibás (e f xs), helyesen: f e xs - op div operátor itt nem használható -- helyette állhatna pl. (fn ((x,y),z) => x*y+z). 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-t, ahol a nem megfelelő operátor használatának felismerésére 2 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::_::_) = tl(explode "ban") @ explode "g" t = #"n" (b) val (_::_::_::t) = List.filter Char.isAlpha (explode "1a2b3c4d") t = [#"d"] (c) val t = map (fn (a,b) => a>=b) [(4+2,2*2), (1,2), (ord #"9",ord #"8")] t = [true, false, true] Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. 7. Tekintsük a következő függvénydefiníciót! (* g : ('a * 'a -> bool) -> 'a list -> 'a list list *) fun g cmp [] = [] | g cmp (x::xs) = let (* f : 'a * 'a list * 'a list * 'a list list -> 'a list list *) fun f (x, [], zs, zss) = rev((x::zs)::zss) | f (x, y::ys, zs, zss) = if cmp(x, y) then f(y, ys, x::zs, zss) else f(y, ys, [], (x::zs)::zss) in f(x, 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 op> [4,3] x = [[3, 4]] (b) val x = g op< [4,3] x = [[4], [3]] (c) val x = g op> [3,4,3,4] x = [[3], [3, 4], [4]] (d) val x = g op< [1,2,2,5,6,5,6,0,5,2,2] x = [[2, 1], [6, 5, 2], [6, 5], [5, 0], [2], [2]] (e) val x = map implode (g op< (explode "abcbgefgfh")) x = ["cba", "gb", "gfe", "hf"] Végül fejezze be a fejkommentet! (f) (* g cmp xs = olyan listák listája, amelyek az xs lista cmp szerint ... *) "... haladó, az elemek eredeti sorrendjét megfordító futamait tartalmazzák, miközben a futamok sorrendje az eredeti." Pontozás (összesen max. 8 pont): 7.a-7.d-re helyes válaszért 1-1, 7.e-7.f-re 2-2 pont jár. 8. Tekintsük az alábbi adattípus-deklarációt: datatype 'a H = V of 'a | N of 'a H list Farsúlyosnak nevezzük az olyan (x, y) párokat, amelyekre x < y. Írjon olyan függvényt farosszeg néven, amely egy (int * int) H típusú adatstruktúrában található farsúlyos párok második tagjának összegé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. (* farosszeg : (int * int) H -> int farosszeg t = a t-beli farsúlyos (x,y) párok y-nal jelölt tagjainak összege *) Példák: farosszeg(V(3,4)) = 4; farosszeg(V(4,4)) = 0; farosszeg(V(4,3)) = 0; farosszeg(N[]) = 0; farosszeg(N[N[],N[],V(3,4)]) = 4; farosszeg(N[N[V(8,2),V(6,9), N[V(7,5),N[V(8,7)],V(~2,7)]],N[],V(4,3)]) = 16; Egy megvalósítása magasabbrendű függvénnyel: fun farosszeg (V(x,y)) = if x < y then y else 0 | farosszeg (N zs) = foldl (fn (x,y) => farosszeg x + y) 0 zs; Segédfüggvénnyel, akkumulátorral: fun farosszeg t = let (* fO : (int * int) H * int -> int fO (t, n) = n + a t-beli farsúlyos (x,y) párok y-nal jelölt tagjainak összege *) fun fO (V(x,y), n) = if x < y then n+y else n | fO (N[], n) = n | fO (N(z::zs), n) = fO(N zs, fO(z, n)) in fO(t, 0) end; 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.