INF3110/4110
Ukeoppgaver uke 38 (17.-19.9.2003)
Oppgave 1
---------
Les l�sningen p� Dronning-oppgaven, ML-kompendiet s.17-18.
Skriv en kort forklaring p� hvordan denne fungerer, og hva du
eventuelt lurer p�.
Oppgave 2
---------
1. Skriv en rekursiv funksjon i ML, kalt sum, som for gitt n regner ut
summen av alle tall fra 1 til n, f.eks. skal sum(5) gi verdien 15.
2. Hvis du n� skriver uttrykket
sum(5) * (sum(5)-1)
vil sum(5) regnes ut to ganger. Pr�v � skrive uttrykket p� en
annen m�te, ved � bruke let-konstruksjonen, slik at sum(5) regnes
ut bare en gang.
Oppgave 3
---------
Fibonacci-tallene er definert ved hjelp av f�lgende funksjon f:
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2), for n > 2
Vi skal lage en ML-funksjon
fun fib(n:int): int * int = ...
som er slik at funksjonsverdien av fib gir paret best�ende av det
n-te Fibonacci-tallet samt det foreg�ende Fibonacci-tallet.
For eksempel skal kallet fib(2) gi paret (1,1),
fib(3) skal gi (2,1),
fib(4) skal gi (3,2),
fib(5) skal gi (5,3) og
fib(6) skal gi (8,5).
Vi definerer det null-te Fibonacci-tallet som 0, og da skal
fib(1) gi paret (1,0).
Bruk let-konstruksjonen til � lage en effektiv fib funksjon!
Oppgave 4 (Eksamen 1990, del 2a,b,e)
---------
I denne oppgaven skal du definere begrepet mengde med f�lgende
velkjente funksjoner:
has -- som tester om et element er med i en mengde
add -- som legger et element inn i en mengde
union -- som danner unionen av to mengder
inter -- som danner snittet av to mengder
empty -- som danner den tomme mengden
Hvis for eksempel mengden "ansatte" best�r av elementene: "kari",
"anne", "lise", og mengden "stud" best�r av elementene: "lars",
"lise", s� vil unionen av de to mengdene best� av: "kari", "anne",
"lise", "lars", og snittet av dem vil best� av: "lise".
1. Vi definerer mengde-begrepet som en parametrisert abstrakt datatype
p� f�lgende m�te:
signature Set_def =
sig type ''Elem Set
val empty: ''Elem Set
val has : ''Elem Set * ''Elem -> bool
val add : ''Elem Set * ''Elem -> ''Elem Set
val del : ''Elem Set * ''Elem -> ''Elem Set
val union: ''Elem Set * ''Elem Set -> ''Elem Set
val inter: ''Elem Set * ''Elem Set -> ''Elem Set
end;
Mengdene skal representeres ved en liste-aktig datastruktur. Vi
skal anta at for typen ''Elem finnes det en funksjon
fun less(x,y:''Elem): bool = ...
som svarer til � teste at x er mindre enn y. Vi krever at listen
som representerer en mengde alltid er sortert med hensyn p� denne
ordning (med minste element f�rst), og dessuten at hvert element
forekommer h�yst en gang i listen. Funksjonene i grensesnittet skal
v�re slik at denne invarianten vedlikeholdes. Spesielt skal
has-funksjonen utnytte invarianten ved � stoppe leting s� snart som
mulig.
Din oppgave er � lage en implementasjon av dette grensesnittet,
dvs. en ``struktur'' for denne signaturen.
2. Diskuter plassforbruket (lager-behovet) til funksjonene du har
laget.
3. Vi velger � representere en mengde som en funksjon m som er slik at
m(x) er sann hvis x er et element i mengden og gal ellers. Lag en
implementasjon av Set-grensesnittet med en slik
representasjon. Typen ''Elem Set skal n� alts� implementeres slik:
type ''Elem Set = ''Elem -> bool;