Alle programmer skal skrives i SML. 
(I allle tilfeller skal du skrive et fullstendig program med
evt. hjelpefunksjoner og andre noedvendige definisjoner.)  

Oppgave 1.__________________________________________________________
Programmer en funksjon qs(L) : int list -> int list, som utfoerer quicksort
paa argument listen (med heltall) L. (Du kan faa bruk for MLs infix
operator @ som slaar sammen to argumentlister, f.eks. [1,2,3] @ [4,5] =
[1,2,3,4,5]. Vaer obs paa hvordan du haandterer duplikater. Valg av pivot er
ikke vesentlig og du kan gjoere det paa en maate som virker enklest mulig.) 
 
Oppgave 1.a.
Generaliser funksjonen qs til en polymorf funksjon som kan sortere
vilkaarlige lister avhengig av sammenlikningsoperator som sendes som aktuell
parameter. Dvs. programmer funksjon 
	   qsg: 'a list * ('a * 'a -> bool) -> 'a list 
som tar som input en liste (av 'a-elementer) og en boolsk
(sammenliknings)funksjon, og returnerer en liste sortert mht. til det siste
argumentet. F.eks. et kall:
	    qsg([2,1,4,5], fn(x,y) => x<y )
skal returnere listen sortert i stigende rekkefoelge: [1,2,4,5], mens et kall
	    qsg([2,1,4,5], fn(x,y) => x>y )
i nedstigende rekkefoelge: [5,4,2,1]. 


Oppgave 2.__________________________________________________________
Programmer en funksjon parseInt: char list -> int * char list, som tar som
input en liste av tegn (produsert av avblank(explode(...)) - se ekstraoppgave
nr.4 fra forrige uke), antar at den starter med et siffer, og da returnerer
den heltallet som staar i starten av listen (dvs. inntil det foerste tegnet
som ikke er et siffer), samt resten av tegnlisten. F.eks.
-- parseInt([#"2",#"1",#"s",#"d"])     = ( 21, [#"s",#"d"])
-- parseInt(avblank(explode "21 s d")) = ( 21, [#"s",#"d"])
-- parseInt([#"2",#"1"])     = ( 21, [])

Du faar selv bestemme hva som skal skje dersom input listen ikke starter med
et siffer -- bare soerg for at funksjonen ikke returnerer da noen
heltallsverdi. 


Oppgave 3.__________________________________________________________
La oss definere 

   datatype AST = I of int | N of AST | P of AST*AST ;

Intensjonen er at AST er abstrakte syntaks traer for aritmetiske uttrykk der:
-- I(x) representerer heltallet x, 
-- N(e) tilsvarer e med et minustegn foran, og 
-- P(e1,e2) tilsvarer summen av e1 og e2. 

Programmer en metode evp: AST -> int, som returnerer en heltallsverdi av et
AST. F.eks., foelgende boer bli tilfelle:
-- evp(N(N(I(5))));
   val it = 5 : int
-- evp(P( N(I(5)), P(I(7),N(I(2))) )) ;
   val it = 0 : int
-- evp(P( I(5), P(I(7),N(I(2))) )) ;
   val it = 10 : int

Programmer saa en metode evg: AST -> int, som gjoer det samme som evp med den
forskjellen at P(e1,e2) tolkes naa (dvs. evalueres) som multiplikasjon og
ikke som addisjon. F.eks.:
-- evg(N(N(I(5)))) ;
   val it = 5 : int
-- evg(P( N(I(5)), P(I(7),N(I(2))) )) ;
   val it = 70 : int
-- evg(P( I(5), P(I(7),N(I(2))) )) ;
   val it = -70 : int

Oppgave 3.a.
Begge evalueringsfunksjonene kan programmeres som en generisk funksjon med
noen ekstra parametere (som bestemmer evaluering av delutrykk). Programmer en
slik generisk funksjon samt to funksjoner som, naar sendt som aktuell
parameter, vil gi de
respektive, evp eller evg, evalueringene. 


Oppgave 4.__________________________________________________________
Du skal lage en parser for aritmetiske uttrykk. Grammatikken er gitt ved BNF:

   EXP ::= INT | (EXP + EXP) | (- EXP)

der INT staar for vilkaarlig heltall (uten noen minus tegn -- Oppgave 2). 
Helt generelt, parser er en funksjon 
       parseExp: string -> AST, 
som returnerer abstrakt syntakstre for input strengen (eller
melding om at input ikke er korrekt). 
Gitt en input streng S, du skal bruke foerst avblank(explode S), foer
parsing begynner, slik at din funksjon skal ha type:
	parseExp: char list -> AST * char list, 
der den ekstra listen av tegn i resultatet er resten av input listen som
gjenstaar etter at hele uttrykket fra starten av input har blitt parset - AST
blir da treet for dette uttrykket. 

F.eks., kallene parseExp(avblank(explode( xxx ))) skal returnere foelgende
naar xxx er:
-- "00123" = (123,[])
-- "(- (23 + (-7))) sde" =  ( N(P(I(23), N(I(7)))), [#"s",#"d",#"e"] )
-- "( (1+2) + (3+4) )" = ( P( P(I(1),I(2)), P(I(3),I(4)) ), [] )


Oppgave 5.__________________________________________________________
Sett sammen funksjonene fra oppgave 4 og 3 til en funksjon 
     ev: string -> int
som leser inn en input streng med et EXP-uttrykk, parser det og deretter
evaluerer og returnerer resultatet.