INF3110/4110
Ukeoppgaver uke 37 (10.-12.9.2003)
Oppgave 1
---------
Skriv en ML-funksjon
fun reverser (l: 'a list) : 'a list = ...
som reverserer rekkef?lgen til elementene i en liste.
Eks. reverser(["A", "B", "C"]) gir ["C", "B", "A"]
og reverser([1, 2, 3, 4]) gir [4, 3, 2, 1]
Oppgave 2
---------
Skriv en ML-funksjon
fun append (l1: 'a list, l2: 'a list) : 'a list = ...
som setter sammen to lister til en.
Eks. append(["A", "B", "C"], ["D", "E", "F"])
gir ["A", "B", "C", "D", "E", "F"]
og append([1,2], [3,4]) gir [1,2,3,4]
Oppgave 3
---------
Gitt ML-typen
datatype Data = tall of int | no;
som vi kan tenke oss er nyttig for ? representere m?lingsresultater
som av og til kan sl? feil (representert ved konstantverdien no) og
ellers gi et tall: tall(5) og no er eksempler p? verdier av denne
typen. Vi kan n? definere en fordoblings-funksjon slik:
fun dobbel(x:Data):Data =
case x of no => no
| tall(i) => tall(i+i);
1. Definer en mindre-enn relasjon
fun mindre(x:Data, y:Data):bool = ...
som er slik at konstanten no er mindre enn alle andre verdier, og
slik at tall(5) er mindre enn tall(6). F.eks. skal mindre(tall(5),
no) gi false, mens mindre(no, tall(5)) skal gi true.
2. Definer en funksjon
fun max(x:Data, y:Data):Data = ...
som gir det st?rste av de to argumentene som
funksjonsverdi. F. eks. skal max(no, tall(5)) gi tall(5).
3. Du skal lage en funksjon
snitt2(x:Data, y:Data):Data = ...
for ? finne gjennomsnittet av to m?linger, slik at snitt2(no,no)
gir no, og snitt2(no,tall(5)) gir tall(5) og
snitt2(tall(8),tall(5)) gir tall(6). Bruk heltallsdivisjon, div,
selv om dette gir et tiln?rmet gjennomsnitt.
4. Gitt typen
type Dataliste = Data list;
Lag en funksjon
fun snitt(l:Dataliste):Data =
case l of [] => no
| x::r => ... ;
som regner et slags gjennomsnitt av alle m?lingene i listen l, slik
at snitt([]) gir no, og snitt([no,tall(5)]) gir tall(5) og
snitt([tall(8),tall(5), tall(7)]) gir tall(7). Bruk
heltallsdivisjon, div, og bruk funksjonen snitt2, selv om dette
ikke gir det mest eksakte gjennomsnitt.
5. Gir snitt([tall(7),tall(8),tall(5)]) det samme resultatet som
snitt([tall(8),tall(5), tall(7)])? Forklar hvorfor/hvorfor ikke?
Oppgave 4
---------
Med et bin?rt s?ketre menes det her et bin?rt tre som er slik at for
node x er alle verdier i venstre subtre til x mindre enn verdien i x
og alle verdier i h?yre subtre til x er st?rre enn verdien i x. I ML
kan slike tr?r defineres ved:
datatype BTre = Tom | Node of BTre * int * BTre;
Eksempel:
val testtre = (* bin?rt s?ketre *)
Node(Node(Tom,1,Tom),2,Node(Node(Tom,3,Tom),4,Node(Tom,5,Tom)));
3 5
\ /
1 4
\ /
2
1. Lag en funksjon
fun Str(t: BTre): int = ...
som finner antall noder i det bin?re treet t.
2. Lag en funksjon som gitt et bin?rtre t: Btre gir som verdi en liste
l: int list som tilsvarer de verdiene vi ``ser'' ved en
infiks-traversering av det bin?re treet t.
3. Som over, men listen skal n? tilsvare de verdiene vi ``ser'' ved en
postfiks-traversering av treet.
4. Som over, men listen skal n? tilsvare de verdiene vi ``ser'' ved en
prefiks-traversering av treet.
5. Lag en funksjon
fun SettInn(x: int, t: BTre): BTre = ...
som lager et nytt bin?rt s?ketre som er lik treet t, men med x satt
inn p? rett plass.
6. Skriv en funksjon
fun ErSortert(t: BTre): Bool = ...
som tester om et gitt bin?rt tre er sortert med hensyn p?
mindre-eller-lik funksjonen, dvs. om treet er et bin?rt s?ketre.
7. Skriv en funksjon som speilvender et gitt bin?rtre.
Oppgave 5
---------
Eksamen 1995, oppgave 3a-c: (Gamle eksamensoppgaver kan finnes ved ?
f?lge link fra hjemmesiden til kurset.)
(3a Typen tid) Gitt f?lgende type i ML som er ment ? beskrive
tidspunkt for start av en forelesningstime:
datatype tid =
man of int | tir of int | ons of int | tor of int | fre of int ;
Vi skal i det f?lgende holde oss til forelesningstimer som starter kl. 12, 13, 14 eller 15.
Defin?r i ML en funksjon
fun neste_tid (x:tid) = ...
som gir neste (mulige) forelesningstime etter x, for eksempel skal
neste tid etter (man 12) v?re (man 13), og neste tid etter (man 15)
v?re (tir 12). Kallet neste tid (fre 15) skal resultere i et unntak,
"helg".
(3b Duplikater i en tidsliste) Tenk deg at du har bladd gjennom
forelesningskatalogen og skrevet opp en liste med tidspunktene for de
forelesningene du vil g? p?. (En dobbeltforelesning gir to elementer i
listen.) Listen er ikke sortert p? noen m?te, og samme tidspunkt kan
komme flere ganger. Lag en funksjon "dup" som tar en slik liste l og
returnerer listen av "duplikater" -- en forekomst av et element er et
duplikat hvis det samme elementet forekommer lenger til h?yre i
listen. For eksempel skal "dup" av listen
[(man 12), (man 13), (tir 12), (man 12), (fre 12), (man 12), (tir 12)]
gi del-listen [(man 12), (tir 12), (man 12)].
(3c Generalisering) Vis eller forklar hvordan dup-funksjonen over kan
generaliseres til en vilk?rlig liste, ''a list (der '' angir at
type-parameteren ''a har en likhetstest).
Oppgave 6
---------
Gitt f?lgende definisjon av funksjonen Gjenta:
fun gjenta(f,d,l) =
case l of [] => d
| x :: l' => f(x,gjenta(f,d,l'));
der d angir en "default"-verdi.
Hvis vi har gitt en funksjon
fun minus (x:int, y:int) = x-y;
s? vil
gjenta(minus, 0, [1,2,3]);
regne ut (1-(2-(3-0))) som gir svaret 2. Du skal lage en
gjenta-versjon som regner ut (((1-2)-3)-0) som skulle gi -4.
Oppgave 7 (Eksamen 1993, oppgave 2a)
---------
La typen ''Elem Rel betegne lister av par av elementer:
type ''Elem Pair = ''Elem * ''Elem;
type ''Elem Rel = ''Elem Pair list;
En verdi r av typen Rel kan brukes til ? representere en (bin?r)
relasjon. For eksempel, la Elem v?re typen Person, og tenk deg at Per
synes han kjenner Anne og Jon, Anne synes hun kjenner Per og Eva, Eva
synes hun kjenner Per, mens Jon synes ikke han kjenner noen. Dette kan
uttrykkes ved mengden av parene (Per, Anne), (Per, Jon), (Anne, Per),
(Anne, Eva), (Eva, Per). Dette eksemplet p? en bekjentskaps-relasjon
skal vi kalle E1.
1. Definer i ML en funksjon
fun inv(r: ''Elem Rel): ''Elem Rel = ...
som snur ("inverterer") relasjonen r, dvs. (x,y) er med i inv(r)
hvis og bare hvis (y,x) er med i r.
2. Definer i ML en funksjon
fun relto(r: ''Elem Rel, s: ''Elem list): ''Elem list = ...
som gir mengden av alle y som er relatert til noe i s. For eksempel
vil relto(E1,s) gi mengden av Anne og Jon hvis s er mengden av Per
alene, og gi mengden av Eva og Per hvis s er mengden av Anne og
Jon.
Begge funksjonene inv og relto skal lages uten bruk av case - isteden
kan du bruke funksjonene oppdater, gjenta og plukk (som definert p?
forelesningen).