SML-programok

20.1. Monológ.

Oktató: Ígéretem szerint küldöm a legutóbbi konzultáción ismertetett feladatpárt (mu-lista generálása, ill. felismerése). A generálásra egy megoldást leírok, a felismerésre a megoldást meghagyom gyakorló feladatnak.

N-edrendű mu-listának hívjuk azt a listát, amelynek ilyen a szerkezete:

[m, u, m, u, u, m, u, u, u, ..., m, u, ..., u]

Azaz a lista pontosan N db m elemet tartalmaz, és az i-edik m-et pontosan i db u elem követi. Adott a datatype mu = m | u deklaráció.

(1) Írjon olyan SML-függvényt mu néven, amely N-edrendű mu-listát készít! Ügyeljen a hatékonyságra: ne használjon append-et!

(* mu N = a fenti definíció szerinti N-edrendű mu-lista mu : int -> mu list PRE: N >= 0 *)

Példa:

mu 5 = [m,u,m,u,u,m,u,u,u,m,u,u,u,u,m,u,u,u,u,u]

Egy lehetséges megoldás:

local (* gmu i j ls = i-szer egy-egy m és minden m után j db u; j minden m után újraindul i aktuális értékétől *) fun gmu 0 _ ls = ls | gmu i 0 ls = gmu (i-1) (i-1) (m::ls) | gmu i j ls = gmu i (j-1) (u::ls) in fun mu n = gmu n n [] end

(2) Írjon olyan SML-függvényt mulista néven, amely egy listáról eldönti, hogy mu-lista-e, s ha igen, hányadrendű! Ha a lista nem mu-lista, az eredmény -1 legyen. Ügyeljen a hatékonyságra!

(* mulista ls = ha ls mu-lista, akkor a rendszáma, egyébként ~1 mulista : mu list -> int *)

Példák:

mu [m,u,m,u,u,m,u,u,u,m,u,u,u,u,m,u,u,u,u,u] = 5 mu [m,u,m,u,u,m,u] = ~1

Feladat: írja meg a függvényt!

20.2. Kérdés.

Az ETS-ben az SML-programozás szekcióban a platós (SPRG.19) feladatra a következő megoldást adtam:

fun platoseged (x1::x2::xs, (darab, elem)::ys) = if x1 = elem then platoseged(x2::xs, (darab+1, elem)::ys) else if x1 = x2 then platoseged(xs, (2, x1)::(darab, elem)::ys) else platoseged(x2::xs, (darab, elem)::ys) | platoseged (x::xs, (darab, elem)::ys) = if x=elem then (darab+1, elem)::ys else (darab, elem)::ys | platoseged ([], ys) = ys | platoseged (_, _) = [];

fun plato (x::xs) = rev(platoseged(x::xs, [(0, x)])) | plato _ = [];

Lehet, hogy nem szép, de az mosml-be betöltve működik és (szerintem) helyes eredményt ad. Ennek ellenére a gyakorlórendszer szerint a függvény rossz eredményt ad.

Ezek után a kérdésem az lenne, hogy melyik az a teszteset, amelyikre ez nem működik (és amely miatt nem fogadja el tőlem a gyakorlórendszer).

És ha már itt tartunk, megjegyzem, hogy éppen az ilyen esetekben nagyon jól jönne, ha a gyakorlórendszer kiírná, hogy milyen bemenetre nem működött jól a program, mi volt a várt és a kapott eredmény. (A Prolog programozás szekcióban éppen így van, ha jól emlékszem.) Megvalósitható? Szerintem nagyon nagy segítség lenne...

20.2. Válasz.

Oktató: !!! Sajnos, utólag nagyon nehéz megmondani, a tesztesetek már nincsenek meg, vagy ha meg is vannak, nem tudjuk, hol.

20.3. Kérdés.

Az sml-gyakorlórendszer plató feladatára találtunk két megoldást. Az első inkább imperatív észjárással érthető meg, míg a másodiknál ragaszkodtunk ahhoz, hogy a vizsgához hasonlóan csak egy segédfüggvényt használjunk fel. Csak arra lennénk kíváncsiak, hogy mindkét megoldás teljes értékű-e!

Az első megoldás:

(* a lista elején álló azonos elemek számát adja vissza *) fun hanyszor (egy::stb, vmi) = if egy = vmi then 1 + hanyszor(stb, vmi) else 0 | hanyszor ([egy], vmi) = 1 | hanyszor ([], vmi) = 0;

(* levágja a lista elején álló azonos elemeket *) fun csonkol [] = [] | csonkol [egy] = [] | csonkol (egy::ketto::stb) = if egy = ketto then csonkol(ketto::stb) else ketto::stb;

(* maga a plató feladat *) fun plato (egy::ketto::stb) = if egy = ketto then (hanyszor(egy::ketto::stb,egy), egy) :: plato(csonkol(egy::ketto::stb)) else plato(ketto::stb) | plato [egy] = [] | plato [] = [];

A második megoldás:

fun plato (x::y::xs) = let fun cutcount (x::y::xs, akku) = if x = y then cutcount(y::xs, x::akku) else if List.length(x::akku) = 1 then cutcount(y::xs, []) else (List.length(x::akku), x) :: cutcount(y::xs, []) | cutcount ([x], akku)= if List.length(akku) = 0 then [] else [(List.length(x::akku), x)] in if x = y then cutcount(x::y::xs, []) else cutcount(x::y::xs, []) end | plato [x] = [] | plato [] = []

20.3. Válasz.

Oktató: !!! Nem látom, mi a különbség az if-ben a két változat között.

20.4. Kérdés.

Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk a használatára.

(* plato ls = az ls platóinak hosszából és a platókat alkotó elemekből álló párok listája. Platónak hívunk egy olyan, legalább kételemű részlistát, amely csupa azonos elemből áll, és egyik irányba sem terjeszthető ki ezzel az elemmel. plato : ''a list -> (int * ''a) list *)

Példa:

plato(explode "abbbbaacbb") = [(4,#"b"), (2,#"a"), (2,#"b")]

20.4. Válasz.

Hallgató: Az alábbi megoldás nem túl szép, de működik. :) Az lst függvény olyan listát csinál, amelyben minden karakterhez odaírja, hogy 1 van belőle, és párt képez belőle. Példa:

lst [#"a", #"a", #"b"] = [(1, #"a"), (1, #"a"), (1, #"a")]

fun lst [g] = [(1,g)] | lst (f::ff) = (1,f) :: lst ff | lst [] = []

Az add függvény összeadja az azonos csoportokat. Példa:

add [(1, #"a"), (1, #"a"), (1, #"a")] = [(2, #"a"), (1, #"a")]

fun add ((i, f) :: (1, ff) :: fff) = if f = ff then add((i+1, ff) :: fff) else (i, f) :: add ((1, ff) :: fff) | add [(i, g)]) = [(i, g)] | add [] = []

Az irt függvény kiirtja az (1, valami) tagokat a listából. List.filter-rel szebb lenne, de valahogy nem szereti a típusokat, én meg inkább megírtam.

fun irt ((i, f) :: farok) = if i = 1 then irt farok else (i, f) :: irt farok | irt [(i, f)] = if i = 1 then [] else [(i, f)] | irt [] = []

fun plato ls = irt(add(lst ls))

Talán a következő egy picivel szebb megoldás... ;)

local fun platoi(A, N, X::XS) = if A = X then platoi(A, N+1, XS) else if N > 1 then (N, A):: platoi(X, 1, XS) else platoi(X, 1, XS) | platoi (A, N, []) = if N > 1 then [(N, A)] else [] in fun plato (X::XS) = platoi(X, 1, XS) | plato [] = [] end

20.5. Kérdés.

Én ezt nem értem. A feladat ez: Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására. (SPRG.16)

(* komplista : string -> string list komplista s = az s unix-állománynév komponenseinek a #"/" karakterek mentén felbontott listája. Az állománynévben egymás után többször szereplő #"/" jel egyetlen #"/" jelként veendő figyelembe. Az állománynév elején és/vagy végén álló #"/" jel esetén az eredménylista első és/vagy utolsó eleme az üres füzér ("") legyen. *)

Példa:

komplista "dr-1/dr-2/file.ext" = ["dr-1","dr-2","file.ext"];

A megoldásom:

fun komplista s = String.fields (fn x => ord x=ord #"/") s

A mosml szerint jó (kipróbáltam a megadott példát is), a gyakrendszer szerint ,,lesz ez még jobb is''. Mit rontottam el???

Ui. Jó lenne, ha itt is kiírna valamit a program, mint a Prolognál, hogy mi volt hibás.

20.5. Válasz.

Oktató: !!! Vajon a gyakorlórendszerben vagy a megoldásban van a hiba? Lehet hibát keresni, tippelni!

20.6. Monológ.

Hallgató: Igen, mindenki jól látja, csak egy fájlt mellékeltem, mert sajnos ezzel szenvedtem az elmúlt egy órában, ha nem többen... de megszületett! Lehet, hogy nem a legszebb, lehet, hogy nem a legelegánsabb, de az enyém. :)

Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

Példa:

komplista "dr-1/dr-2/file.ext" = ["dr-1","dr-2","file.ext"];

Szenvedésem eredménye:

fun komplista s = if String.sub(s,0) = #"/" andalso String.sub(implode(rev(explode s)),0) = #"/" then "" :: String.tokens (fn c : char => ord c=47) s @ [""] else if String.sub(s,0) = #"/" then "" :: String.tokens (fn c : char => ord c =47) s else if String.sub(implode(rev(explode(s))),0) = #"/" then String.tokens (fn c : char => ord c = 47) s) @ [""] else String.tokens (fn c : char => ord c = 47) s;

20.7. Kérdés.

Kérdésem az sml gyakorlórendszer 23-as feladatával kapcsolatos:

Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* harmKozep ms = az ms elemeinek harmonikus közepe, azaz az ms-beli elemek számának és reciprokösszegének hányadosa harmKozep : int list -> real *)

Példa:

harmKozep [2, 4, 4] = 3.0

Kreáltam is megoldást rá:

fun harmKozep xs = let fun hk ([], k, p) = Real.fromInt k / p | hk (x::xs,k, p) = hk (xs, k+1, p + (1.0 / Real.fromInt x )) in hk(xs, 0, 0.0) end

A Moscow ML-lel okosan működik, csakhogy ehhez be kell tölteni a Real.uo-t, de a load "Real"-t nekem a gyakorlórendszer nem szereti. Biztosan van valami más megoldás, amihez nem kell a Real.fromInt, de nem jövök rá, itt mindenképpen kell a / miatt. :-( Esetleg el lehet kerülni valahogy a load-ot?

20.7. Válasz.

Hallgató: Használd helyette a real függvényt, ahhoz nem kell a load.

Oktató: A load használatáról már sokszor, sokat írtunk a GYIK más fejezeteiben. Nézze meg az SML Basis Library, Az MOSML értelmező használata és a Kisbetű, nagybetű című fejezeteket!

20.8. Kérdés.

(* osszeg(xs, ossz): az xs nemüres számlista elemei közé rakva az eredménylista elemeinek az elemeit ( op+ vagy op-) a kapott kifejezés értéke ossz; az eredménylista elemei eggyel rövidebbek xs-nél. osszeg : int list * int -> (int * int -> int) list list *)

Példa:

osszeg([2,3,4,5,6,7], 13) = [[op+,op+,op+,op+,op-], [op-,op-,op+,op+,op+]

Tudja valaki ennek a megoldását?

20.8. Válasz.

Oktató: Szabad a gazda!

20.9. Kérdés.

Egy kérdésem lenne az inter függvénnyel kapcsolatban: a könyvben és a diákon található változat úgy működik, hogy ha az xs listában egy elem többször szerepel, azt az eredményben is többször fogja szerepeltetni. Ez jó így, vagy feltehetjük, hogy az xs és az ys is halmazok, tehát minden elem eleve csak egyszer szerepel bennük? Vagy inkább a sima felfűzés helyett a newMem-et kellene használni?

fun isMem (y, x::xs) = y = x orelse isMem(y, xs) | isMem (_, []) = false; infix isMem; fun newMem(x, xs) = if x isMem xs then xs else x::xs; fun inter ([], _) = [] | inter (x::xs, ys) = let val zs = inter(xs, ys) in if x isMem ys then x::zs else zs end;

Az én változatom:

fun inter (x::xs, ys) = if x isMem ys then newMem(x, inter(xs, ys)) else inter(xs, ys) | inter ([], _) = [];

20.9. Válasz.

Oktató: Specifikáció kérdése. isMem-mel biztonságos, de drágább.

20.10. Monológ.

Hallgató: Most csatolom az ETS-es SML-függvényeket, láttam, hogy érdekelne vkit. Az egyszerűbbekkel foglalkoztam most egyelőre, de meg kell hagyni, a nehezebbekkel nem is bírtam. ;) Szóval ha vkinek vannak jó megoldásai a nehéz példákra, akkor legyen szíves, küldje el vmelyik listára.

Ui. A Samirello-féle komplista megvan, az így átolvasva is elég nehezen emészthető, ja meg a recOsszeg az oké, azzal még elbírtam. ;)

ETS SML EGYSZERŰ FÜGGVÉNYEK by LiFeX (2004-01-27)

SML - egyszerű függvények írása - 8., közepes feladat (#2990)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* coded t = olyan füzér, amelyben minden t-beli karakter helyén az eggyel nagyobb ascii-kódú karakter van PRE: minden t-beli karakter kódja < 255 coded : string -> string *)
Példa:

coded "van" = "wbo";
Megoldás:

fun coded t = let fun b (x::xs) = chr ((ord x) +1)::b xs | b _ = [] in implode(b (explode t)) end;
SML - egyszerű függvények írása - 2., könnyű feladat (#2984)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* len xs = az xs elemeinek a száma len : 'a list -> int *)
Példa:

len ["a","ab","abc"] = 3;
Megoldás:

fun len [] = 0 | len (x::xs) = 1 + len xs;
SML - egyszerű függvények írása - 4., könnyű feladat (#2986)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* inc xs = olyan lista, amelyben minden xs-beli x elem helyén x+1 van PRE: xs minden eleme < Int.maxInt inc : int list -> int list *)
Példa:

inc [4,3,8] = [5,4,9];
Megoldás:

fun inc [] = [] | inc (x::xs) = (x+1)::inc xs;
SML - egyszerű függvények írása - 1., könnyű feladat (#2983)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* ones ns = az 1 értékek száma ns-ben ones : int list -> int *)
Példák:

ones [5,8,7] = 0; ones [1,4,1,6,1,8,1] = 4;
Megoldás:

fun ones [] = 0 | ones (x::xs) = if (x = 1) then 1 + ones xs else ones xs;
SML - egyszerű függvények írása - 12., közepes feladat (#2994)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* sumli (ms, ns) = az ms és ns elemeinek páronkénti összeadásával előálló lista (a rövidebb listát képzeletben annyi 0-val egészítsd ki, hogy a két lista hossza azonos legyen) sumli : int list * int list -> int list *)
Példa:

sumli([1,2,3], [4,5,6,9,7]) = [5,7,9,9,7];
Megoldás:

fun sumli ([],[]) = [] | sumli ((x::xs),(y::ys)) = (x+y)::sumli(xs,ys) | sumli ((x::xs),[]) = x::sumli(xs,[]) | sumli ([],(y::ys)) = y::sumli([],ys);
SML - egyszerű függvények írása - 3., könnyű feladat (#2985)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* longer (xs, ys) = igaz, ha xs hosszabb ys-nál longer : 'a list * 'b list -> bool *)
Példa:

longer([1,2,3], [true, false]) = true;
Megoldás:

fun longer ([],[]) = false | longer ((x::xs),[]) = true | longer ([],(y::ys)) = false | longer ((x::xs),(y::ys)) = longer (xs,ys);
SML - egyszerű függvények írása - 5., könnyű feladat (#2987)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* fib n = az n-edik Fibonacci-szám fib : int -> int *)
Példa:

fib 0 = 0; fib 1 = 1; fib 10 = 55; fib 20 = 6765;
Megoldás:

fun fib 0 = 0 | fib 1 = 1 | fib n = fib(n-1) + fib(n-2);
SML - egyszerű függvények írása - 15., nehéz feladat (#2997)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* recOsszeg n = az 1 és n közötti egészek reciprokának az összege PRE: 0 < n recOsszeg : int -> real *)
Példa:

recOsszeg 3 = 1.83333333333
Megoldás:

fun recOsszeg 1 = 1.0 | recOsszeg n = (1.0/real(n)) + recOsszeg(n-1)
SML - egyszerű függvények írása - 9., közepes feladat (#2991)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* condensed t = a t karaktereit a formázó karakterek kivételével az eredeti sorrendben tartalmazó füzér condensed : string -> string *)
Példa:

condensed " \t Moha \r\t\n med\r \n" = "Mohamed";
Megoldás:

fun condensed t = let fun con [] = [] | con ls = List.filter Char.isAlpha ls in implode(con (explode t)) end;
SML - egyszerű függvények írása - 11., közepes feladat (#2993)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* harmKozep ms = az ms elemeinek harmonikus közepe, azaz az ms-beli elemek számának és reciprokösszegének a hányadosa harmKozep : int list -> real *)
Példa:

harmKozep [2, 4, 4] = 3.0;
Megoldás:

fun harmKozep ms = let val sz = real(length ms) fun recs [] = 0.0 | recs (x::xs) = (1.0/real(x)) + recs xs in sz/(recs ms) end;
SML - egyszerű függvények írása - 6., könnyű feladat (#2988)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* fakt n = n! PRE: n >= 0 fakt : int -> int *)
Példa:

fakt 5 = 120;
Megoldás:

fun fakt 1 = 1 | fakt n = n * fakt(n-1);
SML - egyszerű függvények írása - 7., könnyű feladat (#2989)
Írj az alábbi fejkommentet kielégítő SML-függvényt! Segítségül példát is mutatunk az alkalmazására.

(* sumr rs = az rs elemeinek az összege sumr : real list -> real *)
Példa:

sumr [1.2,3.5,10.0] = 14.7
Megoldás:

fun sumr [] = 0.0 | sumr (n::ns) = n + sumr(ns)

Deklaratív programozás - FP-GYIK
2005. március 1.