Funktionale Programmierung: Begriffe, Definitionen und grundlegende Konzepte

Charakteristische Begriffe

Funktion

Funktionsanwendung

Typ

Ausdruck

Wert

nicht

Zuweisung

Schleife

Prozedur

Objekt

Methode

Auswertung

den durch einen Ausdruck beschriebenen Wert berechnen

Funktion

wie in der Mathematik:
eindeutige Zuordnung eines Resultats zu einem Argument

Beschreibung der Beziehung zwischen Werten

Typ

Beschreibung für eine Menge von Werten
Werteart
anschauliche Sichtweise, in der Theorie etwas zu einfach

ungetypte Sprache

nur eine universelle Werteart

LISP: Listen, genauer Bäume
Perl, Tcl: Strings, Zeichenreihen
Java: Object

dynamisch getypte Sprache

Variablen sind ungetypt,
können jeden Wert aufnehmen
Typinformation ist Teil des Wertes

Ruby, Python, Javascript, ...

getypte Sprache

Es gibt mehrere (viele) verschiedene Typen

statisch getype Sprache

oder streng getypte Sprache

Variablen sind getypt,
die Werteart aller Variablen, Konstanten und Ausdrücke wird vollständig statisch (vor der Programmausführung) bestimmt

Das Sprachsystem stellt sicher, dass nur mit zulässigen Werten gerechnet wird und nur zulässige Werte in Variablen gespeichert werden

Parametertyp

Wertebereich der zulässigen aktuellen Parameter einer Funktion

Resultattyp

Wertebereich der Resultatwerte einer Funktion

Werte

Zahlen, Zeichen, Listen, Bilder, Programme, ...

0, 1, 2
1.0, 4.2
'a', 'b', 'c'
"", "abc", "123"
(1, "abc")
[], ["a"], [1, 2, 3]

Wertedefinition

besteht aus zwei Teilen

Name für einen Ausdruck
Typ des Ausdrucks

Syntax

name :: Typ
name =  expr

Beispiel

dieZahl :: Integer
dieZahl =  6 * (3 + 4)

besitzt den Typ

wird definiert durch
nicht Gleichheitstest (==)

Konvention

Teil der Sprachdefinition

Wertenamen

beginnen mit Kleinbuchstaben

Typnamen

beginnen mit Großbuchstaben

Int, Integer,
Char, String,
Maybe, Either

Funktionsdefinition

für Funktionen mit einem Parameter

fct     :: ArgType -> ResultType
fct x   =  expr

Beispiel

square          :: Integer -> Integer
square x        = x * x
 
smaller         :: (Integer, Integer) -> Integer
smaller (x,y)   = if x <= y then x else y

Anwendung

Aufruf einer Funktion

square 5
square (3 + 4)
square (smaller (5, 3 + 4))

Auswertung
Vereinfachung
Reduktion

Ersetzen der linken Seite durch die rechte Seite und rechnen (reduzieren, vereinfachen, auswerten)

Beispiel

	square (3 + 4)
=	{ Definition von + }
	square 7
=	{ Definition von square }
	7 * 7
=	{ Definition von * }
	49

Auswertung von innen nach außen
und links nach rechts

innermost leftmost

call by value

2. Beispiel

	square (3 + 4)
=	{ Definition von square }
	(3 + 4) * (3 + 4)
=	{ Definition von + im linken Teilausdruck von * }
	7 * (3 + 4)
=	{ Definition von + im rechten Teilausdruck von * }
	7 * 7
=	{ Definition von * }
	49

Auswertung von außen nach innen
und links nach rechts

outermost leftmost

call by name

3. Beispiel

	square (3 + 4)
=	{ Definition von square }
	x * x where x = 3 + 4
=	{ Definition von + im Teilausdruck }
	x * x where x = 7
=	{ Einsetzen von x }
	7 * 7
=	{ Definition von * }
	49

Ersetzen von außen nach innen

Bedarfsauswertung, lazy evaluation

call by need

wie 2. nur keine doppelten Auswertungen

Welches ist die beste Strategie?

Auswertungsreihenfolge

2. Beispiel

three           :: Integer -> Integer
three x         =  3
 
infinity        :: Integer
infinity        =  infinity + 1

call by value

von innen nach außen

	three infinity
=	{ Definition von infinity }
	three (infinity + 1)
=	{ Definition von infinity }
	three ((infinity + 1) + 1)
=	{ Definition von infinity }
	three (((infinity + 1) + 1) + 1)
=	{ und so weiter }
	...

Die Berechnung terminiert nicht,
sie divergiert

call by name

von außen nach innen

	three infinity
=	{ Definition von three }
	3

bottom
⊥

undefinierter Wert: ⊥

Jeder Wertebereich enthält (in der Theorie) einen zusätzlichen undefinierten Wert

für illegale Argumente

Beispiel

1/0

Abbruch des Programms mit einer Fehlermeldung

für nichtterminierende Berechnungen

Beispiel

infinity

Endlos-Rekursion, Endlos-Schleife

.1 ist feststellbar,
.2 nicht

1. Beispiel mit unterschiedlichen Semantiken bei unterschiedlichen Auswertungsstrategien

Auswertungsreihenfolge

3. Beispiel

multiply        :: (Integer, Integer) -> Integer
multiply (x, y) =  if x == 0 then 0 else x * y
 
-- 2 Aufrufe
 
multiply (0, infinity)
multiply (infinity, 0)

Definition: strikt

eine Funktion f ist genau dann strikt, wenn f ⊥ = ⊥ gilt, sonst ist f nicht strikt.

Extensionalitäts-
Prinzip

extensionality

zwei Funktionen f und g sind genau dann gleich, wenn für alle Argumente x gilt: f x = g x

Beispiel

double, double2 :: Integer -> Integer
 
double  x       =  x + x
double2 x       =  2 * x
 
double x = double2 x        -- für alle x
double   = double2

Ob zwei (Haskell-)Funktionen gleich sind, ist im allgemeinen Fall nicht entscheidbar

=> keine Gleichheitstest für Funktionen definiert

Funktionsdefinition

für Funktionen mit mehreren Parametern

Currying

Beispiel .a

smaller         :: (Integer, Integer) -> Integer
smaller (x, y)  =  if x <= y then x else y

ein Parameter bestehend aus einem Paar ganzer Zahlen

Beispiel .b

smallerc        :: Integer -> (Integer -> Integer)
smallerc x y    =  if x <= y then x else y

zwei Parameter

Aufruf

smallerc a      :: Integer -> Integer
(smallerc a) b  :: Integer
 
-- gleichwertig mit
 
smallerc a b

Currying: Weniger Klammern

Currying: Parameter können zu unterschiedlichen Zeitpunkten übergeben werden

Beispiel

plus            :: (Integer, Integer) -> Integer
plus (x, y)     = x + y
 
incr            :: Integer -> Integer
incr y          = plus (1, y)
 
plusc           :: Integer -> (Integer -> Integer)
plusc x y       = x + y
 
incrc           :: Integer -> Integer
incrc           = plusc 1
 
-- Aufruf
 
incrc 41

2. Beispiel

twice           :: (Integer -> Integer) ->
                   (Integer -> Integer)
twice f x       = f (f x)
 
quad            :: Integer -> Integer
quad            = twice square
 
-- ohne Currying
 
twice           :: (Integer -> Integer, Integer) ->
                   Integer
twice (f, x)    = f (f x)
 
quad            :: Integer -> Integer
quad x          = twice (square, x)

NICHT

quad x = twice (square, x) -- für alle x

SONDERN

quad = twice square

λ-Ausdrücke

Funktionen ohne Namen
anonyme Funktionen

Beispiele

λ x -> x + 1
 
λ x y -> x + y
 
λ x -> λ y -> x + y

Das λ-Symbol wird durch das ASCII-Zeichen \ dargestellt.

Viele kleine nur an einer Stelle aufgerufene Funktionen können direkt an der Aufrufstelle eingesetzt werden.

twice (λ x -> x * x)

Syntax für Funktionen

kann vereinfacht (normalisiert) werden

    incr x = x + 1
=
    incr = λ x -> x + 1
 
    add x y = x + y
=
    add x = λ y -> x + y
=
    add = λ x -> λ y -> x + y
=
    add = λ x y -> x + y

Funktionen höherer Ordnung

Konversion

uncurried => curried

curry           :: ((a, b) -> c) -> (a -> b -> c)
curry f x y     = f (x, y)
 
-- oder
 
curry f         = λ x y -> f (x, y)

Konversion

curried => uncurried

uncurry          :: (a -> b -> c) -> ((a, b) -> c)
uncurry f (x, y) = f x y
 
-- oder
 
uncurry f        = λ (x, y) -> f x y

Signatur mit Typparametern

Assoziatvität

des Funktionspfeils ->

	a -> (b -> c)
=	{ Rechtsassoziativität von -> }
	a -> b -> c

Funktionen mit mehreren Parametern

fct              :: t1 -> t2 -> ... -> tn -> t
fct x1 x2 ... xn =  <expr>
 
-- Aufruf
 
fct e1 e2 ... en

2-stellige Operatoren

sind Funktionen mit 2 Parametern in Infix-Notation

3 + 4    entspricht  plusc 3 4
3 + 4    entspricht  (+) 3 4
 
-- Definition von plusc
 
plusc = (+)

Funktionskomposition

zusammensetzen von Funktionen
kombinieren --> Kombinatoren

gegeben

f1 :: t1 -> t2
f2 :: t2 -> t3

Komposition

(f2 . f1) x = f2 (f1 x)
 
-- oder
 
(.) f2 f1 x = f2 (f1 x)
 
-- oder
 
(.) f2 f1   = λ x -> f2 (f1 x)
 
-- oder
 
f2 . f1     =  λ x -> f2 (f1 x)

Typ

(.) :: (t2 -> t3) -> (t1 -> t2) -> (t1 -> t3)

Folgerung

quad    :: Integer -> Integer
quad    =  square . square
 
-- anstatt
 
quad x  = square (square x)

point-free style

quad = square . square

point-wise style

quad x = square (square x)

Funktionskomposition gibt es in (traditionellen) imperativen Programmiersprachen nicht

Ausnahme?

pipes in UNIX

cmd1 | cmd2 == cmd2 . cmd1

Assoziativität

	(f . g) . h
=	{ Assoziativität der Komposition }
	f . (g . h)
=	{ Klammern redundant }
	f . g . h

Komposition

von links nach rechts gelesen

(>>>)     ::  (t1 -> t2) -> (t2 -> t3) -> (t1 -> t3)
f1 >>> f2 = f2 . f1

guards
Wächter

signum          :: Integer -> Integer
signum x
  | x <  0      = -1
  | x == 0      =  0
  | x >  0      =  1
 
-- gleichwertig zu
 
signum          :: Integer -> Integer
signum x        = if x < 0
                  then -1
                  else if x == 0
                       then 0
                       else 1

Rekursion

fact            :: Integer -> Integer
fact n          =  if n == 0
                   then 1
                   else n * fact (n - 1)
 
-- oder
 
fact n
  | n == 0      = 1
  | otherwise   = n * fact (n - 1)

besser

fact            :: Integer -> Integer
 
fact n
  | n == 0   = 1
  | n > 0    = n * fact (n - 1)
  | n < 0    = error "fact with negative argument"

Definition

lokaler Größen

f       :: Float -> Float -> Float
f x y   = (a + 1) * (a + 2)
          where
          a = (x + y) / 2
 
f2      :: Float -> Float -> Float
f2 x y  = (a + 1) * (b + 2)
          where
          a = m / 2
          b = m / 3
          m = x + y

Polymorphe Typen

square          :: Integer -> Integer
sqrt            :: Integer -> Float
 
-- also
 
square . square :: Integer -> Integer
sqrt . square   :: Integer -> Float

Wiederholung: Welchen Typ besitzt .?

(.) :: (b -> c) -> (a -> b) -> (a -> c)
 
-- für alle Typen a, b und c

a, b und c sind Typvariablen

Definition

Typen, die eine Typvariable enthalten, heißen polymophe Typen

Namenskonvention

Typvariablen beginnen mit einem Kleinbuchstaben

Beispiele

curry     :: ((a, b) -> c) -> (a -> b -> c)
 
error     :: String -> a
 
id        :: a -> a
 
undefined :: a
 
-- für alle Typen a, b und c

Definition des Wertes undefined?

undefined :: a
undefined =  undefined

Typklassen

(+)     :: Int -> Int -> Int
(+)     :: Integer -> Integer -> Integer
(+)     :: Float -> Float -> Float
(+)     :: ...
 
-- also (???)
 
(+)     :: a -> a -> a

Beliebige Typen a ist zu allgemein

Lösung

Typklassen

Typen, die eine bestimmte zusätzliche Eigenschaft besitzen

(+) :: Num a => a -> a -> a

verschiedene vordefinierte Typklassen: für Gleichheitstests, Ordnung, Arithmetik, Konversion in eine externe Darstellung, ...

Beispiele

dieser Seite als Haskell-Quelle