funktionale Programmierung Material Motivation Grundlagen Rekursion Listen Funktionen höherer Ordnung list comprehension Generator lazy evaluation Haskell Endrekursion Beispiele
Pfad: Startseite / Fächer / Informatik / funktionale Programmierung / Funktionen höherer Ordnung
Autor: mk
16.12.2010 15:51:11
737
Funktionen höherer Ordnung

map

Oft besteht der Wunsch, mit jedem Element einer Liste etwas zu machen, z.B. das Element zu verdoppeln oder in die dritte Potenz zu erheben oder ... .

def double(liste):
    if liste == []:
       return []
    else:
        return [liste[0]*2] + double(liste[1:])

def cube(liste):
    if liste == []:
       return []
    else:
        return [liste[0]**3] + cube(liste[1:])

Inwieweit unterscheiden sich die beiden Funktionen? Sieht das nicht nach 'böser Code-Duplizierung' aus? Man kann nun eine 'Universal-Funktion' schreiben, die ebenfalls die Liste durchgeht und das mit jedem Element macht, was eine als Parameter übergebenen Funktion f vorschreibt.

def f1(x):
    return x*2

def f2(x):
    return x**3

def mymap0(f,liste):
    if liste == []:
        return []
    else:
        return [f(liste[0])] + mymap0(f,liste[1:])

mymap ist eine Funktion höherer Ordnung, weil sie eine Funktion als Argument hat.

def mymap1(f):
    def g(liste):
        return mymap0(f,liste)
    return g

def mymap2(f):
    return lambda liste : mymap0(f,liste)

Der Name mymap verrät schon, dass es in Python eine eingebaute Funktion map gibt.

filter

Oft möchte man aus einer Liste eine Teilliste aller Elemente, die eine gewisse Bedingung erfüllen, extrahieren.

def myfilter(f,liste):
    if liste == []:
        return []
    else:
        if f(liste[0]):
            return [liste[0]] + myfilter(f,liste[1:])
        else:
            return myfilter(f,liste[1:])

def even(n):
    return (n%2 == 0)
Tests auf der Shell

Filter

filter ist in Python als Generator eingebaut.

reduce

Folgende Beispiele veranschaulichen die Funktion reduce. reduce findet man im Python-Modul functools.

def summe(liste):
    if len(liste) == 0:
        return 0
    else:
        return liste[0] + summe(liste[1:])

def produkt(liste):
    if len(liste) == 0:
        return 1
    else:
        return liste[0] * produkt(liste[1:])

def add(a,b):
    return a + b

def multiply(a,b):
    return a * b

def sum2(liste):
    if len(liste) == 0:
        return 0
    else:
        return add( liste[0] , sum2(liste[1:]) )

def prod2(liste):
    if len(liste) == 0:
        return 1
    else:
        return multiply( liste[0] , prod2(liste[1:]) )

def red1(liste, f, init):
    if len(liste) == 0:
        return init
    else:
        return f( liste[0] , red1(liste[1:], f, init) )

def reduce(f, init):
    return lambda liste : red1(liste,f,init)

def r2(f,init):
    def g(liste):
        return red1(liste,f,init)
    return g

Links