Deklaratív programozás nagyzárthelyi Budapest, 2004. október 28. =========================== SML megoldások, V1.0, dp04a-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. Mik ezek? (a) let val (x, y, z) = (4.5, 5, "A") in [y-x, ord z] end - int-ből (y=5) nem vonható ki real (x=4.5) - ord nem alkalmazható stringre (z="A") (b) ("0", [33], fn _ => 1) = (#"1", [3+3], fn y => 2) - string és char egyenlősége nem vizsgálható - függvények egyenlősége nem vizsgálható (c) foldr op* [(1,0),(2,1),(3,4)] 10 - foldr 2. és 3. paramétere fel van cserélve - foldr op* 10 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 t értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::t::_) = explode "lap" @ tl(explode "pos") t = #"a" (b) val t = map (fn (x,y) => x=y) [(1,2), (2,2), (ord #"A",ord #"a")] t = [false, true, false] (c) val (_::t) = List.filter (fn (x,y) => x<>y) [(ord #"A",ord #"a"), (2,2), (1,1+1)] t = [(1, 2)] Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. 6.c-re csak 2 pont jár [(1, 1+1)] válasz esetén. 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 (r1::r2::rs) = (r1,r2) :: f ((r1*r2)::rs) | 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 [2,3,5,7,11] x = [6, 30, 210, 2310] (a2) val x = g [~1] x = [] (a3) val x = g [~1,1] x = [~1] (a4) val x = g [] x = [] (b) Mutassa be az f [2,3,5,7,11] függvényalkalmazás egyszerűsítési lépéseit, mohó kiértékelést feltételezve! f [2,3,5,7,11] --> (2,3) :: f [6,5,7,11] --> (2,3) :: (6,5) :: f [30,7,11] --> (2,3) :: (6,5) :: (30,7) :: f [210,11] --> (2,3) :: (6,5) :: (30,7) :: (210,11) f [2310] --> (2,3) :: (6,5) :: (30,7) :: (210,11) :: [] --> (2,3) :: (6,5) :: (30,7) :: [(210,11)] --> (2,3) :: (6,5) :: [(30,7), (210,11)] --> ... --> [(2,3), (6,5), (30,7), (210,11)] 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. Egy egészeket tartalmazó számlistában összegelemnek hívunk egy elemet, ha az egyenlő az előtte előforduló elemek összegével. Írjon olyan SML-függvényt osszegelemek néven, amelynek egy egészlista a paramétere, az eredménye pedig az egészlistában előforduló összegelemek listája eredeti előfordulásuk sorrendjében! Definiálja a megfelelő segédfüggvényt, és írjon hozzá fejkommentet. (* osszegelemek : int list -> int list osszegelemek ls = az ls listában előforduló összegelemek listája *) Példák: osszegelemek [0,1,6] = [0]; osszegelemek [3,3,1,7] = [3,7]; osszegelemek [~1,2,1,~4,~2,2] = [1,~2] Egy megvalósítása: fun osszegelemek xs = let (* ossze : int * int list -> int list ossze (s, ys) = azoknak az ys-beli elemeknek a listája, amelyek az őket megelőző elemek s-ben akkumulálódó összegével egyenlők *) fun ossze (_, []) = [] | ossze (s, y::ys) = if s=y then y :: ossze(s+y, ys) else ossze(s+y, ys) in ossze(0, xs) end; 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). Fejkomment hiánya: -2 pont, de nem követelmény a fejkommentben a függvény típusának specifikálása. Nem követelmény a hatékony program sem. ------------------- 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. Mik ezek? (a) let val (z, y, x) = (#"y", 4, 5.0) in [ord z + ord y, x] end - ord paramétere nem lehet int (y=4) - a listaelemek csak azonos típusúak lehetnek (ord z + ord y : int, x : real) (b) (["0"], 6, fn x => x*2) = ([#"0"], 3+3, fn y => y*4) - string list és char list egyenlősége nem vizsgálható - függvények egyenlősége nem vizsgálható (c) foldr 1.0 op/ [(1.2,0.3),(2.4,1.2),(3.6,4.0)] - foldr 1. és 2. paramétere fel van cserélve - foldr op/ 1.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 w értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::_::_::w) = explode "pus" @ rev(explode "gom") w = [#"m", #"o", #"g"] (b) val w = map (fn (x,y) => x<>y) [(4,2*2),(1,2),(ord #"9",ord #"9")] w = [false, true, false] (c) val (_::w) = List.filter (fn (x,y) => x=y) [(ord #"9",ord #"9"), (1,2), (4,2*2)] w = [(4, 4)] Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. 6.c-re csak 2 pont jár [(4, 2*2)] válasz esetén. 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 (n1::n2::ns) = (n1,n2) :: f ((n2+n1)::ns) | f _ = [] fun g zs = map (fn (x,y) => y*x) (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 [2,3,5,7,11] x = [6, 25, 70, 187] (a2) val x = g [~1] x = [] (a3) val x = g [~1,1] x = [~1] (a4) val x = g [] x = [] (b) Mutassa be az f [2,3,5,7,11] függvényalkalmazás egyszerűsítési lépéseit mohó kiértékelést feltételezve! f [2,3,5,7,11] --> (2,3) :: f [5,5,7,11] --> (2,3) :: (5,5) :: f [10,7,11] --> (2,3) :: (5,5) :: (10,7) :: f [17,11] --> (2,3) :: (5,5) :: (10,7) :: (17,11) f [28] --> (2,3) :: (5,5) :: (10,7) :: (17,11) :: [] --> (2,3) :: (5,5) :: (10,7) :: [(17,11)] --> (2,3) :: (5,5) :: [(10,7), (17,11)] --> ... --> [(2,3), (5,5), (10,7), (17,11)] 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! Ha f-ben és g-ben ugyanazzal a művelettel számolt (mindkettőben szorzással vagy mindkettőben összeadással), és jól, észrevételezzük, de nem vonunk le pontot. 7.b Helyes válaszért 3 pont. Nem elvárás az ennyire részletes kifejtés. 8. Egy egészeket tartalmazó számlistában csúcselemnek hívunk egy elemet, ha az nagyobb, mint az előtte előforduló elemek összege. Írjon olyan SML-függvényt csucselemek néven, amelynek egy egészlista a paramétere, az eredménye pedig az egészlistában előforduló csúcselemek listája eredeti előfordulásuk sorrendjében! Definiálja a megfelelő segédfüggvényt, és írjon hozzá fejkommentet. (* csucselemek : int list -> int list csucselemek ls = az ls listában előforduló csúcselemek listája *) Példák: csucselemek [1,~2] = [1]; csucselemek [3,3,1,8] = [3,8]; csucselemek [~1,2,3,~4,~2,2] = [2,3,2] Egy megvalósítása: fun csucselemek xs = let (* csucse : int * int list -> int list csucse (s, ys) = azoknak az ys-beli elemeknek a listája, amelyek az őket megelőző elemek s-ben akkumulálódó összegénél nagyobbak *) fun csucse (_, []) = [] | csucse (s, y::ys) = if s