Programozási paradigmák, nagyzárthelyi, 2000. március 27.  17.15--18.45

			  Standard ML, "A" csoport (30 pont)

Az SML-függvény megírását kérő feladatokban a jegyzetben szereplő összes SML-függvény
(akár beépített, akár a jegyzetben definiált) szabadon használható.  Ha segédfüggvényt
definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja a
függvény típusát és írja le a függvény argumentumai és az eredménye közötti
kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot
kaphat.  Törekedjék egyszerű, tömör és hatékony programozásra; használjon
jobbrekurziót, kerülje a felesleges hívásokat.


5. Mi a típusa az alábbi v1, v2, v3, v4 SML-értékeknek?  Az a)--d) deklarációk
   egymástól függetlenek.
                                                                              (5 pont)
   map          : ('a -> 'b) -> 'a list -> 'b list
   List.filter  : ('a -> bool) -> 'a list -> 'a list
   Char.isSpace : char -> bool

   a) val v1 = (3-4, op^("al","ma"), [#"Q"])
   b) val v2 = let val xs = List.filter Char.isSpace [#"a", #"b", #"c"] in xs end
   c) fun v3 (h, y : real) = h(y + y)
   d) fun v4 ls = map (fn (g, x) => g x) ls

   Megoldás:

   a) v1 : int * string * char list
   b) v2 : char list
   c) v3 : (real -> 'a) * real -> 'a 
   d) v4 : (('a -> 'b) * 'a) list -> 'b list


6. Mit ad eredményül az alábbi f függvény, ha a hatjegyű számként (ééhhnn alakban)
   megadott születésnapjára alkalmazza?  Válaszát indokolja!
                                                                              (5 pont)
   ord          : char -> int
   chr      	: int -> char
   implode  	: char list -> string
   explode  	: string -> char list
   List.concat  : 'a list list -> 'a list

   local 
	 fun f0 x = [x, chr(ord #"9" - ord x + ord #"0")]
   in	  
         fun f k = implode (List.concat (map f0 (explode k)))
   end

   Megoldás:

   f "800229" = "810909272790"
   f0 : char -> char list
   f0 az x argumentumra alkalmazva olyan kételemű listát ad eredményül, amelynek az
      első eleme x, a második eleme pedig az a számjegy karakterként ábrázolva,
      amelyet úgy kapunk, hogy 9-ből kivonjuk az x számjegy decimális értékét.
   f : string -> string
   f az argumentumként kapott füzér összes karakterére alkalmazza az f0 függvényt,
     majd ennek eredményét (karakterek listájának listáját) egyetlen karakterlistává,
     majd füzérré alakítja.


7. Írjon olyan SML-függvényt kezdobetuk néven, amely egy mondat szavainak a
   kezdőbetűiből álló szót ad eredményül!  A mondat szavak sorozata, a szavak között
   pontosan egy szóköz van. Egy szó betűk sorozata.  A Char.isSpace tesztelő függvény
   a szóköz jellegű karakterek felismerésére használható; char -> bool típusú.  A
   mondatban csak szóközök és betűk fordulhatnak elő, ezért minden nem szóköz
   karakterről feltételezheti, hogy az betű.
                                                                              (9 pont)
    (* kezdobetuk t = a t-beli szavak kezdőbetűiből összeállított szó
       kezdobetuk : string -> string
    *)

    Példa:
            kezdobetuk "Barátom régimódi úr nagyon óvatos" = "Brúnó"

   Megoldások:

      (* ---------- magasabb rendű és könyvtári függvényekkel ------------- *)
   fun kezdobetuk t =
   	 implode(map (fn s => String.sub(s, 0)) (String.tokens Char.isSpace t))
   
      (* ------------ gyalogos megoldás ------------- *)
   fun kezdobetuk t =
   	 let (* kb ts = a ts karakterlista szóközt követő betűinek listája
   		kb : char list -> char list
   	     *)
   	     fun kb (#" " :: (ccs as #" " :: cs)) = kb ccs
   	       | kb (#" " :: c :: cs)             = c :: kb cs
   	       | kb (_ :: cs)                     = kb cs
   	       | kb []                            = []
   	 in
   	     implode(kb(explode(" " ^ t)))
   	 end
   

8. Írjon olyan SML-függvényt emelkedok néven, amely megszámlálja, hogy egy
   egészlistában hány emelkedő van!  Emelkedőnek nevezzük az olyan, legalább kételemű,
   maximális hosszúságú (azaz se balra, se jobbra ki nem terjeszthető) számsorozatot,
   amelyben az elemek értéke balról jobbra haladva szigorúan monoton nő.
                                                                             (11 pont)
    (* emelkedok ns = az ns listában az emelkedők száma
       emelkedok : int list -> int
    *)

    Példák:
            emelkedok [1, 2, 3, 5, 8, 7, 6, 7] = 2
            emelkedok [5, 5] = 0

   Megoldás:

   local
       (* e0 (ns, k) = az ns-beli lejtő végén a emelkedőszámot (k) megnövelve áttér e1-re
   		       az utolsó lejtő végén az emelkedők számával tér vissza
   	  e0 : int list * int -> int
       *)
       fun e0 (m::n::ns, k) = if m >= n then e0(n::ns, k) else e1(n::ns, k+1)
   	 | e0 (_, k) = k
       (* e1 (ns, k) = az ns-beli emelkedő végén áttér e0-ra
   		       az utolsó emelkedő végén az emelkedők számával tér vissza
   	  e1 : int list * int -> int
       *)
       and e1 (m::n::ns, k) = if m < n then e1(n::ns, k) else e0(n::ns, k)
   	 | e1 (_, k) = k
   in
       fun emelkedok ns = e0(ns, 0)
   end


----------------------------------------------------------------------------------------------

       Programozási paradigmák, nagyzárthelyi, 2000. március 27.  17.15--18.45

			  Standard ML, "B" csoport (30 pont)

Az SML-függvény megírását kérő feladatokban a jegyzetben szereplő összes SML-függvény
(akár beépített, akár a jegyzetben definiált) szabadon használható.  Ha segédfüggvényt
definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja a
függvény típusát és írja le a függvény argumentumai és az eredménye közötti
kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot
kaphat.  Törekedjék egyszerű, tömör és hatékony programozásra; használjon
jobbrekurziót, kerülje a felesleges hívásokat.


5. Mi a típusa az alábbi v1, v2, v3, v4 SML-értékeknek?  Az a)--d) deklarációk
   egymástól függetlenek.
                                                                              (5 pont)
   map          : ('a -> 'b) -> 'a list -> 'b list
   List.filter  : ('a -> bool) -> 'a list -> 'a list
   Char.isAlpha : char -> bool

   a) val v1 = ("al" ^ "ma", op-(3, 4), [[true]])
   b) val v2 = let val xs = List.filter Char.isAlpha [#"1", #"2", #"3"] in xs end
   c) fun v3 (x, g) = g(x - x : int)
   d) fun v4 zs = map (fn (g, x) => (x, g)) zs

   Megoldás:

6. Mit ad eredményül az alábbi f függvény, ha a hatjegyű számként (ééhhnn alakban)
   megadott születésnapjára alkalmazza?  Válaszát indokolja!
                                                                              (5 pont)
   ord            : char -> int
   chr      	  : int -> char
   implode  	  : char list -> string
   explode  	  : string -> char list
   String.concat  : string list -> string

   local
	 fun f0 x = implode [x, chr(ord x - ord #"0" + ord #"A")]
   in	  
         fun f k = String.concat (map f0 (explode k))
   end

   Megoldás:

   f "800229" = "8I0A0A2C2C9J"
   f0 : char -> string

   f0 az x argumentumra alkalmazva olyan kétkarakteres füzért ad eredményül, amelynek
      az első karaktere x, a második karaktere pedig az angol ábécéből vett, az x
      számjegy decimális értékének megfelelő sorszámú nagybetű. Az A betű indexe 0.
   f : string -> string
   f az argumentumként kapott füzér összes karakterére alkalmazza az f0 függvényt,
     majd ennek eredményét (füzérek listáját) egyetlen füzérré alakítja.


7. Írjon olyan SML-függvényt utsobetuk néven, amely egy mondat szavainak legutolsó
   betűiből álló szót ad eredményül!  A mondat szavak sorozata, a szavak között
   pontosan egy szóköz van. Egy szó betűk sorozata.  A Char.isSpace tesztelő függvény
   a szóköz jellegű karakterek felismerésére használható; char -> bool típusú.  A
   mondatban csak szóközök és betűk fordulhatnak elő, ezért minden nem szóköz
   karakterről feltételezheti, hogy az betű.
                                                                                (9 pont)
    (* utsobetuk t = a t füzérbeli szavak utolsó betűiből összeállított szó
       utsobetuk : string -> string
    *)

    Példa:
            utsobetuk "B bankár szomorú,    nagyon    megható!!!  " = "Brúnó"

   Megoldás:

      (* ----------- magasabb rendű és könyvtári függvényekkel ----------- *)
   fun utsobetuk t = 
   	  implode(map (fn s => String.sub(s, size s - 1)) (String.tokens Char.isSpace t))
   
      (* ------------- gyalogos megoldás -------------- *)
   fun utsobetuk t =
   	 let (* ub ts = a ts karakterlista szóköz előtti betűinek listája
   		ub : char list -> char list
   	     *)
   	     fun ub (#" " :: (ccs as #" " :: cs)) = ub ccs
   	       | ub (c :: #" " :: cs)             = c :: ub cs
   	       | ub (_ :: cs)                     = ub cs
   	       | ub []                            = []
   	 in
   	     implode(ub(explode(t ^ " ")))
   	 end
   

8. Írjon olyan SML-függvényt lejtok néven, amely megszámlálja, hogy egy egészlistában
   hány lejtő van!  Lejtőnek nevezzük az olyan, legalább kételemű, maximális
   hosszúságú (azaz se balra, se jobbra ki nem terjeszthető) számsorozatot, amelyben
   az elemek értéke balról jobbra haladva (nem szigorúan) monoton csökken.
                                                                             (11 pont)
    (* lejtok ns = az ns listában a lejtők száma
       lejtok : int list -> int
    *)

    Példák:
            lejtok [1, 2, 8, 5, 3, 7, 6, 7] = 2
            lejtok [5, 5] = 1

   Megoldás:

   local
       (* l0 (ns, k) = az ns-beli emelkedő végén a lejtőszámot (k) megnövelve áttér l1-re
   		       az utolsó emelkedő végén a lejtők számával tér vissza
   	  l0 : int list * int -> int
       *)
       fun l0 (m::n::ns, k) = if m < n then l0(n::ns, k) else l1(n::ns, k+1)
   	 | l0 (_, k) = k
       (* l1 (ns, k) = az ns-beli lejtő végén áttér l0-ra
   		       az utolsó lejtő végén a lejtők számával tér vissza
   	  l1 : int list * int -> int
       *)
       and l1 (m::n::ns, k) = if m >= n then l1(n::ns, k) else l0(n::ns, k)
   	 | l1 (_, k) = k
   in
       fun lejtok ns = l0(ns, 0)
   end