(* Programmieraufgabe P-38: wortliste.ml *) (* Leonhard Fellermayr *) (* Mat.Nr. 22128130XXXX *) (* =================================================================== Die Test-Zeichenkette aus der Aufgabenstellung ------------------------------------------------------------------- *) let beispielStr = "Ocaml $$ list* typ array 34Typ oCaMl55 7c3ocaml 7676 ";; (* =================================================================== Diverse, bereits bekannte und nŸtzliche Hilfsfunktionen ------------------------------------------------------------------- *) let laenge = String.length;; let anfang = fun s -> String.get s 0;; let rest = fun s -> String.sub s 1 ((laenge s)-1);; let string_of_char = String.make 1;; (* =================================================================== istBuchstabe c - Stellt fest, ob c ein Buchstabe ist. StŸtzt sich dabei auf die ASCII-Konventionen. Eingabetyp: c: CHAR RŸckgabetyp: BOOL ------------------------------------------------------------------- *) let istBuchstabe c = ('A' <= c) && (c <= 'z');; (* =================================================================== listsort list - Simpelster Sortieralgorithmus (Vertauschung), der mittels doSort so oft aufgerufen wird, bis die Liste vollstŠndig sortiert ist. Eingabetyp: list: LISTE RŸckgabetyp: LISTE ------------------------------------------------------------------- *) let rec listsort list = match list with (w1,h1)::(w2,h2)::rest -> if w1 < w2 then (* w1, w2 sind von Haus aus richtig sortiert *) (w1,h1)::(listsort ((w2,h2)::rest)) else (* Umsortieren ist nštig, danach weiter *) (w2,h2)::(listsort ((w1,h1)::rest)) | x::[] -> x::[] | [] -> [];; (* =================================================================== isSorted list - PrŸfe, ob eine Liste vollstŠndig sortiert ist. (vgl. Definition von "Sortiertheit", Folie 222) Eingabetyp: list: LISTE RŸckgabetyp: BOOL ------------------------------------------------------------------- *) let rec isSorted list = match list with (w1,h1)::(w2,h2)::rest -> if w1 > w2 then false else isSorted ((w2,h2)::rest) | _ -> true;; (* =================================================================== doSort list - FŸhrt mittels listsort den Sortiervorgang durch, und zwar solange, bis list sortiert ist (funktionale Nachbildung einer while-Schleife ;) Eingabetyp: list: LISTE RŸckgabetyp: LISTE ------------------------------------------------------------------- *) let rec doSort list = if isSorted (listsort list) then listsort (list) else doSort (listsort (list));; (* =================================================================== isWordInList word list - PrŸfe, ob Wort word i.d. Liste list enth. Eingabetyp: word: STRING; list: LISTE RŸckgabetyp: BOOL ------------------------------------------------------------------- *) let rec isWordInList word list = match list with (w,h)::t -> w = word || isWordInList word t | [] -> false;; (* =================================================================== removeWordFromList word list - Entferne das Wort word aus der Liste list. Existiert es dort nicht, so geschieht nichts. Eingabetyp: word: STRING; list: LISTE RŸckgabetyp: LISTE ------------------------------------------------------------------- *) let rec removeWordFromList word list = match list with (w,h)::t -> if w = word then t else ((w,h) :: removeWordFromList word t) | [] -> list;; (* =================================================================== incrementWordFrequency word list - Suche das Tupel aus Wort und HŠufigkeit zum Wort word und erhšhe dessen HŠufigkeitswert um 1. Gib das aktualisierte Tupel anschlie§end zurŸck. Eingabetyp: word: STRING; list: LISTE RŸckgabetyp: STRING * INT ------------------------------------------------------------------- *) let rec incrementWordFrequency word ((w,h)::t) = if w = word then (w,h+1) else incrementWordFrequency word t;; (* =================================================================== append_or_update word list - PrŸfe mittels isWordInList, ob word schon in list enthalten a) falls nein, wird word an list angehŠngt (au§er es ist ein Leerstring) b) falls ja, wird nur die HŠufigkeit von word um 1 erhšht Eingabetyp: word: STRING; list: LISTE RŸckgabetyp: LISTE ------------------------------------------------------------------- *) let append_or_update word list = if isWordInList word list then (* schon drin: HŠufigkeit erhšhen *) incrementWordFrequency word list :: removeWordFromList word list else (* neues Wort: an Liste anhŠngen, *) if word <> "" then (* falls kein Leerstring *) ((word,1)::list) (* HŠufigkeit zunŠchst auf 1 setzen *) else (* sonst: unverŠnderte Liste *) list;; (* =================================================================== parseString s cw wortliste - Parse den String s nach Wšrtern. Diese werden in cw zwischengespeichert und an wortliste angehŠngt. Eingabetyp: s: STRING; cw: STRING; wortliste: LISTE RŸckgabetyp: LISTE ------------------------------------------------------------------- *) let rec parseString s cw wortliste = if laenge s > 0 then if istBuchstabe (anfang s) then (* Buchstaben sammeln *) parseString (rest s) (cw ^ string_of_char (anfang s)) wortliste else (* komplettes Wort cw an Liste anhŠngen und cw leeren *) parseString (rest s) "" (append_or_update cw wortliste) else (* letztes Wort anhŠngen *) append_or_update cw wortliste;; (* =================================================================== wortliste s - Funktion gemŠ§ Aufgabenstellung: Liefert die gefor- derte Liste der Wšrter aus s und ihrer HŠufigkeiten zurŸck, indem die Wšrter mittels parseString gesucht und anschlie§end mit doSort alphabetisch sortiert werden. Eingabetyp: s: STRING RŸckgabetyp: LISTE ------------------------------------------------------------------- *) let wortliste s = doSort (parseString (String.lowercase s) "" []);; (* =================================================================== BEISPIEL-AUSGABE ------------------------------------------------------------------- *) (* Rufe nun zur Demonstration die Funktion wortliste mit dem Beispiels-String auf, und lasse die Ergebnisliste sortieren. *) let beispielErgebnis = wortliste beispielStr;; (* EOF *)