Sei   ein beliebiger Datentyp. Dann ist eine Liste von Elementen aus   gegeben durch  

Einfache Konzepte der funktionalen Programmierung

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Der Aufruf

(square 6)

ergibt

36

Der Aufruf

(inc 100)

ergibt

101

Rekursion

Bearbeiten

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   mit   kann so erfolgen:

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

Dann ergibt

 (! 20)

den Wert

2432902008176640000

Abstraktion

Bearbeiten

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

Bearbeiten

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

Komposition

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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   und einer Funktion   die Liste   bestimmt.

(map square '(1 2 3))
'(1 4 9)

Faltungen

Bearbeiten

Die (Rechts-) Faltung einer Liste   durch eine zweistellige Funktion   und einen initialwert ist gegeben durch  . 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