INF3110/4110 Ukeoppgaver uke 37 (10.-12.9.2003) Oppgave 1 --------- Skriv en ML-funksjon fun reverser (l: 'a list) : 'a list = ... som reverserer rekkef?lgen til elementene i en liste. Eks. reverser(["A", "B", "C"]) gir ["C", "B", "A"] og reverser([1, 2, 3, 4]) gir [4, 3, 2, 1] Oppgave 2 --------- Skriv en ML-funksjon fun append (l1: 'a list, l2: 'a list) : 'a list = ... som setter sammen to lister til en. Eks. append(["A", "B", "C"], ["D", "E", "F"]) gir ["A", "B", "C", "D", "E", "F"] og append([1,2], [3,4]) gir [1,2,3,4] Oppgave 3 --------- Gitt ML-typen datatype Data = tall of int | no; som vi kan tenke oss er nyttig for ? representere m?lingsresultater som av og til kan sl? feil (representert ved konstantverdien no) og ellers gi et tall: tall(5) og no er eksempler p? verdier av denne typen. Vi kan n? definere en fordoblings-funksjon slik: fun dobbel(x:Data):Data = case x of no => no | tall(i) => tall(i+i); 1. Definer en mindre-enn relasjon fun mindre(x:Data, y:Data):bool = ... som er slik at konstanten no er mindre enn alle andre verdier, og slik at tall(5) er mindre enn tall(6). F.eks. skal mindre(tall(5), no) gi false, mens mindre(no, tall(5)) skal gi true. 2. Definer en funksjon fun max(x:Data, y:Data):Data = ... som gir det st?rste av de to argumentene som funksjonsverdi. F. eks. skal max(no, tall(5)) gi tall(5). 3. Du skal lage en funksjon snitt2(x:Data, y:Data):Data = ... for ? finne gjennomsnittet av to m?linger, slik at snitt2(no,no) gir no, og snitt2(no,tall(5)) gir tall(5) og snitt2(tall(8),tall(5)) gir tall(6). Bruk heltallsdivisjon, div, selv om dette gir et tiln?rmet gjennomsnitt. 4. Gitt typen type Dataliste = Data list; Lag en funksjon fun snitt(l:Dataliste):Data = case l of [] => no | x::r => ... ; som regner et slags gjennomsnitt av alle m?lingene i listen l, slik at snitt([]) gir no, og snitt([no,tall(5)]) gir tall(5) og snitt([tall(8),tall(5), tall(7)]) gir tall(7). Bruk heltallsdivisjon, div, og bruk funksjonen snitt2, selv om dette ikke gir det mest eksakte gjennomsnitt. 5. Gir snitt([tall(7),tall(8),tall(5)]) det samme resultatet som snitt([tall(8),tall(5), tall(7)])? Forklar hvorfor/hvorfor ikke? Oppgave 4 --------- Med et bin?rt s?ketre menes det her et bin?rt tre som er slik at for node x er alle verdier i venstre subtre til x mindre enn verdien i x og alle verdier i h?yre subtre til x er st?rre enn verdien i x. I ML kan slike tr?r defineres ved: datatype BTre = Tom | Node of BTre * int * BTre; Eksempel: val testtre = (* bin?rt s?ketre *) Node(Node(Tom,1,Tom),2,Node(Node(Tom,3,Tom),4,Node(Tom,5,Tom))); 3 5 \ / 1 4 \ / 2 1. Lag en funksjon fun Str(t: BTre): int = ... som finner antall noder i det bin?re treet t. 2. Lag en funksjon som gitt et bin?rtre t: Btre gir som verdi en liste l: int list som tilsvarer de verdiene vi ``ser'' ved en infiks-traversering av det bin?re treet t. 3. Som over, men listen skal n? tilsvare de verdiene vi ``ser'' ved en postfiks-traversering av treet. 4. Som over, men listen skal n? tilsvare de verdiene vi ``ser'' ved en prefiks-traversering av treet. 5. Lag en funksjon fun SettInn(x: int, t: BTre): BTre = ... som lager et nytt bin?rt s?ketre som er lik treet t, men med x satt inn p? rett plass. 6. Skriv en funksjon fun ErSortert(t: BTre): Bool = ... som tester om et gitt bin?rt tre er sortert med hensyn p? mindre-eller-lik funksjonen, dvs. om treet er et bin?rt s?ketre. 7. Skriv en funksjon som speilvender et gitt bin?rtre. Oppgave 5 --------- Eksamen 1995, oppgave 3a-c: (Gamle eksamensoppgaver kan finnes ved ? f?lge link fra hjemmesiden til kurset.) (3a Typen tid) Gitt f?lgende type i ML som er ment ? beskrive tidspunkt for start av en forelesningstime: datatype tid = man of int | tir of int | ons of int | tor of int | fre of int ; Vi skal i det f?lgende holde oss til forelesningstimer som starter kl. 12, 13, 14 eller 15. Defin?r i ML en funksjon fun neste_tid (x:tid) = ... som gir neste (mulige) forelesningstime etter x, for eksempel skal neste tid etter (man 12) v?re (man 13), og neste tid etter (man 15) v?re (tir 12). Kallet neste tid (fre 15) skal resultere i et unntak, "helg". (3b Duplikater i en tidsliste) Tenk deg at du har bladd gjennom forelesningskatalogen og skrevet opp en liste med tidspunktene for de forelesningene du vil g? p?. (En dobbeltforelesning gir to elementer i listen.) Listen er ikke sortert p? noen m?te, og samme tidspunkt kan komme flere ganger. Lag en funksjon "dup" som tar en slik liste l og returnerer listen av "duplikater" -- en forekomst av et element er et duplikat hvis det samme elementet forekommer lenger til h?yre i listen. For eksempel skal "dup" av listen [(man 12), (man 13), (tir 12), (man 12), (fre 12), (man 12), (tir 12)] gi del-listen [(man 12), (tir 12), (man 12)]. (3c Generalisering) Vis eller forklar hvordan dup-funksjonen over kan generaliseres til en vilk?rlig liste, ''a list (der '' angir at type-parameteren ''a har en likhetstest). Oppgave 6 --------- Gitt f?lgende definisjon av funksjonen Gjenta: fun gjenta(f,d,l) = case l of [] => d | x :: l' => f(x,gjenta(f,d,l')); der d angir en "default"-verdi. Hvis vi har gitt en funksjon fun minus (x:int, y:int) = x-y; s? vil gjenta(minus, 0, [1,2,3]); regne ut (1-(2-(3-0))) som gir svaret 2. Du skal lage en gjenta-versjon som regner ut (((1-2)-3)-0) som skulle gi -4. Oppgave 7 (Eksamen 1993, oppgave 2a) --------- La typen ''Elem Rel betegne lister av par av elementer: type ''Elem Pair = ''Elem * ''Elem; type ''Elem Rel = ''Elem Pair list; En verdi r av typen Rel kan brukes til ? representere en (bin?r) relasjon. For eksempel, la Elem v?re typen Person, og tenk deg at Per synes han kjenner Anne og Jon, Anne synes hun kjenner Per og Eva, Eva synes hun kjenner Per, mens Jon synes ikke han kjenner noen. Dette kan uttrykkes ved mengden av parene (Per, Anne), (Per, Jon), (Anne, Per), (Anne, Eva), (Eva, Per). Dette eksemplet p? en bekjentskaps-relasjon skal vi kalle E1. 1. Definer i ML en funksjon fun inv(r: ''Elem Rel): ''Elem Rel = ... som snur ("inverterer") relasjonen r, dvs. (x,y) er med i inv(r) hvis og bare hvis (y,x) er med i r. 2. Definer i ML en funksjon fun relto(r: ''Elem Rel, s: ''Elem list): ''Elem list = ... som gir mengden av alle y som er relatert til noe i s. For eksempel vil relto(E1,s) gi mengden av Anne og Jon hvis s er mengden av Per alene, og gi mengden av Eva og Per hvis s er mengden av Anne og Jon. Begge funksjonene inv og relto skal lages uten bruk av case - isteden kan du bruke funksjonene oppdater, gjenta og plukk (som definert p? forelesningen).