Nagyzéhá, pótzéhá, pótpótzéhá

23.1. Monológ.

Oktató: A tárgy funkcionális programozásról szóló részéből a nagyzéhá előtti SML-előadásokon elhangzottakat kell tudni a nagyzéhára, pótzéhára, pótpótzéhára egyaránt. Az előadásdiák letölthetők a tárgy honlapjáról.

A diákon szereplő belső és könyvtári függvények, köztük az egyszerű ki- és beviteli, valamint konverziós függvények ismerete mellett elvárjuk a General, Int, Real, Math, Char, String és List könyvtárbeli típusok, függvények és más értékek használatának ismeretét.

2004-től kezdve nem adunk fel típusegyenleteket, típuslevezetési feladatokat a zéhán. A négy SML feladat pontozása rendszerint 7-7-7-9, az első két feladat általában három-három részfeladatból áll, többnyire 2-2-3 a részpontozásuk.

Az első feladatcsoportban szintaktikailag helyes, de szemantikai szempontból hibás SML-kifejezésekről kell megmondani, hogy miért hibásak.

A második feladatcsoportban helyes SML-kifejezések értékét kell felírni a lehető legegyszerűbb alakban.

A harmadik feladatban néhány más függvényből (pl. lambda-jelöléssel megadott vagy magasabb rendű könyvtári függvényekből) felépülő SML-függvényt kell alkalmazni különféle értékekre, és meg kell adni az alkalmazás eredményét. Kérdés lehet, hogy mutassa be a függvény egyszerűsítési lépéseit mohó (applikatív sorrendű) vagy lusta (normál sorrendű) kiértékelés esetén.

Végül a negyedik feladatban SML-függvényt kell írni valamilyen lista bizonyos tulajdonságú elemeinek az összeadására, összeszorzására, kigyűjtésére stb.

Érdemes megnézni a korábbi feladatsorokat: a típusegyenletek kivételével a másik három fajta hasonló marad. Néhány példa, a zéhában hasonló jellegű, de ezeknél azért nehezebb feladatok várhatók.

1. fajta. Miért hibás (egyetlen hiba van a kifejezésben)?

(8, 3=4) = (ord #"x", Char.isSpace)

2. fajta. Mi xs értéke egyszerűsítés után?

val (x::xs) = hd [[2*5, 7 div 3], [round 8.0], []]

3. fajta. Adott az f függvény:

fun f g [] = [] | f g (x::xs) = map g x :: f g xs

Mi lesz az

f chr [[2*5, 7 div 3], [round 8.0], []]

függvényalkalmazás eredménye? Mutassa be az egyszerűsítési (behelyettesítési) lépéseket mohó kiértékelést feltételezve!

4. fajta. Növekvő futamnak nevezzük egy listában a lehető leghosszabb, azaz semelyik irányban nem kiterjeszthető, monoton növekvő részsorozatokat. Írjon futamSzam néven olyan SML függvényt, amely egy egészlista növekvő futamainak számát adja eredményül. Példa:

futamSzam [1,4,7,3,5,11,19,8,6,7,8] = 4

23.2. Kérdés.

Tudna vki az előző feladatokra egy-egy példát írni? Előzo zéhákat nem is érdemes tanulmányozni SML-ből ezek szerint?

23.2. Válasz.

Hallgató: Én csinálgattam valamit, remélem, még nem túl későn. Nem garantálom, hogy mind jó, de talán segít. Amit tudtam, ellenőriztem.

1. fajta. Miért hibás (egyetlen hiba van a kifejezésben)?

(8, 3 = 4) = (ord #"x", Char.isSpace)

A 3 = 4 típusa bool, a Char.isSpace típusa char -> bool: különböző típusú értékek nem hasoníthatók össze, egyenlőségük nem vizsgálható.

2. fajta. Mi az xs értéke egyszerűsítés után:

val (x::xs) = hd [[2*5, 7 div 3], [round 8.0], []]

Kezdjük a jobb oldal egyszerűsítésével:

hd [[10, 2], [8], []]

tehát (x::xs) = [10, 2], ugyanis a hd függvény a lista fejét veszi, amely itt [10, 2] tehát xs = [2].

3. fajta. Adott az f függvény:

fun f g [] = [] | f g (x::xs) = map g x :: f g xs

Mi lesz az

f chr [[2*5, 7 div 3], [round 8.0], []]

függvényalkalmazás eredménye? Mutassa be az egyszerűsítési (behelyettesítési) lépéseket mohó kiértékelést feltételezve!

A chr függvénynek egy szám az argumentuma, az eredménye pedig az a karakter, amelynek az adott szám az ascii-kódja. Pl. chr 120 = #"x". Az f függvény üres listára üres listát ad eredményül. Ha a lista nem üres, akkor az x lista összes elemére kiértékeli a g függvényt (ami itt nem más, mint a chr függvény), majd ezt az így keletkezett listát egy új lista elejére fűzi, és végül a maradék listára is meghívja ugyanezt.

Tehát a mohó kiértékelés miatt először beír mindent, amit lehet:

f chr [[10, 2], [8], []]

Utána először végigmegy a [10, 2] listán, és az elemeit átalakítja karakterekké. Az ascii-kódtáblából kiolvasható, hogy chr 10 = #"\n", chr 2 = #"\^B", chr 8 = #"\b". Tehát kapok egy olyan listát, hogy [#"\n", #"\^B"]. Ezután jön a [8] lista, ebből [#"\b"] lesz. Végül []-ből [] lesz. Tehát egy ilyen listát kapok: [[#"\n", #"\^B"], [#"\b"], []].

4. fajta. Növekvő futamnak nevezzük egy listában a lehető leghosszabb, azaz semelyik irányban nem kiterjeszthető, monoton növekvő részsorozatokat. Írjon futamSzam néven olyan SML függvényt, amely egészlista növekvő futamainak számát adja eredményül.

Példa: futamSzam [1,4,7,3,5,11,19,8,6,7,8] = 4

A megoldásom majdnem jó! Egy hiba van vele: a futamSzam [0] meghívásra 2-t ad ki 1 helyett.

fun futamSzam [] = 0
  | futamSzam (x::xs) =
      let
         fun futam ([], Elozo, X) = X+1
           | futam ((x::xs), Elozo, X) =
                if x > Elozo
                then futam(xs, x, X)
                else futam(xs, x, X+1)
      in
         futam((x::xs), 0, 0)
      end

A kérdező folytatja: Ez a hiba könnyen kijavítható: | futamSzam [n] = 1 berakásával, viszont pl. futamSzam [1,1,1]-re 3-at ad, ami annyira nem jó...

Ki tudná kijavítani???