Deklaratív programozás pótpótzárthelyi
                        Budapest, 2005. május 27.
                        ========================
             SML megoldások, V1.0, dp05s-zh3-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 = real 2), op^("a", "bc") <> #"a", [1*4] = [4*1]]
       - real és int nem hasonlítható össze
       - string és char nem hasonlítható össze

   (b) (ord #"B", 2*4 = 4-2, ~4.0) = (#"B", true, ~3+1)
       - int és char nem hasonlítható össze
       - real és int nem hasonlítható össze

   (c) foldl (fn (a,b) => explode a ^ b) [" "] ["one", "zwei", "drie"]
       - op^ helyett más (pl. op@) operátor kell, mert op^ string és
         nem char list típusú operandusokat vár
       - 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 az s értéke az alábbi, egymástól független deklarációk kiértékelése
   után?

   (a) val (_::s::_::_) = explode "ho" @ rev(tl(explode "tel"))
          s = #"o"

   (b) val (r::s) = List.filter (fn (a,b) => (a>=b))
                                  [(4+0,2*2), (2,2-1), (2-1,2)]
          s = [(2, 1)]

   (c) val s = map List.last 
                     [explode("3c4d"), [#"Q"], rev(explode("let")) @ [#"z"]]
          s = [#"d", #"Q", #"z"]

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::bs, zs) =
                     if b-a=n
                     then f(b::bs, 10*a+b::zs)
                     else f(b::bs, 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(1, [1,2,3,4,5,6])
             x = [12, 23, 34, 45, 56]

     (b) val x = g(2, [1,3,4,6,8,9])
             x = [13, 46, 68]

     (c) val x = g(~3, [1,~2,~5,~8,~5,~2,1])
             x = [8, ~25, ~58]

     (d) val x = g(0, [1,~2,~2,4,4,4,5,6,7])
             x = [~22, 44, 44]

   Fejezze be a fejkommentet!

     (e) (* g (0, xs) = az xs azon elemeinek ...szereseiből álló lista,
                        amelyek ...
         *)
         az xs azon elemeinek 11-szereseiből álló lista, amelyek előtt
         (után) velük azonos értékű elem van az eredeti listában

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

   (* lyukasharmasok : (int * int * int) H -> (int * int * int) list
      lyukasharmasok t = a t-beli lyukasharmasok eredeti sorrendet megőrző
      listája
   *)
   
   Példák:

   lyukasharmasok(B[B[],A(6,4,3),A(~6,0,3)]) = [];
   lyukasharmasok(A(6,0,3)) = [(6,0,3)];
   lyukasharmasok(A(~6,0,~3)) = [(~6,0,~3)];
   lyukasharmasok(B[B[],B[],A(6,0,3)]) = [(6,0,3)];
   lyukasharmasok(B[B[A(1,0,4),A(6,0,9),B[A(1,3,2),B[A(7,0,0)]]],
                    B[],A(~3,0,~9)]) = [(1,0,4), (6,0,9), (~3,0,~9)];

   Néhány megvalósítása:

   fun lyukasharmasok (A(h as (a,b,c))) =
         if a * c > 0 andalso b = 0 then [h] else []
     | lyukasharmasok (B xs) = List.concat(map lyukasharmasok xs);
   
   fun lyukasharmasok (A(h as (a,b,c))) =
         if a * c > 0 andalso b = 0 then [h] else []
     | lyukasharmasok (B zs) =
         foldr (fn (h, ws) => lyukasharmasok h @ ws) [] zs;
   
   fun lyukasharmasok (A(h as (a,b,c))) =
         if a * c > 0 andalso b = 0 then [(a,b,c)] else []
     | lyukasharmasok (B zs) =
         rev(foldl (fn (h, ws) => rev(lyukasharmasok h) @ ws) [] zs);
   
   fun lyukasharmasok (A(h as (a,b,c))) =
         if a * c > 0 andalso b = 0 then [h] else []
     | lyukasharmasok (B[]) = []
     | lyukasharmasok (B(z::zs)) = lyukasharmasok z @ lyukasharmasok(B zs);
   
   fun lyukasharmasok t =
     let
         fun lyukasak (A(h as (a,b,c)), ws) =
               if a * c > 0 andalso b = 0 then h::ws else ws
           | lyukasak (B[], ws) = ws
           | lyukasak (B(z::zs), ws) = lyukasak(B zs, lyukasak(z, ws))
     in
         rev(lyukasak (t, []))
     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.