Deklaratív programozás

2. SML kis házi feladat

2003. május 6.

A kis házi feladat beadása nem kötelező.

A feladat

Tekintsük egy egészeket tartalmazó bináris fa, valamint egy irányt kifejező adattípus alábbi deklarációját:

datatype itree = L | B of int * itree * itree
datatype dir   = Left | Right

Egy ilyen bináris fában egy csomópont vagy levél (együttesen: faelem) helyének jellemzésére egy ún. kiválasztót használhatunk. A kiválasztó egy olyan lista, amelynek minden eleme a Left és Right konstansok egyike. A kiválasztó által megnevezett faelemet úgy kapjuk, hogy a fa gyökeréből elindulva, a Left konstans esetén a bal részfára, a Right konstans esetén pedig a jobb részfára lépünk. Például a


B(0, B(1, B(3,L,L),
          L),         
     B(9, B(4,L,L),
          B(0,L,L)))

fában a 0 értékű csomópont kiválasztója [], a 4 értékűé [Right,Left].

A feladat az, hogy egy fenti típusú bináris fában keressük meg egy adott egész számnál (határozottan) nagyobb értékeket a kiválasztójukkal együtt, és ezeket gyűjtsük egy listába.

Írjon SML függvényt nagyobbak néven, amely megkeresi egy adott fában egy adott számnál nagyobb értékű csomópontokat, és ezek értékéből és kiválasztójából álló párokat tetszőleges sorrendben listába gyűjtve eredményül visszaadja.

Az elvárt eredmény az alábbi típusdeklarációkkal írható le:

type selector = dir list
type val_sel  = int * selector

A megirandó eljárás fejkommentje:

(* nagyobbak(fa, also): azon (e,k) párokat tetszőleges sorrendben
     tartalmazó lista, amelyekre igaz, hogy a fa fában a k kiválasztó által
     meghatározott faelem egy e értékű csomópont, és e > also.
   nagyobbak : itree * int -> val_sel list
 *)

Ha definiál segédeljárásokat, akkor azokat feltétlenül lássa el fejkommenttel!

Figyelem! A fenti két datatype deklarációt (az itree és a dir adattípusok deklarációját) írja bele a megoldását tartalmazó khf-ml2.sml állományba is, különben a tesztek nem fognak működni!

Példák

- nagyobbak(L, 28);
> val it = [] : (int * dir list) list

- nagyobbak(B(0,B(1,L,L),B(2,L,L)), 1);
> val it = [(2, [Right])] : (int * dir list) list

- nagyobbak(B(0,B(1,B(3,L,L),
                    L),
                B(9,B(4,L,L),
                    B(0,L,L))), 2);
> val it = [(3, [Left, Left]), (4, [Right, Left]), (9, [Right])] :
  (int * dir list) list

Beadás, tudnivalók

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a második SML kis házi feladat, ezért khf-ml2.sml néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetűket.

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Linux operációs rendszer alatt is működniük kell. A beadási határidő május 15., csütörtök 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár (a 100 pontból).