P1-WS04-MusterLoesung12.txt

;;                                                 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