Funktionale Programmierung: Begriffe, Definitionen und grundlegende Konzepte

Charakteristische Begriffe

Funktion

Funktionsanwendung

Typ

Ausdruck

Wert

nicht

Zuweisung

Schleife

Prozedur

Objekt

Methode

Auswertung

den durch einem 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

LISPListen, genauer Bäume
TclStrings, Zeichenreihen
JavaObject

getypte Sprache

viele verschiedene Wertearten

statisch getype Sprache

oder streng getypte Sprache:

die Werteart aller Variablen, Konstanten und Ausdrücke wird vollständig
statisch (zur Übersetzungszeit) bestimmt

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

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

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

dieses Problem ist unentscheidbar

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

Konversion

uncurried => curried

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

Konversion

curried => uncurried

uncurry          :: (a -> b -> c) -> ((a, b) -> c)
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)

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?

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

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?

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