Deklaratív programozás pózárthelyi
                      Budapest, 2004. május 22.
                  ==================================
             SML megoldások, V1.0, dp04s-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 hiba van.  Mik ezek?

   (a) let val x::y::_::zs = [4, 5.0, ord "A"] in zs end
       - int (4) és real (5.0) típusú eleme nem lehet egyszerre egy listának
       - ord argumentuma char (#"A") és nem string ("A") típusú

   (b) List.filter (fn x => x+1) ([1,0,2,1,3,4], rev[1,0,2,1,3,4])
       - filter 1. argumentumának 'a -> bool típusúnak kell lennie 
       - filter 2. argumentumának listának, nem párnak kell lennie

   (c) (33::[], fn z => z) = ([3+3], fn z => 2*z, ())
       - kettes és hármas különböző típusúak, egyenlőségük nem vizsgálható
       - függvények egyenlősége nem vizsgálható

Pontozás (összesen max. 7 pont):
   5.a - 5.c  Helyes válasz 2-2-3 pont.
   Minden hiba megtalálása 1 pontot, az 5.c esetben a 'függvények egyenlősége
   nem vizsgálható' felismerés 2 pontot ér.

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

   (a) val (_::_::z::_) = [hd(explode "Mara")] @ explode "Maros"
          z = #"a" : char

   (b) val z = map (fn (x,y) => x>=y) [(1,2), (1+1,2), (1+2,2)]
          z = [false, true, true] : bool list

   (c) val (_::z) = List.filter (fn (x,y) => x>=y) [(1+2,2), (1+1,2), (1,2)]
       
          z = [(2, 2)] : (int * int) list

Pontozás (összesen max. 7 pont):
   6.a - 6.c  Helyes válasz 2-2-3 pont. Ha nem a legegyszerűbb alakban ír
   fel egy részkifejezést: -1 pont, pl. [(1+1, 2)]-t ír [(2, 2)] helyett.
   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 (x::y::ys) = (x,y) :: f ((x+y):: rev ys) | 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 [1,2,3,4,5]
             x = [~1, ~2, 5, 7] : int list

     (a2) val x = g [~1]
             x = [] : int list

     (a3) val x = g [~1,1]
             x = [~2] : int list

     (a4) val x = g []
             x = [] : int list

   (b) Mutassa be az f([1,2,3,4,5]) függvényalkalmazás egyszerűsítési
       lépéseit, mohó kiértékelést feltételezve!

       f [1,2,3,4,5] --> (1,2) :: f [3,5,4,3] -->
        (1,2) :: (3,5) :: f [8,3,4] -->
        (1,2) :: (3,5) :: (8,3) :: f [11,4] --> 
        (1,2) :: (3,5) :: (8,3) :: (11,4) f [15] --> 
        (1,2) :: (3,5) :: (8,3) :: (11,4) :: [] -->
        (1,2) :: (3,5) :: (8,3) :: [(11,4)] -->
        (1,2) :: (3,5) :: [(8,3), (11,4)] -->
        ... --> [(1,2), (3,5), (8,3), (11,4)]

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.  Nem elvárás az ennyire részletes kifejtés.

8. Egy egészlistában jó helyen lévő elemnek nevezzük azokat az elemeket,
   amelyek értéke megegyezik a listabeli pozíciójukkal.  A pozíciókat 0-tól
   kezdve számozzuk.  Írjon olyan SML-függvényt johelyek néven, amelynek
   eredménye egy egészlista jó helyen lévő elemeinek a listája.
   Segédfüggvényt definiálhat (fejkommenttel!).

   (* johelyek : int list -> int list
      johelyek zs = zs jó helyen lévő elemeinek a listája
   *)

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

   Egy megvalósítása:

   fun johelyek zs =
         let (* jh  : int list * int -> int list
                jh (xs, i) = xs i értékű x elemeinek a listája,
                             ahol i az x elem pozíciója xs-ben
                PRE: i>=0
             *)
   	  fun jh ([], _) = []
   	    | jh (x::xs, i) = if x=i 
   			      then x :: jh(xs, i+1)
   			      else jh(xs, i+1)
         in
   	  jh(zs,0)
   end;

Pontozás (összesen max. 9 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).
   Nem követelmény a hatékony program.