Deklaratív programozás

2. SML kis házi feladat

2002. november 22.

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

A programot tömörítve, elektronikus levélben kell beküldeni. A beküldéshez egy bash szkriptet kell használni. A szkriptet futtatni a bash dpkhfbe.02a paranccsal lehet (feltéve, hogy ezen a néven mentettük el).

Figyelem!

Letöltéskor ügyeljen arra, hogy a sorvég karakterek un*xos LF-ek maradjanak, az Internet Explorer ui. hajlamos átalakítani őket DOS-os CR-LF-fé.
Letöltés egyenesen az ural2 szerverre:wget '../dp-current/dpkhfbe.02a'
Az ural2 szerveren a/usr/local/binkönyvtárban található a bash program.

A szkript elindulaskor elmagyarázza a teendőket (mi legyen az adott könyvtárban, milyen néven stb.). Mielőtt valaki hibára panaszkodna, győződjön meg róla, hogy a hiba az ural2.hszk.bme.hu szerveren is reprodukálható. (A szkript helyes letöltése után.)

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 feladat

Az alábbi adattípus-deklaráció egy fát definiál:

datatype 'a fa = L | F of 'a * 'a fa * 'a fa

Írjon SML-függvényt utlevel néven, amely egy ilyen struktúrájú fában egy megadott értékhez kiszámítja a gyökértől az érték csomópontbeli előfordulásaihoz vezető utakat! Útnak azt a listát nevezzük, amelynek elemei a bejárás során érintett csomópontbeli értékek, beleértve a gyökeret és a célcsomópontot is.

(* utlevel (fa, ert) = azon utak listája, amelyek fa-ban ert értékű
     csomópontokhoz vezetnek.
   utlevel : ''a fa * ''a -> ''a list list
 *)

Az SML-függvénynek argumentuma egy fából és az ebben keresendő értékből álló pár. Eredménye az összes olyan út listája, amely a gyökérből az érték egy csomópontbeli előfordulásához vezet.

Az eredménylistában minden útnak pontosan egyszer kell szerepelnie. Ha az adott érték egyátalán nem fordul elő a fában, az eredmény az üres lista legyen. A megoldáslistán belüli sorrend tetszőleges.

Ha definiál segédfüggvényeket, azokat feltétlenül lássa el fejkommenttel! Törekedjék arra, hogy a megoldás hatékony legyen!

Fontos! A fenti datatype deklaráció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

- utlevel(L, 1.0);
> val it = [] : real list list

- utlevel(F(1,L,L), 1);
> val it = [[1]] : int list list

- utlevel(F("x", F("y",L,L), F("z",L,L)), "y");
> val it = [["x", "y"]] : string list list

- utlevel(F("x", F("y",L,L), F("z",L,L)), "nincs_benne");
> val it = [] : string list list

- utlevel(F(3, F(2,F(1,L,L),L), F(4,L,F(1,L,L))), 1);
> val it = [[3, 2, 1], [3, 4, 1]] : int list list

- utlevel(F(#"a", F(#"a",L,L), F(#"a",L,L)), #"a");
> val it = [[#"a", #"a"], [#"a", #"a"], [#"a"]] : char list list

Egyéb követelmények és tudnivalók

Ez a második SML kis házi feladat, ezért

 khf-ml2.sml

néven kell beküldeni a megoldást. A beadási határidő december 1., vasárnap 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 max. 100 ponton felül).