Seminare 4 und 5

Dateiinhalt

----------------------------------------------------------------------
--
--  Seminar Theoretische Informatik 
--  "Funktionale Programmierung mit Haskell"
--  Universität Potsdam SS 2014
--  Tim Richter / Mario Frank
--  Kapitel 4: Listen
----------------------------------------------------------------------


Übersicht
---------
0) Importe 
1) Erzeugung von Listen
2) Operatione auf Listen
3) Map- und  Filter-Funktionen
4) Zip-Funktionen
5) Fold und Scan
6) Zusammenhänge und Gesetze
7) Anwendungsbeispiel: Maximum Segment Sum


0)   Importe

> module Listen where
> import Prelude 
> import Debug.Trace
> import System.Random

1) Listen
---------
Listen werden in der Informatik benutzt um viele Elemente 
des gleichen Typs zu verwalten bzw. unter einem gemeinsamen 
Bezeichner zusammenzufassen.

In Haskell sind Listen als rekursiver Datentyp wie folgt definiert:

> data List a = Nil | Cons a (List a)
>  deriving (Eq, Ord, Show)

Der Übersicht halber hat sich allerdings eine Kompaktere schreibweise 
durchgesetzt:
 
(Cons 1 (Cons 2 (Cons 3 Nil))) -> 1:2:3[]-> [1,2,3]

Natürlich kann man die Orientierung auch umkehren:

(Snoc (Snoc (Snoc Nil 1) 2) 3)

Ist der Datentyp den List enthält in Eq bzw. Ord kann man 
Eq und Ord auf Listen definieren:

< instance (Eq a) => Eq (List a) where
<  Nil			== Nil		= True
<  Nil			== Cons y ys	= False
<  Cons x xs	== Nil 			= False
<  Cons x xs	== Cons y ys	= (x == y) ^ (xs == ys)
<  
< instance (Ord a) => Ord (List a) where
<  Nil			> Nil		= False
<  Cons x xs	> Nil			= True
<  Nil			> Cons y ys		= False
<  Cons x xs	> Cons y ys		= (x > y) || (xs > ys)
<  
< null :: List a -> Bool
< null [] = True
< null (x:xs) 0 False
 
 
2) Funktionen auf Listen
------------------------

Um mit Listen vernünftig umgehen zu können braucht man einige Funktionen,
zum Beispiel:

Eine Funktion um zwei Listen miteinander zu verknüpfen
 
> concatenate'				:: List a -> List a -> List a
> concatenate' Nil ls 			= ls
> concatenate' (Cons x xs) ls	= Cons x (concatenate' xs ls)

Eine Funktion um die Elemente einer zweidimensionalen Liste zu verknüpfen
 
> concat' 			:: List(List a) -> List a
> concat' Nil 				= Nil
> concat' (Cons xs xss)		= concatenate' xs (concat' xss)

Eine Funktion um die Reihenfolge der Elemente umzukehren

> reverse' 			:: List a -> List a
> reverse' Nil				= Nil
> reverse' (Cons x xs)		= concatenate' (reverse' xs) (Cons x Nil)

Eine Funktion um die Länge einer Liste zu bestimmen

> length' 			:: List a -> Int
> length' Nil				= 0
> length' (Cons _ xs)		= 1 + length' xs

Funktionen um auf die verschiedenen Teile einer Liste zuzugreifen

> head' 		:: List a -> a
> head' (Cons x _) 		= x

> tail 		:: List a -> List a
> tail (Cons _ xs)		= xs

> last' 			:: List a -> a
> last' (Cons x Nil)				= x
> last' (Cons x (Cons y ys))	= last' (Cons y ys)

> init'		:: List a -> List a
> init' (Cons x Nil)	= Nil
> init' (Cons x (Cons y ys)) = (Cons x (init' (Cons y ys)))

> take'		:: Int -> List a -> List a
> take' 0 _			= Nil
> take' n Nil			= Nil
> take' n (Cons x xs)		    = (Cons x (take' (n-1) xs))

> drop' 	:: Int -> List a -> List a
> drop' 0 xs			= xs
> drop' n Nil			= Nil
> drop' n (Cons x xs)		    = drop' (n-1) xs

Eine Funktion um eine Liste in zwei aufzuteilen

> splitAt'					:: Int -> List a -> (List a, List a)
> splitAt' 0 xs				= (Nil, xs)
> splitAt' n Nil				= (Nil, Nil)
> splitAt' n (Cons x xs)		= ((Cons x ys), zs)
>						 where (ys, zs) = splitAt' (n-1) xs

Eine Funktion um auf ein bestimmtes Element in der Liste zuzugreifen

> getElement'				:: Int -> List a -> a
> getElement' 0 (Cons x xs)	= x
> getElement' n (Cons x xs)	= getElement' (n-1) xs




3) Map, Filter und Listcomprehension
------------------------------------
    Hilfsfunktionen


> nodups    ::(Eq a) => [a] -> [a]
> nodups [] = []
> nodups (x:xs) = x : nodups [ y | y <- xs, y /= x ]

> quicksort :: (Ord a) => [a] -> [a]  
> quicksort [] = []  
> quicksort (x:xs) =   
>    let smallerSorted = quicksort [a | a <- xs, a <= x]  
>        biggerSorted = quicksort [a | a <- xs, a > x]  
>    in  smallerSorted ++ [x] ++ biggerSorted
    
hasNoFactors:

> hasNoFactors :: Integer -> [Integer] -> Bool
> hasNoFactors n = foldr (\f r -> f*f > n || (rem n f /= 0 && r)) True  


isPrime

> isPrime	:: Integer -> Bool
> isPrime z
> 	| z <1 = error "This function is only defined on positive Numbers."
> 	| z==1 = False
> 	| z==2 = True
> 	| otherwise =  hasNoFactors z [2..n ]
>	 where n = floor (sqrt (fromIntegral z))

Zusammenhang von map und concat:
    *****************************************
    * map f . concat = concat . map (map f) *
    *****************************************
    
Mit Typ (a -> b) -> [[a]] -> [b]    
	
Listcomprehension

Listcomprehensions haben folgende Grundstruktur
(können jedoch wesentlich komplexer aufgebaut sein):
  **********************************************  
  * [e | e <- p , g ]                          *
  *      e:      Haskell-Ausdruck (Expression) *
  *      e <- p: Ein Generator für e           *
  *      g:	     Guards, Filter                *
  **********************************************      

Listcomprehensions am Beispiel Primzahlen       
isPrime mittels Listcomprehension:

> isPrimeL :: Integer -> Bool
> isPrimeL n
>       | n > 1     = [] == [x | x<-[2..m], n `mod` x == 0] 
>       | n < 1     = error "isPrimeL is only defined on positive Numbers."
>       | otherwise = False
>         where m   = floor (sqrt (fromIntegral n))

Der "isPrime"-Test lässt sich natürlich ebenfalls leicht zum generieren einer Liste einsetzen:

> makePrimeList1	:: Integer -> [Integer]
> makePrimeList1 n = [x |x<-[1..n], isPrime x ]

Bauen wir das aus zu Tupeln von Primzahlzwillingen:
makePrimeTwinsList, erster Versuch

> makePrimeTwinsList1	::	Integer -> [(Integer,Integer)]
> makePrimeTwinsList1 b = [(n,m)|n<-[1..b],m<-[1..b],isPrime n,isPrime m,(m-n)==2 ]

Schlechte Laufzeit, daher:

> makePrimeTwinsList2	::	Integer -> [(Integer,Integer)]
> makePrimeTwinsList2 b = [(n,n+2)|n<-[1,3..b],isPrime n,isPrime (n+2)]

Schon besser, jetzt mit dem verbesserten isPrime-Test:

> makePrimeTwinsList	::	Integer -> [(Integer,Integer)]
> makePrimeTwinsList b = [(n,n+2)|n<-[1,3..b],isPrimeL n,isPrimeL (n+2)]


4) Die zip- und unzip-Funktionen
     ----------
Die zip-Funktionen nehmen Listen entgegen und verarbeiten diese zu einer Liste von Tupeln,
in denen jeweils die Elemente mit gleichem Index der Ausgangslisten miteinander vertupelt werden.
zip nimmt zwei Listen entgegen und verarbeitet diese zu Tupeln, zip3 nimmt drei Listen.
Die Definition von zip ist recht simpel:

  ******************************************
  * zip :: [a] -> [b] -> [(a,b)]	         *
  * zip (a:as) (b:bs) = (a,b) : zip as bs  *
  * zip _      _      = []		             *
  ******************************************

  
Ein Beispiel für die Anwendung von zip3 und eines für die Anwendung von unzip3:

> w = zip3 "AE NE" "LRESI" "BTITN"
> tt = [('S','i','w'),('c','s','e'),('h','t','i'),('n',' ','s'),('e',' ','s'),('e',' ',' ')]

Dabei ist jedoch zu beachten, dass unzip (bzw. unzip3) die Ergebnislisten in Tupelform zurückgibt.
zip kann leicht ausgebaut werden zur Verarbeitung von mehr als zwei bzw. drei Listen.


5)  Die fold-Funktionen:
    --------------------
Neben Map und Filter ist der Fold-Operator einer der mächtigeren 
Operationen auf Listen.

Eine Funktion der Form

< func :: List a -> a
< func []     = e
< func (x:xs) = x # func xs     

kann sehr einfach als fold-funktion umgesetzt werden

< func = fold (#) e

Dabei steht (#) für einen Operator auf a und e (meist) für das neutrale Element von a

Fold ersetzt den Cons-Operator (:) mit (#) und [] mit e:

1:2:3:4:[] -> 1(#)2(#)3(#)4(#)e

Als Beispiel die sum-funktion:

< sum :: Num a => List a -> a
< sum []     = 0
< sum (x:xs) = x + sum xs

< sum = foldr (+) 0

foldr bedeutet 'fold right' und klammert den resultierenden Ausdruck rechtsassoziativ

1:2:3:4:[] -> (1 + (2 + (3 + (4 + 0)))) = 10

dementsprechend existiert auch ein foldl ('fold left')

1:2:3:4:[] -> ((((0 + 1) + 2) + 3) + 4) = 10

foldr und foldl werden wie folgt definiert:

< foldr :: (a -> b -> b) -> b -> [a] -> b
< foldr f e []     = e
< foldr f e (x:xs) = f x (foldr f e xs)

< foldl :: (b -> a -> b) -> b -> [a] -> b
< foldl f e []     = e
< foldl f e (x:xs) = foldl (f e x) xs

> decimal :: [Int] -> Int
> decimal = foldl horner 0
>			 where horner n x = 10*n + x 

	decimal [5,2,3]
=	foldl horner 0 					 [5,2,3]
=	foldl horner (10*0 + 5) 			 [2,3]
=	foldl horner (10*(10*0 + 5) + 2) 		 [3]
=	foldl horner (10*(10*(10*0 + 5) + 2) + 3)	 []
= 	(10*(10*(10*0 +5) + 2) + 3) = 523


Es gibt noch eine weitere definition von fold:

Problem: Eine Funktion die das größte Element einer Liste finden soll

< maxlist :: Ord a => List a -> a
< maxlist = foldr (max) e

Welcher Wert soll für e gewählt werden?

Die fold-Varianten liefern eine Alternative für solche Fälle:

< foldr1 :: (a -> a -> a) -> [a] -> a
< foldr1 f (x:xs) = if null xs then x else f x (foldr1 f xs)

< foldl1 :: (a -> a -> a) -> [a] -> a
< foldl1 f (x:xs) 0 if null xs then x else foldl f x xs

Fold mit Trace-Ausgabe

> foldr'            ::(Show a, Show b ) => (a -> b -> b) -> b -> [a] -> b
> foldr' f acc []     =  trace (show acc) $ acc
> foldr' f acc (x:xs) =  (traceShow xs) $ f x (foldr' f acc xs)



> foldl'            :: (Show a, Show b ) =>  (a -> b -> a) -> a -> [b] -> a
> foldl' f acc []     =   trace (show acc) $ acc
> foldl' f acc (x:xs) =  (traceShow xs) $  foldl' f (f acc x) xs



5.2)  Die scan-Funktionen
        -------------------
Die Segmente einer Liste sind die einzelnen Teilfolgen aufeinanderfolgender Elemente.
Z.B. sind die Segmente der Liste [1,2,3,4] die Folgenden:
[[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4],[]]
Die Initialsegmente davon sind:
[[],[1],[1,2],[1,2,3],[1,2,3,4]]
und die Tail-Segmente:
[[1,2,3,4],[2,3,4],[3,4],[4],[]]
Die scan-Funktionen sind ähnlich den fold-Funktionen, jedoch werden nicht die einzelnen
Elemente, sondern die Segmente einer Liste verarbeitet.
Wie bei den fold-Funktionen gibt es auch bei den scan-Funktionen wiederum Right- und Left-Versionen.
scanr verarbeitet die Tailsegmente, scanl die Initialsegmente
Z.B. lässt sich map sum . inits mittels scanl folgendermaßen darstellen:

    **********************************
    * scanl (+) 0 =  map sum . inits *
    **********************************

Die scanl-Implementierung aus Prelude (mit zusätzlichen Trace-Ausgaben):

> scanl'   :: (Show a, Show b) => (b -> a -> b) -> b -> [a] -> [b]
> scanl' f q ls  = (traceShow ls) $ q : (case ls of
>                                 []   -> []
>                                 x:xs ->   scanl'  f (f q x) $(traceShow ls)$ xs)


6) Gesetze mit Fold
-------------------

Die sogenannten 'duality theorems' beschreiben Gesetze die sich mit den
Beziehungen zwischen foldr und foldl beschäftigen

First duality theorem:

Sei (#) ein assoziativer Operator mit (links- und rechts-) neutralem Element e.
Dann gilt:


  **************************************************
  *  foldr (#) e xs = foldl (#) e xs		           *
  **************************************************
 


Second duality theorem:

Wenn zwei Operanden (#) und (~) und e für alle x, y und z folgende 
  Bedingungen erfüllen

  (x (#) y) (~) z 	= x (#) (y (~) z)
   x (#) e			= e (~) x
   
dann gilt:

  **************************************************
  * foldr (#) e xs = foldl (~) e xs		             *
  **************************************************
 
  
Das kann auf den ersten Blick etwas verwirrend sein deswegen illustrieren 
wir das an einem Beispiel:

Die Funktion reverse:

< reverse = foldr snoc [], where snoc x xs = xs ++ [x]
< reverse = foldl cons [], where cons xs x = x : xs

Third duality theorem:
  *************************************************
  * foldr f e xs = foldl (flip f ) e (reverse xs) *
  *************************************************


6.2) Fold-Fusion
----------------
Fold-map Fusion:
  *******************************************
  * (foldr f a) . (map g) = foldr (f . g) a *
  *******************************************
  
Fold-concat Fusion:
 **************************************************
 * (foldr f a) . concat = foldr (flip(foldr f)) a *
 **************************************************
  
Zusammenhänge der scan-, fold- und map-Funktionen:
    ***************************************
    * scanr f e = map (foldr f e) . tails *
    * scanl f e = map (foldl f e) . inits *
    ***************************************

6.5) Bookkeeping Law:
    *****************************************************
    * foldr f a . concat = foldr f a . map (foldr f a ) *
    * z.B.: sum . concat = sum . map sum                *
    * oder: maximum . concat = maximum . map maximum    *
    *****************************************************
Das Bookkeeping-Law lässt sich anwenden, wenn die Argumente
von foldr eine assoziative Operation und deren neutrales Element sind.
 
    
6.6) Fold-Scan-Fusion Law
    ******************************************
    * foldr1 (+) . scanl (*) 1 = foldr (o) 1 *
    * (mit x o y = 1 + x*y )                 *
    ******************************************
Beispiel
1+x0 + x0*x1+x0*x1*x2 = 1+x0(1+x1(1+x2))
= foldr1 (+) . scanl (p) 1 where p x y = 1+x*y
    
    
7) Maximum Segment Sum
--------------------------
Zu ermitteln ist die maximale Summe von hintereinander liegenden Teilfolgen
aus einer gegebenen Liste von Integer-Zahlen.
Z.B. für die Folge [2,-3,40,-4,50,-1] ist [40,-4,50] das
maximale Segment, die Summe 86.
Oder [-159,110,-28,-37,68,46,91,32,45,101,113,-73,-186,-162,-123,-192,-189,-79,-175,-158,-199,4,127,-38,-50,-36,82,-188]
mit ([110,-28,-37,68,46,91,32,45,101,113],541)


Hilfsfunktionen tails und inits:

> tails	:: [a] ->[[a]]
> tails = foldr f [[]]
>		where f x xss = (x : head xss) : xss
> inits	:: [a] ->[[a]]
> inits = foldr f [[ ]]
>		where f x xss = [ ] : map (x :) xss


Hilfsfunktion zur Erzeugung der Sequenzen (werden für die reine Summenbildung nicht benötigt):

> getSequences	:: [a ] -> [[a ]]
> getSequences = concat . map inits . tails

> getUniqSequences :: [Integer] -> [[Integer]]
> getUniqSequences = nodups . getSequences 


Hilfsfunktion zur Erzeugung der Summen, realisiert durch foldl
(ist in Prelude aber bereits als "sum" vorhanden)

> listSum	:: [Integer] -> Integer
> listSum = foldl (+) 0	


Die eigentliche MSS-Funktion

> mss' :: [Integer] -> Integer
> mss' = maximum . map listSum . getSequences

Der Aufbau der Sequenzliste ist jedoch langsam, da n^2 Segmente entstehen 
und über diese summiert wird, daher kubische Laufzeit
Daran lässt sich einiges verbessern, nehmen wir die Funktion dazu auseinander:
====================================================
== maximum . map sum . concat . map inits . tails ==
====================================================
Aus dem Zusammenhang map f . concat = concat . map (map f)
können wir dies umformen zu
==========================================================
== maximum . concat . map (map sum) . map inits . tails ==
==========================================================

Dies lässt sich nun weiter umformen mittels der Regel
map (f . g) = map f . map g zu:
======================================================
== maximum . concat . map (map sum . inits) . tails ==
======================================================

Mittels Bookkeeping-Law foldr f a . concat = foldr f a . map (foldr f a ),
hier in der Form maximum . concat = maximum . map maximum

Die letztgenannten zwei Umformungen sind bei Bird zu einem Schritt zusammengefasst.

lässt sich dies weiter umformen, der Term maximum . concat
lässt sich ersetzen durch maximum . map maximum
===========================================================
== maximum . map maximum . map (map sum . inits) . tails ==
===========================================================

map sum . inits lässt sich durch scanl ersetzen:
========================================================
== maximum . map (maximum . scanl (+) 0 ) . tails     ==
========================================================
Das lässt sich weiter umarbeiten, wir benötigen jedoch
noch die untere Grenze, die aufgrund des Vorhandenseins
der leeren Liste 0 ist.

> p :: (Num a, Ord a) => a -> a -> a
> p x y = max 0 (x+y)

Da maximum = foldr1 (max) ist
und sich + distributiv zu max verhält, lässt sich das
Fold-Scan-Fusion Law anwenden, das zu folgenden Ergebnis führt:
=====================================================
== maximum . map (foldr (p) 0) . tails             ==
=====================================================

Damit noch nicht genug: Denn der Term "map  (foldr (p)0) . tails"
lässt sich durch scanr (p) 0 ersetzen.
Das führt zu einer mss-Funktion mit linearer Laufzeit,
jedoch nur für die eigentliche Summe (die Sequenz selbst wird dabei nicht ausgegeben).

    *******************************
    * mss = maximum . scanr (p) 0 
    *******************************
    
> mss :: [Integer] -> Integer
> mss = maximum . scanr (p) 0

Erzeugung einer Liste mit Tupeln der Sequenzen zusammen mit der jeweiligen Sequenzsumme 

> getSumTupelsFromSequences :: Num t => [[t]] -> [([t], t)]
> getSumTupelsFromSequences l = [(x,sum x)|x<-l ]

Zur Erzeugung einer SumTupel-Liste direkt aus einer Integer-Liste lassen sich 
die beiden Funktionen ganz einfach (mittels Funktionskomposition) verbinden:

> getSumTupels = getSumTupelsFromSequences . getSequences

Extrahieren einzelner Tupel

> getX ([],x)  = x 
> getX ((y:ys),x)  = x 
		  		  
> getTupel [] _ = ([],0)
> getTupel (x:xs) n = if getX x == n then x else getTupel xs n

Einige weitere nützliche Kompositionen:

> getSumTupelFromIntegerList	:: [Integer] -> Integer -> ([Integer], Integer)
> getSumTupelFromIntegerList =  getTupel . getSumTupels

> getLargestTupel	::  [Integer] -> ([Integer], Integer)
> getLargestTupel x = getSumTupelFromIntegerList x (mss x)

Daten zum testen

> z1 = getSumTupels [1..10]
> z2 = [2,-3,40,-4,50,-1]
> makeRandIntListFromTo   :: Integer -> Integer -> Int -> Int -> [Integer]
> makeRandIntListFromTo u o n s =  take n (randomRs (u,o)  (mkStdGen s ) )::[Integer ]
> makeRandIntListTo   :: Integer -> Int -> [Integer]
> makeRandIntListTo o n =  take n (randomRs (0,o)  (mkStdGen 45 ) )::[Integer ]