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

2. fun max(x:Data,y:Data):Data = if mindre(x,y) then y else x;

3. fun snitt2(x:Data,y:Data):Data =
   case x of no      => 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 = <som over>
eller
   fun dup (l: ''a list) = <som over>
eller
   fun dup (l): ''a list = <som over>
eller
   fun dup (l: ''a list): ''a list = <som over>

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