Funktional Praktikum 1

Page content

Funktional Teil 1

;;load lisp files
(load "more-functional.lisp")

1. Iteration

(defun range (a &optional (b nil) (c 1))
  (cond ((null b)
          (funcall 'range 0 a c))
        (t (cond ((< (* a c) (* b c))    ;;mit c multiplizieren um Bedingung umzukehren wenn c negativ
          (cons a (funcall 'range (+ a c) b c)))
             (t nil)))))

(defun repeat (times value)
  (mapcar (lambda (n) value)
    (range times)))

* (repeat 5 'hello)
(HELLO HELLO HELLO HELLO HELLO)

(defun repeatedly (times fun)
  (mapcar fun (range times)))

Lösung

;;Anlegen einer Liste, die fünfmal das Symbol HELLO enthält
(repeatedly 5 #'(lambda (&REST R) 'hello))

;;Eine Liste, die fünf zufällige Würfelergebnisse (1..6) enthält.
(repeatedly 5 #'(lambda (&REST R) (random 7)))

;;Eine Liste mit fünf IDs: ("id0" "id1" "id2" "id3" "id4")
(repeatedly 5 #'(lambda (arg) (concatenate 'string "id" (write-to-string arg))))

Funktion always:

(defun always (val)
    (lambda (&rest args)
        (declare (ignore args)) val))
(defmacro setfun (symb fun)
`(prog1 ',symb (setf (symbol-function ',symb) ,fun)))
(setfun answer (always 'hello))

(repeatedly 5 #'answer)
(HELLO HELLO HELLO HELLO HELLO)

Fragen

  • Wird hier eine Closure verwendet?
    Ja, es wird ein Closure verwendet, da die Lambda Funktion das arg der always Funktion zurückgeben kann.
  • Geben Sie an, wie Sie die Liste, welche fünfmal das Symbol HELLO enthält (erste der Aufgaen oben) nun mit repeatedly und always erzeugen können.
    ….
  • Ist always eine Funktion höherer Ordnung?
    Ja, da always eine Funktkion zurückgibt.

2. Funktion dekorieren

Funktionen für die Aufgabe

;; Parse string to float if possible, else return NIL
;;
(defun parse-float (strg)
  (if (stringp strg)
      (with-input-from-string (s strg)
        (let ((res (read s)))
          (if (eq (type-of res) 'single-float) res nil)))))

;; Parse string to int if possible, else return NIL
;;
(defun parse-int (strg)
  (ignore-errors (parse-integer strg)))

;;dekorieren
(defun decorate (f pre &optional (post #'(lambda (arg) arg)))
  (lambda (&rest args)
    (cond ((equal args '(:orig)) f)
          (t (funcall post (apply f (apply pre args)))))))
          
;;dispatch, ruft eine liste von funktionen auf, bis die erste true zurückgibt
(defun dispatch (&rest funcs)
  (lambda (&rest args)
    (if (null funcs) nil
        ;; else
        (let ((result (apply (car funcs) args)))
          (if result result
              ;; else
              (apply (apply #'dispatch (cdr funcs)) args))))))
              
(defun print-res (res)
  (format t "Result: ~S~%" res) res)

Aufgabe

(setfun num (dispatch #'parse-int #'parse-float #'identity))
(defun num-args (&rest args)
  (mapcar #'num args))
  • Was macht die Funktion num? Demonstrieren Sie dies an ein paar Beispielaufrufen. Welchen Zweck erfüllt die Funktion identity in der Definition von num?
  • Schreiben Sie mit Hilfe von decorate und num-args eine neue Funktion add, welche beliebige Zahlen addieren kann, egal ob sie als Zahlenliteral oder als String vorliegen.
(setfun add (decorate #'+ #'num-args #'print-res))
* (add 1 2 "100" "2.5" 3.2)
Result: 108.7
108.7
  • Demonstrieren Sie die Möglichkeiten der Funktion add an ein paar Beispielaufrufen.
  • Welche Verbesserungen wären noch sinnvoll? Ergänzen Sie Ihre Implementierung entsprechend.

3. Partielle Anwedung

(defun partial (f &rest args)
(lambda (&rest more-args)
(apply f (append args more-args))))

(setfun three-times (partial #'* 3))
* (three-times 3)
9

Aufgaben:

  • Welche Kriterien muss eine Funktion erfüllen, um endrekursiv (tail recursive) zu sein? Wozu dient hier das zweite Argument?

funktion f ist dann endrekursiv wenn die letzte Berechnung von f der rekursive Aufruf ist. Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird.
mit dem zweiten Argument kann die Fakultät noch mit einem Faktor multipliziert werden.

  • Passen Sie die Funktion mit Hilfe von partial so an, dass der rekursive Aufruf mit allen Argumenten vorbereitet, aber noch nicht ausgeführt wird. Wie muss man die Funktion nun aufrufen, damit die Fakultät von 3 ausgerechnet wird?
(setfun fact-three (partial #'factorial 3 1))
FACT-THREE
* (fact-three)
6

4. Quicksort (optional)