Deklaratív programozás pótzárthelyi Budapest, 2004. november 25. ============================ SML megoldások, V1.0, dp04a-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) let val (x, y, z) = (4, ~4.0, #"A") in [y-x, chr z] end - real-ből (y=~4.0) nem vonható ki int (x=4) - chr nem alkalmazható char-ra (z=#"A") (b) ("0.0", [3+3], fn x => x) = (#"1", [3+6], fn y => y) - string és char egyenlősége nem vizsgálható - függvények egyenlősége nem vizsgálható (c) foldr op:: 0 [1,2,3.0] - listában csak azonos típusú elemek lehetnek - foldr op:: nem int, hanem int list típusú egységelemet vár Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Minden hiba megtalálása 1 pontot, 5.c második válasza 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 "top") t = [#"o", #"p"] (b) val t = map (fn (n,m) => n<>m) [(1,2), (ord #"A",ord #"a"), (2,2), (round 5.2,floor 5.9) ] t = [true, true, false, false] (c) val (_::t::_) = List.filter (fn (n,m) => n=m) [(ord #"z",ord #"z"), (2,2), (1,1+1), (round 5.2,floor 5.9) ] t = (2, 2) Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-3-2 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 (r1::r2::r3::rs) = (r1,r3) :: f (r2::rs) | f _ = [] fun g zs = map (fn (a,b) => a*b) (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 = [10, 33] (a2) val x = g [~1,~2,~3,~4,~5] x = [3, 10] (a3) val x = g [1,2,0] x = [0] (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,5) :: f [3,7,11] --> (2,5) :: (3,11) :: f [7] --> (2,5) :: (3,11) :: (30,7) :: [] --> (2,5) :: [(3,11)] --> [(2,5), (3,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. Kevésbé részletes kifejtés is elfogadható. 8. Mértani számhármasnak nevezzük a három pozitív (>0) egészből álló, egész hányadosú mértani sorozatot alkotó hármast. Írjon olyan SML-függvényt mertani néven, amelynek paramétere egy egészeket tartalmazó lista, az eredménye pedig szomszédos listaelemekből álló mértani számhármasok listája! Segédfüggvényt definiálhat, ha ír hozzá fejkommentet. (* mertani : int list -> (int * int * int) list mertani ls = az ls lista szomszédos elemeiből álló mértani számhármasok listája *) Példák: mertani [] = []; mertani [4,8] = []; mertani [2,4,8] = [(2,4,8)]; mertani [2,4,8,8,8] = [(2,4,8),(8,8,8)]; mertani [2,4,8,16] = [(2,4,8),(4,8,16)]; mertani [2,4,8,17] = [(2,4,8)]; mertani [1,3,12,48,16] = [(3,12,48)]; mertani [~2,~4,~8] = []; Egy megvalósítása: fun mertani xs = let fun (* m0 : int list -> (int * int * int) list -> (int * int * int) list m0 zs ss = a zs lista szomszédos elemeiből álló mértani számhármasok listája az ugyancsak mértani számhármasokat tartalmazó ss lista elé fűzve *) m0 (x::y::z::zs) ss = m0 (y::z::zs) (if 0 x*2) = (["0"], 3+3, fn y => y*2) - char list és string list egyenlősége nem vizsgálható - függvények egyenlősége nem vizsgálható (c) foldr op^ 0 ["a","b",#"c"] - listában csak azonos típusú elemek lehetnek - foldr op^ nem int, hanem string típusú egységelemet vár Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Minden hiba megtalálása 1 pontot, 5.c második válasza 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 "sutak") w = [#"k", #"a", #"t", #"u", #"s"] (b) val w = map (fn (x,y) => x=y) [(1*2,2*1), (1,2), (ord #"9",~(ord #"9")), (round 3.7,floor 4.2) ] w = [true, false, false, true] (c) val (_::w) = List.filter (fn (x,y) => x<>y) [(ord #"9",~(ord #"9")), (1,2), (1*2,2*1), (round 3.7,floor 4.2) ] w = [(1, 2)] Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-3-2 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 (n1::n2::n3::ns) = (n1 + n3 div 2, n2) :: f (n3::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 = [12, 70] (a2) val x = g [~1,~2,~3,~4,~5] x = [6, 24] (a3) val x = g [~1,2,0] x = [~2] (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] --> (4,3) :: f [5,7,11] --> (4,3) :: (10,7) :: f [11] --> (4,3) :: (10,7) :: [] --> (4,3) :: [(10,7)] --> [(4,3), (10,7)] 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. Kevésbé részletes kifejtés is elfogadható. 8. Rendezett pithagoraszi számhármasnak nevezzük az olyan pozitív (>0) egészekből álló (x,y,z) hármast, amely kielégíti az x*x+y*y=z*z egyenletet, és amelyre x (int * int * int) list pithagoraszi ls = az ls lista szomszédos elemeiből álló pithagoraszi számhármasok listája *) Példák: pithagoraszi [] = [] pithagoraszi [3,4] = [] pithagoraszi [1,3,4,5,6,7] = [(3,4,5)] pithagoraszi [1,4,3,5,3,7,24,25] = [(7,24,25)] pithagoraszi [7,24,25,5,16,63,65] = [(7,24,25),(16,63,65)] pithagoraszi [3,4,5,12,13] = [(3,4,5),(5,12,13)] pithagoraszi [~5,~4,~3] = [] Egy megvalósítása: fun pithagoraszi xs = let fun (* p0 : int list -> (int * int * int) list -> (int * int * int) list p0 zs ss = a zs lista szomszédos elemeiből álló pithagoraszi számhármasok listája az ugyancsak pithagoraszi számhármasokat tartalmazó ss lista elé fűzve *) p0 (x::y::z::zs) ss = p0 (y::z::zs) (if 0