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