Benutzer:West of House/FP

2

Sei $A$ ein beliebiger Datentyp. Dann ist eine Liste von Elementen aus $A$ gegeben durch $A*=Nil|ConsAA*$

Einfache Konzepte der funktionalen Programmierung

In der funktionalen Programmierung sind bestimmten Arbeitsmuster gängig. Die Wichtigsten werden im folgenden am Beispiel des leicht verständlichen Lisp-Dialekts Scheme erläutert.

Definition

Die Definiton einer Funktion erfolgt genau wie bei imperativer/struktirierter Programmierung. Zur Definition gehören ein Funktionsname, eine Parameterliste und ein Funktionskörper. Die Funktion 'square berechnet das Quadrat einer Zahl.

(define (square k) 
  (* k k))

(In Lisp/Scheme steht der Operator immer direkt hinter der sich öffnenden Klammer. Danach folgen die Operanden. Die Form (define (foo bar) baz) hat also den Operator define und die beiden Operanden (foo bar) und baz. Bei der Form (* k k) ist er Operator * und der Operanden sind k k. Den Funktionsaufruf $f(x)$ würde man in Scheme/Lisp (f x) notieren.)

Ein weiteres Beipiel ist die Funtion inc, die eine Zahl inkrementiert.

(define (inc n)
  (+ 1 n))

Applikation

Der Aufruf

(square 6)

ergibt

36

Der Aufruf

(inc 100)

ergibt

101

Rekursion

In der funktionalen Programmierung existieren keine Schleifen, da Schleifen zeitliche Abfolgen von Zuständen sind. Darum verwendet man Rekursion. Schleifen sind nur ein Spezialfall der Rekursion und deshalb durch diese voll ersetzbar. Die Berechnung der Fakultät $!:\mathbb {N} \to \mathbb {N}$ mit $!:n\mapsto 1\cdot 2\cdot 3\cdot ..\cdot n$ kann so erfolgen:

(define (! n)
  (if (< n 2)
      1
      (* n (! (- n 1)))))

Dann ergibt

 (! 20)

den Wert

2432902008176640000

Abstraktion

Dies ist das erste im engeren Sinne funktionale Konzept. Aufgabe der Funktion sort2 ist es, die beiden Parameter a und b in der richtigen Reihenfolge als Liste zurück zu geben. Dabei wird eine Ordungsrelation order übergeben und ein Funktion key, die aus einem der Datenelemente a,b das Merkmal berechnet, dass dieser Ordung gehorchen soll.

Der Vorteil dieser Herangehensweise ist es, dass die Funktionen key und order bei der Definition von sort2 offen bleiben können und erst bei der Applikation mitgegeben werden müssen.

(define (sort2 a b key order)
   (if (order (key a) (key b))
       (list a b)
       (list b a)))

Um nun die beiden Listen (2 3) und (7 2) nach dem ersten Element aufsteigend zu ordnen, ist dann folgender Aufruf geeignet:

(sort2 '(2 3) '(7 2) first <)

Es erfolgt die Ausgabe:

'((2 3) (7 2))

Aufsteigende Anordnung nach dem zweiten Element ist dann so berechenbar:

(sort2 '(2 3) '(7 2) second <) 

Die Rückgabe ist dann:

'((7 2) (2 3))

Synthese

Mit Synthese von Funtionen ist gemeint, Funktionen zur Laufzeit zusammenzusetzen und dabei gegebenenfalls vorhandene Funktionen zu verwenden.

Komposition

Aus den beiden Funktionen square und inc kann eine Funktion zusammengesetz werden, die incremente quadriert:

(define inc-sq
   (compose square inc))

Die neu geschaffene Funktion ist kann dann so gerufen werden:

(inc-sq 5)

Das Resultat ist

36

Natürlich kann auf die explizite Definition von inc-sq verzichtet werden. Dazu wird die Funktionsapplikation (compose square inc) in der die Operatortstellung am Anfang der Liste gesetzt:

((compose square inc) 10) 

Ausgabe:

121

Eigene Kompositionsoperatoren definieren

Die folgende Funktion twice errechnet eine Funktion, die eine Funktion f zweimal auf einen Operanden anwendet:

(define (twice f)
  (compose f f))

Die Berechnung der vierten Potenz kann dann so defniert werden:

(define to-the-forth (twice square))

Der Aufruf

(to-the-forth 3)

ergibt dann

81

anonyme Funktionen

Häufig wird eine Funktion nur benötigt, um sie direkt zu verwenden. Dann kann sie ohne Namen mit dem Symbol 'lambda vereinbart werden. Hier werden alle Zahlen, die nicht größer als 10 sind, aus einer Liste entfernt:

(filter (lambda (x) (> x 10)) '(4 3232  333  2 1 1))

Das Ergebnis ist:

'(3232 333)

Neben dem filter-idiom oben gibt es weitere oft verwendete Verfahren, wie das Mapping, das aus einer Liste $[x_{1},x_{2},..,x_{n}]$ und einer Funktion $f$ die Liste $[f(x_{1}),f(x_{2}),..,f(x_{n})]$ bestimmt.

Mapping

(map square '(1 2 3))

'(1 4 9)

Faltungen

Die (Rechts-) Faltung einer Liste $[x_{1},x_{2},x_{3},..,x_{n}]$ durch eine zweistellige Funktion $f(a,b)$ und einen initialwert ist gegeben durch $f(x_{1},f(x_{2},f(x_{3},..,f(x_{n},i)..)$. Viele Schleifen aus der imperativen Programmierung realisieren de facto Faltungen. Daher kommen Faltungen verscheidener Art sehr oft in der Funktionalen Programmierung vor.

(define (reduce init fn list)
  (if (null? list) init
      (fn (car list)
          (reduce init fn (cdr list)))))

Die Summe einer Zahlenliste ist dann so berechenbar:

(reduce 0 + '(3 4 5 6))

18