Listen in Haskell - Einfache Listenoperationen

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

Gliederung: Einfache Listenoperationen

Konkatenation I / (++)

(++)       :: [a]->[a]->[a]
[]++ys     =  ys
(x:xy)++ys =  x:(xs++ys)

Anwendung:

?“Hello“++“World“
“HelloWorld“

Eigenschaften:

Assoziative Operation mit neutralem Element []. (*)

(*) Also z.B.: [1,2]++[]=[1,2].

Konkatenation II / concat

concat          :: [[a]]->[a]
concat[]        =  []
concat(xs:xss)  =  xs ++ concat xss

Anwendung:

?concat [“Hello“,“ “,“World“]
“Hello World“

Eigenschaften:

concat(xss++yss) = concat xss++concat yss

Umdrehen / reverse

reverse        :: [a]->[a]
reverse[]      =  []
reverse(x:xs)  =  reverse xs ++ [x]  (*)

Anwendung:

?reverse [1,2,3]
[3,2,1]

Eigenschaften:

reverse (reverse xs) = xs [für alle endlichen Listen xs] (**)

(*) Diese Implementation hat ein Problem: Da für eine Liste der Länge n n mal (++) ausgewertet wird, und (++) selbst eine lineare Laufzeitkomlexität hat, ist O(n)=n^2. Wir werden noch eine effizientere (lineare Laufzeitkomplexität) Implementation kennen lernen.
(**) Diesen Satz werden wir beispielhaft für die Implementationen von reverse und (++), die wir hier kennengelernt haben, beweisen.

Länge ermitteln / length

length       :: [a]->Int
length[]     =  0
length(x:xs) =  1 + length xs

Anwendung:

?length “Text“
4

Eigenschaften:

- length(xs++ys) = length xs + length ys
- lineare Laufzeitkomplexität

Index-Zugriff / (!!)

(!!)          :: [a]->Int->a
(x:xs)!!0     =  x
(x:xs)!!(n+1) =  xs!!n

Anwendung:

?“Text“!!0
‘T‘

Eigenschaften: (*)

- Indexierung beginnt mit 0
- lineare Laufzeit

(*) Programmierer, die in imperativen Sprachen viel mit Arrays gearbeitet haben, könnten versucht sein, Listen in Haskell mit "until", "length" und (!!) wie Arrays zu verarbeiten. In funktionalen Sprachen ist dieses Vorgehen allerdings weder idiomatisch, noch geschickt, da length und (!!) eine lineare Laufzeitkomplexität haben (nicht konstant wie bei Arrays in imperativen Sprachen). Meistens finden sich elegantere Lösungen, die ohne length und (!!) auskommen.

Die ersten i Elemente einer Liste nehmen / take

take             :: Int -> [a] -> [a]
take 0 xs        =  []
take (n+1)[]     =  []
take (n+1)(x:xs) =  x:take n xs

Anwendung:

?take 5 “Wurstbrot“
“Wurst“

Eigenschaften:

Wenn i>=length xs dann: take i xs = xs

Die ersten i Elemente einer Liste entfernen / drop

drop             :: Int -> [a] -> [a]
drop 0 xs        =  xs
drop (n+1)[]     =  []
drop (n+1)(x:xs) =  drop n xs

Anwendung:

?drop 5 “Wurstbrot“
“brot“

Eigenschaften:

take n xs ++ drop n xs = xs (*)

(*) Für alle nicht-negativen n. Für sehr große n (> length xs) ist take n xs = xs und drop n xs=[].

Eine Liste an Position i zerteilen / splitAt

splitAt       :: Int->[a]->([a],[a])
splitAt n xs  =  (take n xs, drop n xs)

Anwendung:

?SplitAt 5 “Wurstbrot“
(“Wurst“, “brot“)

Eigenschaften:

Tatsächliche Implementation effizienter als die hier Angegebene, kommt mit einer Traversierung aus (hier:2).

Listen aus Intervallen von Ordinaltypen erzeugen / [n..m]

[m..n]
[m..] (*)

Anwendung:

?[‘A‘..‘Z‘]
“ABCDEFGHIJKLMNOPQRSTUVWXYZ“
?[‘Z‘..‘A‘]
““
?take 5 [1..] (**)
[1,2,3,4,5]

(*) Für Elementtypen mit begrenztem Wertebereich ist [m..] = [m..maxBound], also z.B. ['\0'..] = ['\0'..'\255'] oder [False..] = [False, True].
(**) Hier sehen wir den Effekt der Lazy-Evaluation. Da take nur die ersten 5 Elemente der unendliche Liste [1..] benötigt, werden auch nur diese berechnet. Der Ausdruck kann also (mindestens) so effizient ausgewertet werden, wie take 5 [1..5].

Reißverschluss / zip

zip              :: [a]->[b]->[(a,b)]
zip [] ys        =  []
zip (x:xs)[]     =  [] (*)
zip (x:xs)(y:ys) =  (x,y):zip(xs,ys)

Anwendung:

?zip [1..] “Text“
[(1,‘T‘),(2,‘e‘),(3,‘x‘),(4,‘t‘)]

Eigenschaften:

length(zip xs ys)=min(length xs)(length ys) (**)

(*) Es mag überaschend erscheinen, daß die Definition zip (x:xs) [] = [] anstelle von zip xs [] = [] verwendet wurde. Diese Definition folgt aber dem Idiom, die linken Seiten der Definitionsgleichungen einer Funktion disjunkt zu gestalten. Hier wird also explizit klargestellt, daß der Fall zip [] [] in der ersten, und nicht in der zweiten Definitionsgleichung behandelt wird.
Disjunkte Definitionsgleichungen erleichtern auch Beweise, weil man nicht aufpassen muss in die richtige Gleichung einzusetzen, wenn es nur eine Mäglichkeit gibt.
In Haskell wird bei Mehrdeutigkeit immer die erste zutreffende Definition ausgewertet.

Illustration:

last :: [a]->a
last (x:xs) = last xs
last [x] = x

Ups! Hier wird das Rekursionsende niemals erreicht, da auch im Falle einer einelementigen Liste (x:[]) die erste Definition verwendet wird.

Lösung:

last :: [a]->a
last (x1:x2:xs) = last (x2:xs)
last [x] = x

(**) Ist eine der beiden Listen länger, werden die überzähligen Elemente dieser Liste nicht berücksichtigt.

Reißverschluss öffnen / unzip

unzip            :: [(a,b)]->([a],[b])
unzip            =  pair(map fst,map snd) (*)

Anwendung:

?unzip[(1,‘E‘),(2,‘i‘)]
([1,2],“Ei“)

Eigenschaften:

zipp (unzip xys)=xys
[zipp ist die uncurried-Version von zip]

(*) Diese Implementation greift voraus. Wir werden im Abschnitt "Listenoperationen II" sehen, wie die Funktion map arbeitet, und wann man sie benutzen kann.

weitere Listenoperationen

head :: [a] -> a   -- xs!!0

tail :: [a] -> [a] -- ~“drop 1 xs“ (*)

last :: [a] -> a   -- letztes Element

init :: [a] -> [a] -- “pop_back“ (**)

(*) "tail xs" ist nur ungefähr gleich "drop 1 xs", da "tail [] = undefined" und "drop 1 [] = []".
(**) Ich finde den Begriff init zum Entfernen des letzten Elementes einer Liste gewöhnungsbedürftig. In imperativen Sprachen heisst diese Operation für gewöhnlich pop_back.

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