*** MINTA, MEGOLDÁSOKKAL ***

     Programozási paradigmák, nagyzárthelyi, 2000. mm. dd.  hh.mm--hh.mm

                       Standard ML, "?" 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.


1. Mi a típusa az alábbi v1, v2, v3 SML-értékeknek?  Az a)--c) deklarációk
   egymástól függetlenek.

   map : ('a -> 'b) -> 'a list -> 'b list
   o   : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

   a) val v1 = ("123.0", ((~123.0 - 123.0), (ord #"\123"), floor 123.0))
   b) val v2 = let val cs = explode "ejnye" in map ord cs end 
   c) fun v3 h y = h y y
   d) val v4 = fn ls => map (op o) ls


2. Mit ad eredményül az alábbi f függvény, ha a nyolcjegyű számként (EEEEHHNN
   alakban megadott SAJÁT születésnapjára alkalmazza?  (Ha például
   1978. június 15-én született volna, mit adna eredményül f 19780615 ?).
   Válaszát indokolja!

   Int.toString n = az n egész szám füzér alakban
   Int.toString : int -> string

   load "Int";
   fun f n = let val ns = explode(Int.toString n)

                 fun g i d xs =
                      if length xs >= d
                      then  hd xs :: g (i+d) (d+1) (List.drop(xs,d)) 
                      else []

             in 
                  implode(rev(g 1 1 ns))
             end


3. Adott egy nem-negatív egészekből álló lista.  E lista két eleme közeli, ha
   egymás mellett vannak a listában, és a különbségük abszolút értéke kisebb
   2-nél.  Írjon SML-függvényt kozeli néven, amelynek a specifikációja a
   következő:

    (* kozeli : int list -> ((int * int) option, int list)
       kozeli ns = (xy, zs): 
          xy = SOME (x, y), ahol x és y az ns lista következő két közeli eleme,
             vagy
          xy = NONE, ha nincs közeli elem az ns listában,
          zs pedig a lista még feldolgozatlan része
    *)

    Ezután írjon kozeliek néven olyan SML-függvényt, amely egy nem-negatív
    egészekből álló lista összes közeli eleméből képzett párokból álló listát
    ad eredményül!

    (* kozeliek : int list -> int list
       kozeliek ns = a nem-negatív egészekből álló ns lista összes közeli eleméből
                     képzett párok listája
    *)
 
    Példa:
            kozeliek [1, 2, 3, 5, 8, 6, 7, 6] = [(1, 2), (2, 3), (6, 7), (7, 6)]


4. Írjon SML-függvényt szorlista néven, amely egy csupa pozitív egészeket
   tartalmazó lista olyan folytonos részlistáit gyűjti össze egy listába,
   amelyekben az elemek szorzata a megadott számmal egyenlő!

   (* szorlista(ns, s) = a pozitív egészeket tartalmazó ns lista olyan
                         folytonos részlistáinak listája, amelyekben s az
                         elemek szorzata
      szorlista : int list * int -> int list list
   *)

   Példák:
   szorlista([1, 2, 3, 1, 4, 5, 6], 6) =  
                     [[1, 2, 3], [1, 2, 3, 1], [2, 3], [2, 3, 1], [6]];
   szorlista ([1,1,1], 1) = [[1], [1, 1], [1, 1, 1], [1], [1, 1], [1]];
   szorlista ([], 1) = [];


(*  --------  az 1. feladat megoldása -------- *)

val v1 = ("123.0", ((~123.0 - 123.0), (ord #"\123"), floor 123.0))

(*
  val v1 = ("123.0", (~246.0, 123, 123)) : string * (real * int * int)

  "123.0" : string

  (~123.0 - 123.0) = (~246.0 : real)

          ord : char -> int
  (ord #"\123") = (123 : int)

          floor : real -> int
  floor 123.0 = (123 : int)

  ((~123.0 - 123.0), (ord #"\123"), floor 123.0) = 
                                ((~246.0, 123, 123) : real * int * int)
*)



val v2 = let val cs = explode "ejnye" in map ord cs end

(*
  val v2 = [101, 106, 110, 121, 101] : int list

  explode "ejnye" = ([#"e", #"j", #"n", #"y", #"e"] : char list)

  ord : char -> int
  map : ('a -> 'b) -> 'a list -> 'b list

      'a  ==  char,  'b  ==  int
  map ord : char list -> int list

  map ord [#"e", #"j", #"n", #"y", #"e"] = 
                                  ([101, 106, 110, 121, 101] : int list)
*)


fun v3 h y = h y y

(*
  val v3 = fn : ('a -> ('a -> 'b)) -> 'a -> 'b

  y : 'a
  h : 'a -> 'a -> 'b
  v3 : ('a -> 'a -> 'b)    ->    'a    ->   'b
*)


val v4 = fn ls => map (op o) ls

(*
  val v4 = fn : (('a -> 'b) * ('c -> 'a)) list -> ('c -> 'b) list

  map : ('A -> 'B) -> 'A list -> 'B list

  op o : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b  ==
                                    ('a -> 'b) * ('c -> 'a) -> ('c -> 'b)

      'A  ==  ('a -> 'b) * ('c -> 'a),   'B  ==  'c -> 'b

  map (op o) : ('a -> 'b) * ('c -> 'a) list   ->   ('c -> 'b) list

*)


(*  --------  a 2. feladat megoldása -------- *)

load "Int";
fun f n = let val ns = explode(Int.toString n)

              fun g i d xs =
                   if length xs >= d
                   then  hd xs :: g (i+d) (d+1) (List.drop(xs, d)) 
                   else []

          in 
              implode(rev(g 1 1 ns))
          end

f 19780615 = "891"

(*  

  explode(Int.toString 19780615) =
                             [#"1", #"9", #"7", #"8", #"0", #"6", #"1", #"5"]

  g : int -> int -> 'a list -> 'a list

  g 1 1 [#"1", #"9", #"7", #"8", #"0", #"6", #"1", #"5"] = [#"1", #"9", #"8"]

    g 1 1 [#"1", #"9", #"7", #"8", #"0", #"6", #"1", #"5"]
           length xs = 8, d = 1
           drop 1 elemet hagy el

    g 2 2 [#"9", #"7", #"8", #"0", #"6", #"1", #"5"]
           length xs = 7, d = 2
           drop 2 elemet hagy el

    g 4 3 [#"8", #"0", #"6", #"1", #"5"]
           length xs = 5, d = 3
           drop 3 elemet hagy el

    g 7 4 [#"1", #"5"]
           length xs = 2, d = 4 
           
*)


(*  --------  a 3. feladat megoldása -------- *)

  (* kozeli : int list -> ((int * int) option, int list)
     kozeli ys = (xy, zs),ahol 
        xy = SOME (x, y), ahol x és y az ns lista következő két közeli eleme,
           vagy
        xy = NONE, ha nincs közeli elem az ns listában, és
        zs a lista még feldolgozásra váró maradéka
  *)
fun kozeli (x :: (yys as y::ys)) = if abs(x-y) < 2
                                   then (SOME(x, y), yys) 
                                   else kozeli (yys)
  | kozeli ys = (NONE, ys)

  (* kozeliek : int list -> int list
     kozeliek ns = a nem-negatív egészekből álló ns lista összes közeli
                   eleméből képzett párok listája
  *)
fun kozeliek ys = case kozeli ys of
                      (SOME p, zs) => p :: kozeliek zs
                    | (NONE, zs) => []

  (* jobbrekurzív megoldás
  *)
local
    fun k0 (ys, ws) = case kozeli ys of
                          (SOME p, zs) => k0(zs, p::ws)
                        | (NONE, zs) => rev ws
in
    fun kozeliek ys = k0(ys, [])
end

(*  --------  a 4. feladat megoldása -------- *)


(* szorlista(ns, s) = a pozitív egészeket tartalmazó ns lista olyan folytonos
                      részlistáinak listája, amelyekben s az elemek szorzata
   szorlista : int list * int -> int list list
*)
fun szorlista(ns, s) =

      let (* szor0(xs, n, zs, yss) = 
               n az xs elejéről eddig levett elemek szorzata,
               zs az xs elejéről eddig levett x elemek (fordított sorrendű)
                  listája,
               yss az n = s feltételt eddig kielégítő zs részlisták (fordított
                  sorrendű) listája

             szor0 : int list * int * int list * int list list -> int list list
          *)

          fun szor0 (x::xs, n, zs, yss) = 
              let 
                  val xn = x*n
              in 
                  if xn < s  
                      then szor0(xs, xn, x::zs, yss)

                  else if xn = s 
                      then szor0(xs, xn, x::zs, rev(x::zs)::yss)

                  else yss
              end

            | szor0 ([], _, zs, yss) = yss

          (* szor1(ms, yss) = yss az ms adott feltételeket kielegítő eddigi
                              részlistáinak (fordított sorrendű) listája

             szor1 : int list * int list list -> int list list
          *)
          fun szor1 (mms as m::ms, yss) = szor1(ms, szor0(mms, 1, [], yss))

            | szor1 ([], yss) = rev yss

      in
          szor1(ns, [])
      end;

szorlista([1, 2, 3, 1, 4, 5, 6], 6) 
                       =  [[1, 2, 3], [1, 2, 3, 1], [2, 3], [2, 3, 1], [6]];

szorlista([1,1,1], 1) = [[1], [1, 1], [1, 1, 1], [1], [1, 1], [1]];

szorlista([], 1) = [];


(* zh-MINTA vege *)