Funktionale Programmierung: Listen und einfache Listenfunktionen

Literatur	LYAH: An Intro to Lists
	LYAH: Texas ranges

Notation	[1,2,3] :: [Int] ['h','a','l','l','o'] :: [Char] -- = String "hallo" :: [Char] [[1,2], [3], []] :: [[Int]] [(+), (*)] :: [Int -> Int -> Int]

Konzept	Listen können vollständig durch einen selbst definierten 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	Nil = [] Cons = (:) -- rechtsassoziativ
	[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 ++ ?
	O(n) mit n = Länge 1.Argument
?	Striktheit von ++ ? undefined ++ ys = ??? xs ++ undefined = ???
	strikt im 1. Argument undefined ++ ys = undefined xs ++ undefined /= 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'?
	Unterschiedliche Typen
?	Typ von null'?
	null' :: Eq a => [a] -> Bool

Unendliche Listen	Beispiel
	from :: Integer -> [Integer] from x = x : from (x + 1)

?	[0] ++ from 1 = ??? from 1 ++ [0] = ???
	[0] ++ from 1 = from 0 from 1 ++ [0] = from 1

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?
	O(n²)
?	Laufzeitverbesserung möglich?
	Ja, auf O(n)
?	Wie?
	reverse :: [a] -> [a] reverse = reverse' [] where reverse' r [] = r reverse' r (x:xs) = reverse' (x:r) xs

Eigenschaften	von reverse
	reverse (reverse x) = x -- für alle x -- gleichwertig 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] = ???
	length (from 0) = undefined length [undefined, undefined] = 2

Eigenschaften	length (xs ++ ys) = length xs + length ys

?	Wozu kann dieses Gesetz genutzt werden?
	automatische Tests Compiler Optimierung

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 : []) = x last (x : xs) = last xs last [] = error "last with empty list"
init	init :: [a] -> [a] init (x : []) = [] init (x : xs) = x : init xs init [] = error "init with empty list"

?	Laufzeit von head, tail, last und init?
	head: O(1) tail: O(1) last: O(n) init: O(n)
?	Speicherbedarf von head, tail, last und init?
	head: O(1) tail: O(1) last: O(1) init: O(n)

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) = ???
	head (from 0) = 0 tail (from 0) = from 1 last (from 0) = undefined init (from 0) = from 0

?	Punktfreie Definition von last und init (mit reverse)?
	last = head . reverse init = reverse . tail . 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 !! ?
	O(n), nicht konstant!