INF3110/4110
L�sningsforslag uke 37 (10.-12.9.2003)
Oppgave 1
---------
fun reverser (l: 'a list) : 'a list =
case l of [] => []
| x :: xs => reverser(xs) @ [x];
Oppgave 2
---------
fun append (l1: 'a list, l2: 'a list) : 'a list =
case l1 of [] => l2
| x :: xs => x :: append(xs, l2);
Oppgave 3
---------
1. fun mindre(x:Data,y:Data):bool =
case y of no => false
| tall(i) => (case x of no => true
| tall(j) => j y
| tall(j) => case y of no => x
| tall(i) => tall((i+j) div 2);
4. fun snitt(l:Dataliste):Data =
case l of [] => no
| x::r => snitt2(x,snitt(r));
5. Fordi rekursjonen g�r til slutten av listen f�r noe regnes ut, vil
snitt([tall(7),tall(8),tall(5)]) f�rst regne ut
snitt2(tall(8),tall(5)) som gir tall(6), og s�
snitt2(tall(7),tall(6)) som ogs� gir tall(6) (pga
heltallsdivisjon). Dette er IKKE det samme resultatet som
snitt([tall(8),tall(5), tall(7)]) som f�rst tar snittet av tallene
5 og 7, som blir 6, og s� snitt2 av 6 og 8, som til slutt gir
tall(7).
Oppgave 4
---------
1. fun Str(t: BTre): int =
case t of Tom => 0
| Node(v,i,h) => Str(v) + 1 + Str(h);
2. fun Infiks(t: BTre): int list =
case t of Tom => []
| Node(v,i,h) => Infiks(v) @ [i] @ Infiks(h);
3. fun Postfiks(t : BTre): int list =
case t of Tom => []
| Node(v,i,h) => Postfiks(v) @ Postfiks(h) @ [i];
4. fun Prefiks(t: BTre): int list =
case t of Tom => []
| Node(v,i,h) => [i] @�Prefiks(v) @�Prefiks(h);
5. fun SettInn(x: int, t: BTre): BTre =
case t of Tom => Node(Tom, x, Tom)
| Node(v,i,h) => if x <= i then Node(SettInn(x, v), i, h)
else Node(v, i, SettInn(x, h));
6. Et bin�rtre er sortert hvis listen vi f�r ved infiks traversering
er sortert. Vi trenger derfor en hjelpefunksjon ListeSortert som
sjekker om en liste av heltall er sortert eller ikke.
fun ListeSortert(l: int list): bool =
case l of [] => true
| x1::l1 => case l1 of []� => true
| x2::l2 => x1 <= x2 andalso
ListeSortert(l1);
fun ErSortert(t: BTre): bool = ListeSortert(Infiks(t));
7. fun Speilvend(t: BTre): BTre =
case t of Tom => Tom
| Node(v,i,h) => Node(Speilvend(h), i, Speilvend(v));
Oppgave 5
---------
exception helg;
fun neste_tid(x:tid) =
case x of man t => if t<15 then man (t+1) else (tir 12)
| tir t => if t<15 then tir (t+1) else (ons 12)
| ons t => if t<15 then ons (t+1) else (tor 12)
| tor t => if t<15 then tor (t+1) else (fre 12)
| fre t => if t<15 then fre (t+1) else raise helg;
fun has x l =
case l of [] => false
| x'::l' => x=x'
orelse has x l';
fun dup(l: tid list) =
case l of [] => []
| x'::l' => if has x' l' then x'::(dup l')
else dup l' ;
Hjelpefunksjonen has er her av typen ''a -> ''a list -> bool.
fun dup l =
eller
fun dup (l: ''a list) =
eller
fun dup (l): ''a list =
eller
fun dup (l: ''a list): ''a list =
forutsatt at has fungerer p� vilk�rlige lister, slik som v�r has
over. Typen til dup blir n�: ''a list -> ''a list.
Oppgave 6
---------
fun gjenta2(f,d,l) =
case l of [] => d
| x :: r => case r of [] => f(x,d)
| y :: r' => gjenta2(f,d,(f(x,y)::r'));
Oppgave 7
---------
1. Vi definerer f�rst en funksjon snu som snur ett par. Selve
inv-funksjonen kan da enkelt lages ved hjelp av oppdater.
fun snu(x: ''Elem Pair): ''Elem Pair = (#2 x, #1 x);
fun inv(r: ''Elem Rel): ''Elem Rel = oppdater(snu,r);
2. Vi lager oss f�rst en funksjon ltest som tester om f�rste element i
et par er med i den gitte listen. Funksjonen rpart plukker ut andre
element av et par, da det bare er disse vi skal ha med i det
endelige svaret.
fun ltest(s: ''Elem list) (x: ''Elem Pair): bool = has(s, #1 x);
(* has kan defineres som f�r: *)
fun has(s,e) = case s of []�=> false
| e'::s' => e=e' orelse has(s',e);
fun rpart(x: ''Elem Pair): ''Elem = #2 x;
Funksjonen relto kan da lages ved hjelp av oppdater og plukk som
f�lger:
fun relto(r: ''Elem Rel, s: ''Elem list): ''Elem list =
oppdater(rpart, plukk(ltest(s), r));