Listen in Haskell - Listenoperationen höherer Ordnung

[ Gliederung ] [ Einführung ] [ Listenoperationen I ] [ Vollständige Induktion ] [ Listenoperationen II ] [ Literatur ]

Gliederung: Listenoperationen höherer Ordnung

Anwenden einer Funktion auf alle Elemente einer Liste / map

 
map           :: (a->b)->[a]->[b]
map f []      =  []
map (x:xs)    =  f x : map f xs
Anwendung: 
?map ord “Hallo“
[72,97,108,108,111]
Eigenschaften: 
map id = id
map f . map g = map (f.g)(*)
(*) Man kann diese Eigenschaft nutzen, um Traversierungen zu sparen. Zumindestens in der Theorie können solche Optimierungen auch von Compilern ausgeführt werden.

Aufsammeln aller Elemente die einem Prädikat p genügen / filter

 
filter           :: (a->Bool)->[a]->[a]
filter p []      =  []
filter p (x:xs)  =  if p x then x : filter p xs else filter p xs
Anwendung: 
?filter isUpper “AbKUErzungsFImmel“
“AKUEFI“
Eigenschaften: 
filter p . filter q = filter (p and q) (*)
filter p . concat = concat . map(filter p)
(*) Auch hier können wieder Traversierungen gespart werden!

"Mathematische Mengenkonstruktion"(*) / List comprehensions

 
[expr(x) | x<-xs, constraint(x)] = ...
[expr(x,y) | x<-xs, y<-s, constraints(x,y)] = ... (**)
usw.usf.
Anwendung: 
?[x*x|x<-[1..10],odd x]
[1,9,25,49,81]
?[x*y|x<-[1..10],y<-[1,2],odd x]
[1,2,3,6,5,10,7,14,9,18] (***)
(*) Der Begriff "Mathematische Mengenkonstruktion" ist natürlich Humbug. Ich habe diese Bezeichnung nur deshalb benutzt, weil man in Haskell zur Konstruktion von Listen eine Schreibweise nutzen kann, die der Schreibweise, mit der in der Mathematik üblicherweise Mengen definiert werden, sehr ähnlich ist.
Dieses Konstrukt versagt natürlich spätestens dann, wenn unabzählbare Mengen beschrieben werden sollen.
(**) Die Reihenfolge der Erzeuger (x<-xs) und Constraints, sowie deren Anzahl ist beliebig. Die hier verwendete Schreibweise ist jedoch idiomatisch.
(***) Der zuletzt deklarierte Erzeuger bildet offensichtlich hier die "innere Schleife":
x*y: {1*1, 1*2, 3*1, 3*2, 5*1, 5*2, 7*1, 7*2, 9*1, 9*2}

Die Fold-Funktionen (fold-right) / foldr

 
foldr            :: (a->b->b)->b->[a]->b
foldr f e []     =  e
foldr f e (x:xs) =  f x (foldr f e xs)
Anwendung: 
?foldr (+) 0 [1,2,3] (*)
6
Eigenschaften: 
foldr ($) e [x1,x2,..,xn] = x1 $ (x2 $ (..(xn $ e)..)) (**)
(*) Üblicherweise wird als Startelement e das neutrale Element von f übergeben. Auf diese Weise akkumuliert sich das Ergebnis über die gesamte Liste beginnend mit dem letzten Listenelement welches von rechts mit dem "neutralen Element" verknüpft wird.
(**) ($) sei irgenteine zweistellige Verknüpfung. Da wir keine Annahme darüber machen, ob es sich um eine rechts-/oder links-assoziative Verknüpfung handelt sind die Klammern notwendig.

Die Fold-Funktionen (fold-left) / foldl

 
foldl            :: (b->a->b)->b->[a]->b
foldl f e []     =  e
foldl f e (x:xs) =  foldl f (f e x) xs
Anwendung: 
?foldl f [] [1,2,3] where f xs x = x:xs (*)
[3,2,1]
Eigenschaften: 
foldl ($) e [x1,x2,..,xn] = (..((e $ x1) $ x2)..) $ xn
(*) Here we go! reverse in einer Zeile auf der Command line reingehackert, und zudem ist es noch effizient. Lineare Laufzeitkomplexität im Vergleich zu Quadratischer bei der Implementation im vor-vorhergehdem Abschnitt.

Die Fold-Funktionen (fold-left-nonempty) / foldl1

 
foldl1          :: (a->a->a)->[a]->a
foldl1 f (x:xs) =  foldl f x xs
Anwendung: 
?foldl1 max [3,(-2),5,1] (*)
5
Eigenschaften: 
- foldl1 funktioniert nur auf nicht leeren Listen.
- foldr1 existiert äquivalent.
(*) max ist eine typische Anwendung für foldl1, da es für max (auf ganzen Zahlen) kein neutrales Element gibt, ist es nicht möglich max irgentwie sinnvoll auf die leere Liste anzuwenden. Hat man mindestens ein Element zur Verfügung kann man sich dieses allerdings schnappen und als "neutrales Element" in die foldl Funktion reinstecken.

Die Scan-Funktionen (scan-left) / scanl

 
scanl           :: (b->a->b)->b->[a]->[b]
scanl f e []    =  [e]
scanl f e (x:xs)=  e : scanl f (f e x) xs (*)
Anwendung: 
?scanl (*) 1 [1..5]
[1,1,2,6,24,120]
Eigenschaften: 
Es gibt scanr,scanl1,scanr1 mit den äquivalenten Eigenschaften der Fold-Familie.
(*) Anders als bei foldl wird bei scanl das akkumulierte Element bei jedem Zwischenschritt in der Ergebnisliste eingehängt. Die Ergebnisliste hat immer ein Element mehr als die übergebende Liste. Dieses Element ist das Element e welches bei foldl an die erste Stelle der Ergebnisliste gelangt, und bei foldr an die Letzte.

[ Gliederung ] [ Einführung ] [ Listenoperationen I ] [ Vollständige Induktion ] [ Listenoperationen II ] [ Literatur ]