Deklaratív programozás nagyzárthelyi, 2003. december 4.
           =======================================================
           SML megoldások, 1.2. változat, dp03a-zh1-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 = y :: (x y)        g : ('a -> 'a list) -> 'a -> 'a list
(c) fun g x y = x :: (g x y)      g : 'a -> 'b -> 'a list


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-nov-04")    k = [#"0", #"4"] : char list
(b) val (_,k,_) =
      let val (x::y::z::_) =
            List.drop(explode "03-nov-04", 3)
      in (x,y,z)
      end                                               k = #"o" : char
(c) val k =
      foldr op+ 100 (map (fn x => x mod 3) [1,9,4,5])   k = 104 : int


7. A ('p, 'q) PQ adattípust így deklaráljuk:
  
datatype ('p, 'q) PQ = S | P of 'p | Q of 'q | PQ of ('p * 'q)

(a) Írja fel (a1) S,                       S : ('p, 'q) PQ
             (a2) PQ és                    PQ : ('p * 'q) -> ('p, 'q) PQ
             (a3) P "alma" típusát!        P "alma" : (string, 'a) PQ

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

fun f (P p)       = p
  | f (PQ (p, q)) = p ^ str q
  | 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 S                           x = ""
(b2) val x = f (P "piros")                 x = "piros"
(b3) val x = f (Q #"q")                    x = ""
(b4) val x = f (PQ ("piros", #"q"))        x = "pirosq"


8. Nevezzünk rámpának egy balról jobbra haladva egyesével növekvő, legalább
   kételemű számsorozatot.  Írjon olyan SML-függvényt \ntt{ rampa } néven,
   amely egy nemnegatív egészekből álló listában található rámpák számát
   adja eredményül.  Segédfüggvényt definiálhat (fejkommenttel!).

(* rampa : int list -> int
   rampa xs = a rámpák száma xs-ben
*)

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

Egy megvalósítása:

fun rampa xs =
      (* rampa0 : int list * bool * int -> int
         rampa0 (xs, r, i) = i + az új rámpák száma xs-ben
                             (ha r = true, akkor nem új a rámpa)
      *)
      let fun rampa0 (x::y::ys, true, i) =
                rampa0(y::ys, x+1=y, i)
	    | rampa0 (x::y::ys, false, i) =
                rampa0(y::ys, x+1=y, i + (if x+1=y then 1 else 0))
	    | rampa0 (_, _, i) = i
      in
	  rampa0(xs, false, 0)
      end


-------------------
     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 x y = y :: (x y)        g : ('a -> 'a list) -> 'a -> 'a list
(c) fun g x y = y :: (g x y)      g : 'a -> 'b -> 'b list

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-nov-04")    k = [#"v"] : char list
(b) val (_,_,k) =
      let val (x::y::z::_) =
            List.drop(explode "03-nov-04", 6)
      in (x,y,z)
      end                                               k = [#"v"] : char list
(c) val k =
      foldl op* 10 (map (fn x => x div 3) [8,9,6])      k = 120 : int


7. A ('m, 'w) MW adattípust így deklaráljuk:
  
datatype ('m, 'w) MW = N | M of 'm | W of 'w | WM of ('w * 'm)

(a) Írja fel (a1) N,                       N : ('m, 'w) MW
             (a2) WM és                    WM : ('w * 'm) -> ('m, 'w) MW
             (a3) W 95.3 típusát!          W 95.3 : ('a, real) MW

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

fun f (W w)       = w
  | f (WM (w, m)) = str m ^ w
  | 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 N                           x = ""
(b2) val x = f (M #"m")                    x = ""
(b3) val x = f (W "wuu")                   x = "wuu"
(b4) val x = f (WM ("wuu", #"m"))          x = "mwuu"


8. Nevezzünk lépcsőnek egy 0-val kezdődő, balról jobbra haladva állandó
   különbséggel növekvő, legalább kételemű számsorozatot.  Írjon olyan
   SML-függvényt \ntt{ lepcso } néven, amely egy nemnegatív egészekből álló
   listában található lépcsők számát adja eredményül.  Segédfüggvényt
   definiálhat (fejkommenttel!).

(* lepcso : int list -> int
   lepcso xs = a lépcsők száma xs-ben
*)

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

Egy megvalósítása (a szükségesnél általánosabb, mert nem használja ki, hogy
lépcső minden olyan sorozat, amely 0, 0+d váltással indul):

fun lepcso xs =
      let fun lcs (0::0::ys, _, i) = lcs(0::ys, 0, i)
	    | lcs (0::y::ys, _, i) = lcs(y::ys, y, i+1)
	    | lcs (x::y::ys, 0, i) = lcs(y::ys, 0, i)
	    | lcs (x::y::ys, d, i) =
                if x+d = y
                then lcs(y::ys, d, i)
                else lcs(y::ys, 0, i)
	    | lcs (_, _, i) = i
      in
	  lcs(xs, 0, 0)
      end

Ez a megoldás kihasználja, hogy a lépcső  0, 0+d váltással indul.

fun lepcso [] = 0
  | lepcso [0] = 0      (* vagy lepcso [_] = 0 *)
  | lepcso (0::0::ys) = lepcso(0::ys)
  | lepcso (0::ys) = lepcso ys + 1
  | lepcso (_::ys) = lepcso ys