Deklaratív programozás pótzárthelyi, 2003. december 11.
           =======================================================
           SML megoldások, 1.1. változat, dp03a-zh2-mlmegol-v1-1.txt
           =========================================================

-------------------
      A csoport
-------------------

5. Mi a g típusa az alábbi, egymástól független deklarációk kiértékelése
   után?

(a) fun g x y = x y :: g x y      g : ('a -> 'b) -> 'a -> 'b list
(b) fun g x y = g y x             g : 'a -> 'a -> 'b
(c) fun g x y = x(g x y)          g : ('a -> 'a) -> 'b -> 'a


6. Mi a k értéke és típusa az alábbi, egymástól független deklarációk
   kiértékelése után?

(a) val (_::_::k) =
      List.filter Char.isDigit (explode "03-dec-11")        k = [#"1", #"1"] : char list
(b) val (_,k) =
      let val (x::y::_) = List.drop(explode "03-dec-11", 3)
      in (x,y)
      end                                                   k = #"e" : char
(c) val k = foldr op* 1 (map (fn x => x mod 2) [1,9,3,5])   k = 1 : int


7. Az ('r, 's) RS adattípust így deklaráljuk:
  
datatype ('r, 's) RS = Q | R of 'r | S of 's | T of ('r * 's)

(a) Írja fel (a1) Q,                      Q : ('r, 's) RS
             (a2) T és                    T : ('r * 's) -> ('r, 's) RS
             (a3) S "er" típusát!         S "er" : ('r, string) RS

Tekintsük az f függvény definícióját:

fun f (S s) = s
  | f (T (r, s)) = s ^ str r
  | f _ = ""

(b) Mi az x értéke az alábbi, egymástól független deklarációk kiértékelése
  után?

(b1) val x = f Q                           x = ""
(b2) val x = f (S "sok")                   x = "sok"
(b3) val x = f (R #"r")                    x = ""
(b4) val x = f (T (#"k", "sok"))           x = "sokk"


8. Írjon olyan SML-függvényt tobbszor néven, amely egy egészeket tartalmazó
   rendezett lista egynél többször előforduló elemeiből álló, az elemek
   eredeti sorrendjét megőrző listát ad eredményül.  Segédfüggvényt
   definiálhat (fejkommenttel!).

(* tobbszor : int list -> int list
   tobbszor xs = az xs egynél többször előforduló elemeinek az eredeti
                 sorrendet megőrző listája
   PRE : xs nagyság szerint rendezve van
*)

Példák:   tobbszor [] = [];
          tobbszor [0,2,3,4] = [];
          tobbszor [0,3,3,5,5,5,6,7,7] = [3,3,5,5,5,7,7];
          tobbszor [1,1,6] = [1,1];

Két megvalósítása:

fun tobbszor (x::y::ys) =
      let (* take : int list -> int list
             take zs = zs csupa x-et tartalmazó prefixuma zs maradéka elé füzve
          *)
          fun take (z::zs) = if x=z then z::take(zs) else tobbszor(z::zs)
            | take [] = []
      in
          if x=y then x::take(y::ys) else tobbszor(y::ys)
      end
  | tobbszor ys = []

fun tobbszor (x::y::ys) =
      if x=y then x::egyformak(y::ys) else tobbszor(y::ys)
  | tobbszor ys = []
(* egyformak : int list -> int list
   egyformak xs = az xs egynél többször előforduló elemeinek az eredeti
                  sorrendet megőrző listája
   PRE : xs nagyság szerint rendezve van; 
         xs feje többszörösen előforduló elem
*)
and egyformak (x::y::ys) =
      if x=y then x::egyformak(y::ys) else x::tobbszor(y::ys)
  | egyformak ys = ys

-------------------
     B csoport
-------------------

5. Mi a g típusa az alábbi, egymástól független deklarációk kiértékelése
   után?

(a) fun g x y = y x :: g x y      g : 'a -> ('a -> 'b) -> 'b list
(b) fun g y x = g x y             g : 'a -> 'a -> 'b
(c) fun g x y = y(g x y)          g : 'a -> ('b -> 'b) -> 'b

6. Mi a k értéke és típusa az alábbi, egymástól független deklarációk
   kiértékelése után?

(a) val (_::_::k) =
      List.filter Char.isLower (explode "03-dec-11")        k = [#"c"] : char list
(b) val (k,_) =
      let val (y::z::_) = List.drop(explode "03-dec-11", 5)
      in (y,z)
      end                                                   k = #"c" : char
(c) val k = foldl op* 1 (map (fn x => x div 2) [7,9,3,5])   k = 24 : int


7. Az ('s, 'r) SR adattípust így deklaráljuk:
  
datatype ('s, 'r) SR = Q | R of 'r | S of 's | T of ('r * 's)

(a) Írja fel (a1) Q,                       Q : ('s, 'r) SR
             (a2) T és                     T : ('r * 's) -> ('s, 'r) SR
             (a3) R 95.3 típusát!          R 95.3 : ('s, real) SR

Tekintsük az f függvény definícióját:

fun f (S s) = s
  | f (T (r, s)) = str r ^ s
  | f _ = ""

(b) Mi az x értéke az alábbi, egymástól független deklarációk kiértékelése
  után?

(b1) val x = f Q                           x = ""
(b2) val x = f (R #"r")                    x = ""
(b3) val x = f (S "sir")                   x = "sir"
(b4) val x = f (T (#"z", "sir"))           x = "zsir"


8. Írjon olyan SML-függvényt egyszer néven, amely egy egészeket tartalmazó,
  nagyság szerint rendezett lista pontosan egyszer előforduló elemeiből
  álló, az elemek eredeti sorrendjét megőrző listát ad eredményül.
  Segédfüggvényt definiálhat (fejkommenttel!).

(* egyszer : int list -> int list
   egyszer xs = az xs pontosan egyszer előforduló elemeinek az eredeti
                sorrendet megőrző listája
   PRE : xs nagyság szerint rendezve van
*)

Példák:   egyszer [] = [];
          egyszer [0,2,3,4] = [0,2,3,4];
          egyszer [0,3,3,5,5,5,6,7,7] = [0,6];
          egyszer [1,1,6] = [6];

Két megvalósítása:

fun egyszer (x::y::ys) =
      let (* drop : int list -> int list
             drop zs = zs y-okból álló prefixuma nélküli része
          *)
          fun drop (z::zs) = if y=z then drop zs else z::zs
            | drop [] = []
      in
          if x=y then egyszer(drop ys) else x::egyszer(y::ys)
      end
  | egyszer ys = ys

fun egyszer [] = []
  | egyszer (x::xs) = 
     let (* esz : int list * int * int * int list -> int list
         *)
         fun esz ([], x, 0, zs) = rev(x::zs)
           | esz ([], _, _, zs) = rev zs
           | esz (y::ys, x, 0, zs) = if x=y then esz(ys, y, 1, zs) else esz(ys, y, 0, x::zs)
           | esz (y::ys, x, b, zs) = if x=y then esz(ys, y, b, zs) else esz(ys, y, 0, zs)
     in
         esz (xs, x, 0, [])
     end