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));