P1-WS04-MusterLoesung12.txt
Version vom 12. Dezember 2006, 22:42 Uhr von 81.177.14.26 (Diskussion)
;; Musterloesung Aufgabenblatt 12 ;; P1 WiSe 04/05 ;; Henrich Pöhls ;; Daniel Schreckling ;; In diesem Aufgabenblatt werden Funktionen aus der Datei tools.scm ;; verwendet. Deshalb wird sie an dieser Stelle eingebunden. (load "tools.scm") ;; Aufgabe 1 ;; 1 a) Funktionen höherer Ordnung sind Funktionen, deren ;; Argumente bzw. Funktionsparameter wiederum Funktionen darstellen ;; oder deren Rückgabewerte Funktionen sind. ;; So muß z.B. "map" eine Funktion als Parameter haben und ist daher von ;; höherer Ordnung. Dagegen ist "eq" keine Funktion höherer Ordnung, ;; obwohl man den Aufruf "(eq + -)" ausführen kann (Ergebnis #f). ;; 1 b) ;; "map" ist eine Funktion höherer Ordnung, weil der erste Parameter eine ;; einstellige Funktion sein muß. ;; "plus-oder-minus" ist eine Funktion höherer Ordnung, weil der ;; Rückgabewert immer - oder + ist. ;; "pepper" ist eine Funktion höherer Ordnung, weil das erste Argument "f" ;; eine zweistellige Funktion sein muß. ;; "my-tan" ist keine Funktion höherer Ordnung, weil sowohl das Argument ;; als auch der Rückgabewert Zahlen sein müssen. ;; 1 c) ;; Die globale Umgebung wird verwendet, um das Argument "3" des ;; Funktionsaufrufes zu reduzieren. (Da es eine Zahl ist, findet keine ;; Reduktion statt.) Der Wert des Symbols pepper wird ebenfalls in der ;; globalen Umgebung aufgelöst zu dem Lambda-Ausdruck ;; (lambda (f arg1) (lambda (arg2) (f arg1 arg2))) ;; Bei der Anwendung dieser anonymen Funktion auf + und 1 entsteht eine ;; neue Umgebung mit den Bindungen f = + und arg1 = 1. Nach der ;; Funktionanwendung entsteht also der Ausdruck ;; (lambda (arg2) (+ 1 arg2)) ;; Erst bei der Anwendung dieser anonymen Funktion auf das ursprüngliche ;; Argument 3 entsteht eine weitere Umgebung, in der die Bindung arg2 = 3 ;; gilt. Der Gesamtausdruck wird also reduziert zu ;; (+ 1 3) ;; und weiter zum Ergebnis 4. ;; 1 d) ;; (map (curry * 2) '(1 2 3)) ;; ;; Jedes Element der Liste wird mit zwei multipliziert. ;; ;; Ergebnis: (2 4 6) ;; (map cons '(1 2 3) '(1 2 3)) ;; ;; Aus den Elementen beider Listen werden jeweils paarweise und in der ;; entsprechenden Reihenfolge Paare gebildet. Hierfür wird der ;; "Paarkonstruktor" cons verwendet ;; ;; Ergebnis: ((1 . 1) (2 . 2) (3 . 3)) ;; (filter pair? '((a b ) () 1 (()))) ;; ;; filter pred list => list ;; ;; Filtert genau die Elemente aus der übergebenen Liste, die das ;; Prädikat pred erfüllen. Hier bedeutet dies, dass genau die Elemente ;; herausgefiltert werden, die vom Typ pair sind. ;; ;; Da die leere Liste '()' und die Zahl '1' nicht vom Typ pair sind, ;; werden sie nicht in die Ergebnismenge übernommen. ;; ;; (()) ist im Unterschied zu () vom Typ pair?, da (()) eine abgekürzte ;; Schreibweise für ( () . () ) ist. ;; ;; Ergebnis: ((a b) (())) ;; Aufgabe 2) ;; Zum Testen unserer Funktionen verwenden ;; wir folgende Liste (define xs '(1 -2 -3 4 5 6 -7 8 -9 10)) ;; 2 a) ;; Verwende die Funktion reduce (reduce (lambda (x y) ;; Summiere die Absolutbeträge zweier Zahlen (+ (abs x) (abs y)) ) ;; lambda xs 0 ) ;; reduce ;; Eine zweite mögliche Lösung unter Verwendung einer ;; rekursiven Funktion wäre: ;; Rekursionsabschluss: Sollte die Liste die ;; Länge null haben, so ist die Summe der ;; Absolutbeträge auch null ;; Rekursionsschritt: Addiere zum Absolutbetrag ;; des ersten Elementes die Summe der Absolutbeträge ;; der Restliste (define (sum-abs xs) (cond ((null? xs) 0) (else (+ (abs(car xs)) (sum-abs (cdr xs)) ) ) ) ) ;; Ergebnis bei Anwendung auf unsere Beispielliste: 55 ;; 2 b) ;; Verwende die Funktion Filter und selektiere alle ;; Elemente der Liste, die kleiner 0 sind (filter ;; #t, wenn x kleiner 0 ist, #f sonst (lambda (x) (< x 0)) ;; die Liste xs ) ;; filter ;; Verwendet man außerdem curry, so wird die ;; Lösung noch kürzer. Beachte: bei dieser ;; Lösung muss aufgrund der Argumentpositionen ;; > verwendet werden. (filter (curry > 0) xs) ;; Alternative wäre: (filter (rcurry < 0) xs) ;; Ergebnis bei Anwendung auf unsere Beispielliste: ;; (-2 -3 -7 -9) ;; 2 c) ;; Zunächst werden alle Zahlen aus xs gefiltert, die ungerade sind, ;; also das Prädikat odd? erfüllen. Die Länge der resultierenden ;; Liste entspricht dann der Anzahl der ungeraden Zahlen in der Liste xs. (length (filter odd? xs)) ;; Ergebnis bei Anwendung auf unsere Beispielliste: 5 ;; 3) ;; Hier wird ein Beispiellagerstand definiert (define *Lagerbestand* '((Gummibaerchen . 100) (Lakritzschnecken . 30) (Wundertueten . 300) (Brausepulver . 1000) (Schokolade . 350) (Zahnpasta . 30))) ;; 3 a) ;; anzahl-von artikel => Anzahl ;; Bestimmt zum Namen eines Artikels die Anzahl ;; des Artikels, die im *Lagerbestand* aufgeführt ;; ist. (define (anzahl-von artikel) ;; hole den Wert zum ersten Element in der Liste (cdar ;; filtere genau die Elemente, deren Schlüssel ;; gleich dem Argument artikel ist (filter ;; #t, wenn der Schlüssel von x = artikel, #f sonst (lambda (x) (eqv? (car x) artikel)) *Lagerbestand* ) ;; filter ) ;; cdar ) ;; Verwendet man die Operation assq für assoziative ;; Listen, so erhält man folgende Lösung: (define (anzahl-von2 artikel) (cdr (assq artikel *Lagerbestand*))) ;; Ergebnis bei Anwendung auf unseren Beispielbestand: ;; > (anzahl-von 'Lakritzschnecken) ;; 30 ;; > (anzahl-von2 'Lakritzschnecken) ;; 30 ;; Hier wird natürlich davon ausgegangen, dass die ;; assoziative Liste konsistent ist und jeder Schlüssel ;; nur einmal vorkommt. Sollte dies nicht so sein, so ;; kann man zusätzlich über die Liste der Paare summieren ;; und man erhält folgende Lösung: (define (anzahl-von3 artikel) ;; summiere die Elemente der Liste (reduce + ;; Reduziere anhand von cdr die Elemente dieser ;; Liste (die Artikel) nur auf deren Anzahl (map cdr ;; Ermittle alle Elemente von *Lagerbestand2* ;; deren Schlüsselwert gleich dem Argument artikel ist (filter (lambda (x) (eqv? (car x) artikel)) *Lagerbestand2*) ) ;; map 0) ;; reduce ) ;; mit folgendem nicht ganz konsistenten Lagerbestand (define *Lagerbestand2* '((Gummibaerchen . 100) (Lakritzschnecken . 30) (Lakritzschnecken . 32) (Wundertueten . 300) (Brausepulver . 1000) (Schokolade . 350) (Zahnpasta . 30))) ;; erhält man für ;; > (anzahl-von3 'Lakritzschnecken) ;; 62 ;; 3 b) ;; Definiere zunächst eine Hilfsfunktion, die ;; zu zwei Artikeln, den Artikel ermittelt, der ;; die kleinere Anzahl aufweist. Bei Gleichheit ;; wird der erste Artikel zurückgegeben (define (min_artikel x y) (cond ((<= (cdr x) (cdr y)) x) (else y))) ;; Unter Verwendung von reduce wird zunächst der ;; Artikel in unserer assozativen Liste ermittelt, ;; der den kleinsten Wert hat. Die seed muss dem ;; ersten Element entsprechen. Abschließend wird ;; der Schlüssel des resultierenden Paars ermittelt, ;; in unserem Fall der Artikelname. ;; Falls in der Liste mehrere Artikel mit minimaler ;; Anzahl vorkommen, so wird nur der erste Artikel ;; ausgegeben. (define (minimum alist) (car (reduce min_artikel alist (car alist)))) ;; Ergebnis bei Anwendung auf Beispielliste: ;; > (minimum *Lagerbestand*) ;; lakritzschnecken ;; Zweite Lösungsmöglichkeit: ;; Definiere eine Hilfsfunktion, die rekursiv den Artikel ;; ermittelt, der die geringste Menge aufweist. ;; Rekursionsabbruch: Die Liste hat nur ein Element. Der ;; Artikel mit der kleinsten Anzahl ist genau das Element ;; dieser einelementigen Liste ;; Rekursionsschritt: Der Artikel mit der geringsten Anzahl ;; an Elementen ist das Minimum aus dem Kopf und dem Minimum ;; der Restliste. (define minimum_kv (lambda (alist) (if (= (length alist) 1) (car alist) (if (<= (cdr (car alist)) (cdr (minimum_kv (cdr alist)))) (car alist) (minimum_kv (cdr alist)) ) ) ) ) (define (minimum2 alist) (car (minimum_kv alist))) ;; Ergebnis bei Anwendung auf Beispielliste: ;; > (minimum2 *Lagerbestand*) ;; lakritzschnecken ;; Dritte erweiterte Lösungsmöglichkeit: ;; Problem: Obige Funktionen liefern nur EIN Minimum, d.h. falls ;; zwei oder mehr Artikel die minimale Anzahl aufweisen, wird nur ;; der erste Artikel angezeigt. ;; minimum3 bestimmt zunächst das Minimum mit einer ähnlichen ;; Funktion, die in der ersten Lösungsmöglichkeit verwendet wurde ;; und filtert dann die Elemente aus der Liste, die genau diese ;; minimale Anzahl haben. Abschließend werden mit map die Namen ;; der Artikel extrahiert. Ergebnis ist eine Liste von Namen, die ;; Artikel bezeichnen, die eine minimale Anzahl aufweisen. (define (minimum3 alist) (let ;; berechne zunächst die minimale Artikelanzahl, ;; die in a list zu finden ist ((mini (cdr (reduce min_artikel alist (car alist))))) ;; extrahiere die Namen der Artikel (schlüsselwerte) (map car ;; filtere die Artikel heraus, die die minimale ;; Anzahl aufweisen (filter ;; #t, wenn dieser Artikel auch die minimale Anzahl ;; aufweist (lambda (x) (= (cdr x) mini) ) ;; lambda alist ) ;; filter ) ;; map ) ;; let ) ;; Ergebnis bei Anwendung auf unsere Beispielliste ;; > (minimum3 *Lagerbestand*) ;; (lakritzschnecken zahnpasta) ;; 3 c) (define *sollbestand* 1000) ;; nachbestellung artikel => artikel ;; Ermittelt zu einem Artikel die Anzahl der Einheiten, ;; die nachbestellt werden müssen, um den Vorrat auf ;; den Sollbestand zu erhöhen. Sind mehr Einheiten von ;; diesem Artikel vorhanden, so wird 0 ausgegeben. (define (nachbestellung artikel) (cons (car artikel) (if (< (cdr artikel) *sollbestand*) (- *sollbestand* (cdr artikel)) 0))) ;; Ergebnis bei Anwendung auf Beispielliste: ;; > (nachbestellung '(Lakritzschnecken . 800)) ;; (lakritzschnecken . 200) ;; 3 d) ;; Generiert eine Liste, die die Anzahl an Einheiten enthält, ;; die für einen bestimmten Artikel nachbestellt werden müssen. (define (bestelliste bestand) (map nachbestellung bestand)) ;; Ergebnis bei Anwendung auf Beispielliste: ;; > (bestelliste *Lagerbestand*) ;; ((gummibaerchen . 900) ;; (lakritzschnecken . 970) ;; (wundertueten . 700) ;; (brausepulver . 0) ;; (schokolade . 650) ;; (zahnpasta . 970))
297850591943426100394568