Notation
|
[1,2,3] :: [Int]
['h','a','l','l','o'] :: [Char]
"hallo" :: [Char]
[[1,2], [3], []] :: [[Int]]
[(+), (*)] :: [Int -> Int -> Int]
|
|
|
Konzept
|
Listen können vollständig durch einen eigenständigen
Datentyp implementiert werden.
|
|
data List a = Nil
| Cons a (List a)
|
|---|
|
|
Cons
|
für construct
|
|
[1, 2, 3]
=
Cons 1 (Cons 2 (Cons 3 Nil))
|
|---|
|
|
Spezialsyntax
|
|
|
[1, 2, 3]
=
1 : (2 : (3 : []))
=
1 : 2 : 3 : []
|
|---|
|
|
Muster
|
für Funktionen über Listen
|
|
f :: [a] -> ...
f [] = ...
f (x : xs) = ...
|
|---|
|
|
Funktionen
|
auf Listen
|
|
|
Konkatenation
|
[1, 2, 3] ++ [4, 5]
=
[1, 2, 3, 4, 5]
|
|
|
++
|
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)
|
|
|
?
|
Laufzeit von ++ ?
|
?
|
Striktheit von ++ ?
undefined ++ ys = ???
xs ++ undefined = ???
|
Gleichheitstest
|
für Listen
|
|
instance Eq a => Eq [a] where
[] == [] = True
[] == (y : ys) = False
(x : xs) == [] = False
(x : xs) == (y : ys) = (x == y) && (xs == ys)
|
|---|
|
|
|
Definition von Ord analog.
|
null
|
Test auf leere Liste
|
|
null :: [a] -> Bool
null [] = True
null (x : xs) = False
null' x = x == []
|
|---|
|
|
?
|
Unterschied: null und null'?
|
?
|
Typ von null'?
|
|
|
Unendliche Listen
|
Beispiel
|
|
from :: Integer -> [Integer]
from x = x : from (x + 1)
|
|---|
|
|
?
|
[0] ++ from 1 = ???
from 1 ++ [0] = ???
|
|
|
concat
|
Verallgemeinerung von ++
|
|
concat :: [[a]] -> [a]
concat [] = []
concat (xs : xss) = xs ++ (concat xss)
|
|---|
|
|
reverse
|
Umdrehen Reihenfolge der Elemente in einer Liste
|
|
reverse :: [a] -> [a]
reverse [] = []
reverse (x : xs) = reverse xs ++ [x]
|
|---|
|
|
?
|
Laufzeit von reverse?
|
?
|
Laufzeitverbesserung möglich?
|
?
|
Wie?
|
|
|
Eigenschaften
|
von reverse
|
|
reverse (reverse x) = x
reverse . reverse = id
|
|---|
|
|
length
|
die Anzahl der Elemente in einer Liste
|
|
length :: [a] -> Int
length [] = 0
length (x : xs) = 1 + length xs
|
|---|
|
|
?
|
length (from 0) = ???
length [undefined, undefined] = ???
|
|
|
Eigenschaften
|
length (xs ++ ys) = length xs + length ys
|
|
|
?
|
Wozu kann dieses Gesetz genutzt werden?
|
|
|
Zugriffsfunktionen
|
|
head |
head :: [a] -> a
head (x : xs) = x
head [] = error "head with empty list"
|
tail |
tail :: [a] -> [a]
tail (x : xs) = xs
tail [] = error "tail with empty list"
|
last |
last :: [a] -> a
last (x : xs) = if null xs
then x
else last xs
last [] = error "last with empty list"
|
init |
init :: [a] -> [a]
init (x : xs) = if null xs
then []
else x : init xs
init [] = error "init with empty list"
|
|
|
?
|
Laufzeit von head, tail, last und init?
|
?
|
Speicherbedarf von head, tail, last und init?
|
|
|
Eigenschaften
|
Wann gelten diese Gesetze?
|
|
[head xs] ++ tail xs = xs
init xs ++ [last xs] = xs
|
|---|
|
|
?
|
head (from 0) = ???
tail (from 0) = ???
last (from 0) = ???
init (from 0) = ???
|
|
|
?
|
Punktfreie Definition von last und init (mit reverse)?
|
|
|
take, drop
|
Anfangsstücke und Endstücke einer Liste
|
take |
take :: Int -> [a] -> [a]
take n xs
| n <= 0 = []
take n [] = []
take n (x : xs) = x : take (n - 1) xs
|
drop |
drop :: Int -> [a] -> [a]
drop n xs
| n <= 0 = xs
drop n [] = []
drop n (x : xs) = drop (n - 1) xs
|
|
|
Eigenschaften
|
take n xs ++ drop n xs = xs
take m . take n = take (m `min` n)
drop m . drop n = drop (m + n)
take m . drop n = drop n . take (m + n)
|
|
|
Indizierter Zugriff
|
(!!) :: [a] -> Int -> a
(x : xs) !! 0 = x
(x : xs) !! n | n > 0 = xs !! (n - 1)
|
|
|
?
|
Laufzeit von !! ?
|
|
|
Funktionale Programmierung: Listen und einfache Listenfunktionen
