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;