Deklaratív programozás

3. SML kis házi feladat

V1.1 2006. november 22.

A feladat

Tekintsük az alábbi adattípus-deklarációt:

datatype 'a t = B of ('a * 'a t) list | L of 'a

Írjon olyan SML-függvényt foldCnt néven, amely egy 'a t típusú adatstruktúra 'a típusú elemeinek számát, valamint az elemeken elvégzett e egységelemű f művelet eredményét adja vissza az adatstruktúra balról jobbra haladó, preorder sorrendű bejárásával. (Gondoljon arra, hogy nem-asszociatív műveletek esetén a különböző bejárási sorrendek különböző eredményt adnak.)

(* foldCnt : ('a * 'b -> 'b) -> 'b -> 'a t -> ('b * int)
   foldCnt f e t = (s, c), ahol az s a t 'a típusú elemein elvégzett e egységelemű
                    f művelet eredménye a t balról jobbra haladó bejárása mellett,
                    a c pedig ezeknek az elemeknek a száma
*)

Segédfüggvényeket definiálhat.

A programot olyan nagyméretű fákkal is tesztelni fogjuk, amelyekre a nem elég hatékony programok a megadott időlimiten (5s) belül nem futnak le.

A jobbrekurzív függvényekből generált számítási folyamatok kevesebb tárterületet használnak, mint a nemjobbrekurzív függvényekből generáltak, ezért ajánljuk, hogy lehetőleg jobbrekurzív függvényeket írjon, ám ez nem kötelező, a pontozásba nem számít bele.

Példák

foldCnt op+ 0 (L 4) = (4, 1);
foldCnt op+ 0 (B[]) = (0, 0);
foldCnt op+ 0 (B[(3,L 4)]) = (7, 2);
foldCnt op+ 0 (B[(3,L 4),(5,L 6),(7,B[])]) = (25, 5);
foldCnt op- 0 (B[(3,L 4),(5,L 6),(7,B[(1,L 2),(8,L 9),(0,B[])])]) = (~7, 10);
foldCnt op* 0 (B[(3,L 4),(5,L 6)]) = (0, 4);
foldCnt op* 1 (B[(3,L 4),(5,L 6),(7,B[])]) = (2520, 5);
foldCnt op* 1.0 (B[(3.0,L 4.0),(5.0,L 6.0),(7.0,B[])]) = (2520.0, 5);
foldCnt op^ "" (B[("kutya",L"fa")]) = ("fakutya", 2);
foldCnt op^ "" (B[("kutya",L"fa"),("macska",L"farok")]) = ("farokmacskafakutya", 4);
foldCnt op:: [] (B[([3,4],L[4]),([1,2],L[0,1])]) = ([[0, 1], [1, 2], [4], [3, 4]], 4);

Tudnivalók a beadásról

A kis házi feladat beadását, jóllehet nem kötelező, a tárgy minden hallgatójának nagyon ajánljuk.

A programot az Elektronikus Tanársegéd segítségével a weben keresztül lehet beadni, a HF beadás menüpont alatt.
A beadási határidő 2006. november 30., 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.