Organisatorisches

Wo gehen wir Mittagessen?
Wollen wir heute abend etwas trinken/essen gehen?

Die Zimmer können in der Mittagspause bezogen werden. Schlüssel im iPunkt.

Gedanken zu Fortbildungen

Ruhe keine Schüler, kein hektisches Lehrerzimmer
Gedankenaustausch interessante Gespräche, nette Kolleginnen und Kollegen mit ähnlichen Interessen
Freiheit kein Druck, etwas abliefern zu müssen
Zeit Ausprobieren, wozu wir sonst keine Zeit haben
Anregungen Neue Ideen mitnehmen

Meine Erwartungen an Euch

Das funktionale Paradigma
mit Haskell


Marc Alexander Domay


12. und 13. November 2018


am PL in Speyer

Übersicht

12. November

1 Organisatorisches, Einführung, Beispiele
2 Erste Schritte, ghci, Grundlagen, Syntax, Übungen
Mittagessen :-)
3 Typen, grundl. Konzepte, Listen, Tupel, Übungen
4 Funktionstypen, Curried Functions, Polymorphe Typen, Übungen

13. November

1 Wiederholung, Klassen, Fkt.Definitionen, Guarded Equations, Quicksort, Lambda-Expressions, Übungen
2 List Comprehensions, Guards, zip, String Comprehensions, Cäsar-Verschl., Übungen
Mittagessen :-)
3 Rekursion, Rek. über Listen, Entwurf von Rekursionen, Übungen
4 Zusammenfassung, Ausblicke, vertiefende Übungen, Feedback

Einführende Beispiele

Einführende Beispiele

Liste mit Quadratzahlen

Python


squares = []
for i in range(n):               # 0 <= i < n 
   squares.append( (i+1)*(i+1) ) # man muss daran denken
print(squares) 

					
Haskell

squares n = [ x^2 | x <- [1..n] ]
 

					

pythagoräische Tripel

( 3, 4, 5 ), (6,8,10), (5,12,13), ...

pyths n = [ (x,y,z) |  
	z <- [3..n], 
	x <- [3..z], 
	y <- [x..z], 
	x^2 + y^2 == z^2 ]
					

Primzahlen

Primzahlen sind Zahlen, die nur die Teiler 1 und sich selbst haben, oder anders formuliert, Zahlen deren Teilermenge genau zwei Elemente enthält.


teiler n = [x | x <- [1..n], n `mod` x == 0 ]
					

istprim n = length (teiler n) == 2
					

primzahlenkleiner n = [x | x <- [1..n], istprim x  ]
					

perfekte Zahlen

Perfekte Zahlen sind Zahlen, die gleich der Summe all ihrer Teiler (ohne die Zahl selbst) sind.
z.B.: 6 = 1+2+3 oder 28 = 1+2+4+7+14


istperfekt n = (n == sum (init (teiler n))

perfektekleiner n = [x | x <- [1..n], istperfekt x ] 

					

... dann installieren wir mal ...

https://www.haskell.org/

Grundlegende Haskell Syntax

Grundlegende Haskell Syntax

Mathematische Ausdrücke, Operatoren

  • Die Operatoren haben die mathematische Ausführungsreihenfolge.
  • Die Exponentiation bindet nach rechts,
  • alle anderen Operationen binden nach links.

 Prelude> 2+3*4 
 14 
 Prelude> (2+3)*4 
 20 
 Prelude> sqrt (3^2 + 4^2) 
 5 
					

Funktionsanwendung

Der Ausdruck
$$ f(a,b) + cd $$ wird in Haskell so geschrieben:


 Prelude> f (a,b) + c*d   -- geht beides.  Das ist ein subtiler,
 Prelude> f a b + c*d     -- aber entscheidender Unterschied.
					

Die Anwendung von Funktionen bindet stärker als alles andere.

Funktionsanwendung

Mathematisch in Haskell
$$ f(a,b) + cd $$

			 f a b + c*d  
			
$$ f(g(x))$$

			 f (g x) 
			
$$ f(x, g(y))$$

 			 f x (g y) 
			
$$ f(x) \cdot g(y)$$

			 f x * g y  
			

Haskell Standard Prelude

Haskell hat im Standard Prelude ein ganze Menge Funktionen eingebaut.

Listen werden wie in Python mit eckigen Klammern notiert. Die Listenelemente werden mit Kommas getrennt.


 Prelude> head [1,2,3,4,5] 
 1 
					

 Prelude> tail [1,2,3,4,5] 
 [2,3,4,5] 

 Prelude> [1,2,3,4,5] !! 2 
 3         -- der Index fängt bei 0 an

 Prelude> take 3 [1,2,3,4,5] 
 [1,2,3] 

 Prelude> drop 3 [1,2,3,4,5] 
 [4,5] 
					

 Prelude> length [1,2,3,4,5] 
 5 

 Prelude> sum [1,2,3,4,5] 
 15 

 Prelude> product [1,2,3,4,5] 
 120 

 Prelude> [1,2] ++ [4,5,6] 
 [1,2,4,5,6] 

					

Die Dokumentation zum Standard Prelude kann man hier einsehen:
https://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude.html

Haskell Programme

Haskell Programme sind gespeicherte Funktionsdefinitionen

Haskell Dateien haben die Endung beispiel.hs

Schlüsselwörter:


					case      class     data         default     deriving
					do        else      foreign      if  in      import 
					infix     infixl    infixr       instance    let
					module    newtype   of   then    type        where
				

Wir dürfen die Schlüsselwörter nicht als Namen verwenden.

Texteditor ghci

Listenargumente werden in Haskell gerne mit dem Suffix 's' versehen.

Haskell Namen beginnen mit Kleinbuchstaben und dürfen '_', Ziffern, Groß- und Kleinbuchstaben und einfache Hochkommas (:-O) enthalten.

 
				ns = [1,2,3]      -- ok, Name folgt der Konvention 's' anhängen
				arg_2             -- ok
				Number            -- nicht ok, beginnt mit Großbuchstaben.
				f                 -- ok
				f'                -- ok
				f''               -- ok
				myFun             -- ok
				

Kommentare werden so ausgezeichnet:

 
				-- ein einzeiliger Kommentar 

				{- erste Zeile Kommentar 
				   zweite Zeile Kommentar 
				   dritte Zeile Kommentar -} 
				

Tabulatorzeichen im Editor können Probleme verursachen. Die Layout-Regel:

 
				a = b + c 
				    where 
				        b = 1      -- lokale Definition im Body von a
				        c = 2      -- lokale Definition im Body von a
				d = a * 2          -- auf derselben Ebene wie a
				                   -- nicht mehr im Body von a

				-- oder in einer Zeile: 
				a = b + c where {b=1; c=2};d = a * 2 -- viel schlechter lesbar
				

Whitespace hat in Haskell wie in Python semantische Bedeutung.

... jetzt ihr ...

  1. Vollziehe die Beispiele selbst nach und probiere einfach mal aus.
  2. Finde die drei Syntaxfehler:
     
    				N = a `div` length xs
                where
                   a = 10
                  xs = [1,2,3,4,5]
    				
  3. Baue die Funktion 'last' nach, die das letzte Element einer Liste zurückliefert.
  4. Die Funktion 'init' entfernt das letzte Element einer Liste. Baue 'init' auf zwei Arten nach.

Typen

Werte und ihre Typen

Ein Typ ist eine Sammlung verwandter Werte.

Beispiele:

 
					-- Typ  Bool 
					True  :: Bool 
					False :: Bool 
					

 
					-- Funktionstyp  Bool -> Bool 
					not :: Bool -> Bool
					

Typ-Inferenz

Jeder Ausdruck muss einen Typ haben.

Der Typ eines Ausdrucks wird vor der Evaluation abgeleitet oder berechnet.


					 f :: A -> B       e :: A 
					---------------------------
					         f e :: B 
					

ghci :type

Der Typ eines beliebigen Ausdrucks kann in ghci leicht abgerufen werden:



prelude> :type True 
True :: Bool 

prelude> :type not 
not :: Bool -> Bool 

					

Das hilft bei der Fehlersuche und beim Verständnis.

Bool

			True, False
			
Char

			'a', '0', '_', ...
			
String

			"haskell", "1+2=3", ...
			
Int

			-2^63 .. 2^63 -1
			
Integer

			-- arbitrary precision Integers
			
Float, Double

			-- 32/64 Bit IEEE 754 Fließkommazahlen
			

Eine Liste ist eine Folge von Elementen desselben Typs in eckigen Klammern.



 [False,False,True] ::  [Bool] 

 ['a','b','c','d'] ::  [Char] 

 ["Eins","Zwei","Drei"] ::  [String] 

 length ["Eins","Zwei","Drei"]  -- die Anzahl der Elemente
 3 

					

Ein Tupel ist eine Folge von Komponenten möglicherweise verschiedenen Typs. Die Anzahl der Komponenten heißt Arität (arity).



 (False,True) ::  (Bool,Bool) 

 (False,'a',True) ::  (Bool,Char,Bool) 

 ("Yes",True,'a') ::  (String,Bool,Char) 

-- komplexere Tupeltypen: 
 ("Yes",(True,'a')) ::  (String,(Bool,Char)) 

 (['a','b'],[False,True]) ::  ([Char],[Bool]) 

 [('a',False),('b',True)] ::  [(Char,Bool)] 


					

... jetzt ihr ...

  1. Vollziehe die Beispiele selbst nach und probiere einfach mal aus.
  2. Was sind die Typen der folgenden Werte?
     
    ['a','b','c']
    ('a','b','c')
    [(False,'0'),(True,'1')]
    ([False,True],['0','1'])
    [tail,init,reverse]
    				
  3. Schreibe Definitionen, die die folgenden Typen haben:
     
    bools :: [Bool]
    nums :: [[Int]]
    cmplx :: (Float,Float) 
    vieleck :: [(Int,Int)] 
    				

Funktions-Typen

Eine Funktion ist eine Abbildung (Mapping), die ein Argument eines Typs einem Resultat eines anderen Typs zuordnet.



not :: Bool -> Bool   -- 'not' ist Abb. von Bool nach Bool

even :: Int -> Bool   -- 'even' ist Abb. von Int nach Bool

f :: T1 -> T2         -- 'f' ist Abb. von T1 nach T2 

					

Für das Argument und das Resultat einer Funktion gibt es keine Einschränkungen, was die Typen angeht.

Damit wird es langsam interessant:



add :: (Int,Int) -> Int  -- Typdefinition zuerst: guter Stil. 
add (x,y) = x+y   

					


zeroto :: Int -> [Int]   -- Typdefinition zuerst: 
zeroto n = [0..n]        -- immer noch guter Stil. ;-)

					

herkömmlich definierte Funktion:



add :: (Int,Int) -> Int -- Typdefinition von letzter Folie
add (x,y) = x+y

					

Curried Functions: ... the Haskell way

Funktionen können auch Funktionen als Resultate zurückliefern.



add' :: Int -> (Int -> Int) -- Curried Typedefinition
add' x y = x+y

					

Der Name "Curried" ist dem Namensgeber Haskell Curry der Sprach gewidmet.

noch ein Beispiel:


mult :: Int -> ( Int -> ( Int -> Int ) )
mult x y z = x*y*z

-- mit Klammern: 
((mult x) y) z = (x* y)* z 
					

Die Zuordnungspfeile binden nach rechts, und die Funktionsauswertung bindet nach links. So spart man sich Klammern.


mult :: Int -> Int -> Int -> Int 
mult x y z = x*y*z
					

Typvariablen und polymorphe Typen

Die Funktion "length" gibt die Länge einer Liste von Elemente zurück.
Die Anzahl der Elemente hängt nicht vom Element-Typ ab.


 length [1,2,3,4,5] 
 5 

 length ['A','B','C']   -- unabhängig vom Element-Typ
 3 
					

Bei der Typdefinition nimmt man deshalb Typ-Variablen.


length :: [a] -> Int 
					

Typdefinitionen mit Typvariablen nennt man polymorphe Typen.

... jetzt ihr ...

vollzieht die Beispiele selbst nach und probiert einfach mal aus.

  1. Schreibe Definitionen, die die folgenden Typen haben:
     
    add :: Int -> Int -> Int -> Int 
    copy :: a -> (a,a) 
    apply :: (a -> b) -> a -> b
    				
  2. Was sind die Typen der folgenden Funktionen?
     
    second xs = head (tail xs) 
    swap (x,y) = (y,x)
    pair x y = (x,y) 
    double x = x*2
    palindrome xs = reverse xs == xs 
    twice f x = f (f x) 
    				

Feierabend