Listen als Funktionen
|
Das Konkatenieren von Listen und das Anhängen eines Elementes hinten
an eine Liste hat eine Laufzeitkomplexität von O(n) mit n = Länge
der (ersten) Liste.
|
|
Dadurch bekommen Algorithmen, die Listen durch Konkatenation
zusammensetzen, häufig eine quadratische Laufzeit.
Ein typisches Beispiel ist die Konversion eines binären Baums in eine
Liste, bei der die Elemente der Liste in der
Reihenfolge im Baum bei einem depth-first-Durchlauf
vorkommen.
|
Beispiel |
für einen Algorithmus mit nicht linearer Laufzeit:
|
|
data BinTree a = Empty
| Node (BinTree a) a (BinTree a)
|
|---|
|
binTreeToList :: BinTree a -> [a]
binTreeToList Empty
= []
binTreeToList (Node l x r)
= binTreeToList l
++
[x]
++
binTreeToList r
|
|---|
Lösung |
Dieses ineffiziente Verhalten kann dadurch eliminiert werden,
dass eine andere Repräsentation für die Listen gefunden wird, bei
der die ineffizienten Operationen (++) geschickter realisiert werden.
|
|
Als Lösungsmöglichkeit bietet sich sehr häufig eine Darstellung als Funktion an
(ein Funktionstyp). Dieser Ansatz ist auch hier eine Lösungsmöglichkeit.
|
Typdefinition |
type FList a = [a] -> [a]
|
Abbildung |
Zu jeder normalen
Liste (jedem Wert aus [a]) gibt es
genau eine Funktion (einen Wert aus FList a), die diese Liste repräsentiert und umgekehrt.
Es gibt also eine bijektive Abbildung zwischen den Listen und den Funktions-Listen.
|
fromList |
fromList :: [a] -> FList a
fromList l = \ xs -> l ++ xs
fromList l = (l ++)
|
toList |
toList :: FList a -> [a]
toList l = l []
toList = ($ [])
|
Aufgabe .a |
Entwickeln Sie die Basisfunktionen für die normalen Listen
mit gleicher Funktionalität für FList a
|
Signaturen |
empty :: FList a
singleton :: a -> FList a
cons :: a -> FList a -> FList a
snoc :: FList a -> a -> FList a
append :: FList a -> FList a -> FList a
concatF :: [FList a] -> FList a
mapF :: (a -> b) -> FList a -> FList b
foldrF :: (a -> b -> b) -> b -> FList a -> b
headF :: FList a -> a
tailF :: FList a -> FList a
nullF :: FList a -> Bool
reverseF :: FList a -> FList a
|
Aufgabe .b |
Diskutieren Sie die Laufzeiten dieser Operationen
|
Aufgabe .c |
Entwickeln Sie eine Funktion
|
|
binTreeToFList :: BinTree a -> FList a
binTreeToList :: BinTree a -> [a]
binTreeToList = toList . binTreeToFList
|
|---|
?
|
Lösung
|
|
binTreeToFList :: BinTree a -> FList a
binTreeToFList Empty
= empty
binTreeToFList (Node l x r)
= binTreeToFList l
`append`
singleton x
`append`
binTreeToFList r
|
Aufgabe .d |
Untersuchen Sie die Laufzeit dieser Implementierung
|
Funktionale Programmierung: Funktionen als Daten
