INF3110/4110
                   Ukeoppgaver uke 38 (17.-19.9.2003)



Oppgave 1
---------

Les løsningen på Dronning-oppgaven, ML-kompendiet s.17-18.
Skriv en kort forklaring på hvordan denne fungerer, og hva du
eventuelt lurer på.



Oppgave 2
---------

1. Skriv en rekursiv funksjon i ML, kalt sum, som for gitt n regner ut
   summen av alle tall fra 1 til n, f.eks. skal sum(5) gi verdien 15.

2. Hvis du nå skriver uttrykket
      sum(5) * (sum(5)-1)
   vil sum(5) regnes ut to ganger.  Prøv å skrive uttrykket på en
   annen måte, ved å bruke let-konstruksjonen, slik at sum(5) regnes
   ut bare en gang.



Oppgave 3
---------

Fibonacci-tallene er definert ved hjelp av følgende funksjon f:
   f(1) = 1
   f(2) = 1
   f(n) = f(n-1) + f(n-2), for n > 2

Vi skal lage en ML-funksjon 
   fun fib(n:int): int * int = ...
som er slik at funksjonsverdien av fib gir paret bestående av det
n-te Fibonacci-tallet samt det foregående Fibonacci-tallet.
For eksempel skal kallet fib(2) gi paret (1,1),
                         fib(3) skal gi  (2,1),
                         fib(4) skal gi  (3,2), 
                         fib(5) skal gi  (5,3) og 
                         fib(6) skal gi  (8,5). 
Vi definerer det null-te Fibonacci-tallet som 0, og da skal
                         fib(1) gi paret (1,0).
Bruk let-konstruksjonen til å lage en effektiv fib funksjon!



Oppgave 4 (Eksamen 1990, del 2a,b,e)
---------

I denne oppgaven skal du definere begrepet mengde med følgende
velkjente funksjoner:
   has -- som tester om et element er med i en mengde
   add -- som legger et element inn i en mengde
   union -- som danner unionen av to mengder
   inter -- som danner snittet av to mengder
   empty -- som danner den tomme mengden

Hvis for eksempel mengden "ansatte" består av elementene: "kari",
"anne", "lise", og mengden "stud" består av elementene: "lars",
"lise", så vil unionen av de to mengdene bestå av: "kari", "anne",
"lise", "lars", og snittet av dem vil bestå av: "lise".

1. Vi definerer mengde-begrepet som en parametrisert abstrakt datatype
   på følgende måte:

   signature Set_def =
      sig type ''Elem Set
         val empty: ''Elem Set
         val has  : ''Elem Set * ''Elem     -> bool
         val add  : ''Elem Set * ''Elem     -> ''Elem Set
         val del  : ''Elem Set * ''Elem     -> ''Elem Set
         val union: ''Elem Set * ''Elem Set -> ''Elem Set
         val inter: ''Elem Set * ''Elem Set -> ''Elem Set
      end;

   Mengdene skal representeres ved en liste-aktig datastruktur. Vi
   skal anta at for typen ''Elem finnes det en funksjon
      fun less(x,y:''Elem): bool = ...
   som svarer til å teste at x er mindre enn y. Vi krever at listen
   som representerer en mengde alltid er sortert med hensyn på denne
   ordning (med minste element først), og dessuten at hvert element
   forekommer høyst en gang i listen. Funksjonene i grensesnittet skal
   være slik at denne invarianten vedlikeholdes. Spesielt skal
   has-funksjonen utnytte invarianten ved å stoppe leting så snart som
   mulig.

   Din oppgave er å lage en implementasjon av dette grensesnittet,
   dvs.  en ``struktur'' for denne signaturen.

2. Diskuter plassforbruket (lager-behovet) til funksjonene du har
   laget.

3. Vi velger å representere en mengde som en funksjon m som er slik at
   m(x) er sann hvis x er et element i mengden og gal ellers. Lag en
   implementasjon av Set-grensesnittet med en slik
   representasjon. Typen ''Elem Set skal nå altså implementeres slik:
      type ''Elem Set = ''Elem -> bool;