Haskell

• Rein funktionale Sprache
• Funktionen als First-Class-Citizens
• keine (überschreibbaren) Variablen
• Ziel: Auswertung eines Ausdrucks

• Bool (auch: Boolean): True oder False
• Char: 'a', '2', '\n'
• String (ist: [Char]): "Name", ['N','a','m','e']
• Int: best. Wertebereich
• Integer: beliebige Größe
• Float
• Double

... stehen auch mit Wertebereich auf dem Cheatsheet!

Grundrechenarten

+, -, *, /, div, mod

Exponentiation

^ (ganzzahliger Exponent), **

Vergleichsoperatoren

==, /=, <, >, <=, >=

Boolsche Operatoren

&&, ||, not

Jede zweistellige Funktion kann sowohl in Infix- als auch mittels Klammerung in Präfix-Notation aufgerufen werden.

5 + 3
(+) 5 3

5 / 3
(/) 5 3

(&&) True False
True && False

mod 5 3
5 `mod` 3

div 5 3
5 `div` 3

Einfache Typangaben von Funktionen werden in folgender Form gemacht:

Typ -> Typ -> ... -> Typ

Beispiele:

(+) :: Double -> Double -> Double
(/) :: Double -> Double -> Double
(&&) :: Bool -> Bool -> Bool
(mod) :: Int -> Int -> Int
(==) :: Char -> Char -> Bool

Offensichtlich gibt es Funktionen, die für mehrere konkrete Typen anwendbar sind, z.B.:

• (==)

  (für alle Werte, die sich vergleichen lassen)

• (+)

  (für jegliche Zahlen)

• mod

  (für ganze Zahlen)

Die o.g. Funktionen sind also für mehr als die dargestellten Typen definiert:

(+) :: Double -> Double -> Double
(+) :: Int -> Int -> Int
(+) :: Float -> Float -> Float
(+) :: Integer -> Integer -> Integer

Unter Nutzung von Typvariablen a, b, ... kann deutlich gemacht werden, dass mehrere Typen (ggf. einer angegebenen Typklasse, siehe nächste Folie) eingesetzt werden können.

(+) :: a -> a -> a

• Eine Typvariable steht für einen Typ.
• Der Typ

  [a] -> Int

  heißt allgemeinster Typ für

  length

  .
• Funktionen, deren Typ eine Typvariable enthält, heißen polymorphe Funktionen.

Manche Funktionen sind zwar polymorph, aber dennoch nur für bestimmte Typen anwendbar. So lässt sich (+) eigentlich nur auf Zahlen anwenden. Es gibt daher eine Reihe von Typklassen:

• Eq: alle primitiven Datentypen
• Ord: Bool, Char, Int, Integer, Float, Double (impliziert Eq)
• Num: Int, Integer, Float, Double
• Fractional: Float, Double (impliziert Num)
• Integral: Int, Integer (impliziert Num)
• Enum: Char, Int, Integer, Float, Double

Die Einschränkung von Typvariablen durch Typklassen wird wie folgt dargestellt:

(Typklasse a, Typklasse b, ...) => Typ -> Typ -> ... -> Typ

Für die vorangegangenen Beispiele gilt also:

(==) :: (Eq a) => a -> a -> Bool
(+) :: (Num a) => a -> a -> a
mod :: (Integral a) => a -> a -> a

(&&) :: Bool -> Bool -> Bool allgemeiner geht nicht 

Was bedeutet folgender Funktionstyp?

(>=) :: (Ord a) => a -> a -> Bool

• Zwei Parameter und ein Rückgabewert?
• Ein Parameter und als Rückgabe eine Funktion? D.h.

  a -> (a -> a)

In Haskell implizite Klammerung nach rechts, d.h. zweiter Fall.

Jede Funktion in Haskell kann partiell aufgerufen werden. Achtung bei zweistelligen Operatoren!

Beispiele:

((+) 1) Nachfolger
((*) 10) Zehnfache einer Zahl
((^) 3) 3 hoch Zahl
((>=) 0) Zahl kleiner gleich 0?

Achtung: Haskell "verdreht" zweistellige transitive Funktionen zur natürlichsprachigen Bedeutung:

(^ 3) Zahl hoch 3
(>= 0) Zahl größer gleich 0?

• Folge von Komponenten i.A. unterschiedlichen Typs
• Notation:

  (T1, T2, ..., Tn)

  bezeichnet n-Tupel, dessen i-te Komponente vom Typ T_i ist
• leeres Tupel:

  ()

• Tupel mit einer Komponente nicht erlaubt (Warum?)

(True, False) :: (Bool, Bool)
(1, 'c', "test") :: (Num a) => (a, Char, String)
((True, False), (False, False)) :: ((Bool, Bool), (Bool, Bool))
(1) :: (Num a) => a Zahl in Klammern, kein 1-Tupel!

• Folge von Elementen gleichen Typs
• Jede Liste ist entweder leer

  []

  , oder sie besteht aus einem Element und einer Restliste

  (x:xs)

• Auflistung der Listenelemente möglich:

  [1,2,3,4]

• Auch unendliche Listen möglich

[True, False, False] :: [Bool]
[1,2,3,4] :: (Num a) => [a]
[1,2,3,4.2] :: (Fractional a) => [a]
[(True,0), (False,1), (True,2)] :: (Num a) => [(Bool, a)]
[] :: [a]

Komfortable Möglichkeit, Listen als arithmetische Folge zu definieren:

• [n..m]

  →

  [n,n+1,...,m-1,m]

• [n,k..m]

  →

  [n,n+(k-n),n+2*(k-n)...,m]

Beispiele

[1..10] → [1,2,3,4,5,6,7,8,9,10]
[1,3..10] → [1,3,5,7,9]
[10,7..(-3)] → [10,7,4,1,-2]
['a'..'f'] → ['a','b','c','d','e','f']
[1,3..] → [1,3,5,7,...] unendliche Liste

Listenkomprehension (1)

• Beschreibung einer Liste über ihre Eigenschaften
• vgl. Mathematik: { n² | n ∈ Ν, n gerade }
• Haskell analog:

  [Resultatausdruck | Generator, Wächter]

• Hier konkret:

  [n^2 | n <- [1..], even n]

Eine Listenkomprehension kann mehrere Generatoren besitzen:

[(x,y) | x <- [1..3], y <- [True, False]]
→ [(1,True),(1,False),(2,True),(2,False),(3,True),(3,False)]

[(x,y) | x <- [1..4], y <- [True, False], y, x `mod` 2 == 0]
→ [(2,True),(4,True)]

Je weiter rechts ein Generator steht, desto schneller verändert er sich, analog zu verschachtelten Schleifen.

... die auch auf dem Cheatsheet stehen:

Erstes Element einer Liste zurückgeben

head :: [a] -> a
head [1..10] == 1

Liste ohne das erste Element

tail :: [a] -> [a]
tail [1..10] == [2..10]

Letztes Listenelement

last :: [a] -> a
last [1..10] == 10

Ersten n Elemente einer Liste

take :: Int -> [a] -> [a]
take 5 [1..10] == [1..5]

Liste ohne die ersten n Elemente

drop :: Int -> [a] -> [a]
drop 5 [1..10] == [6..10]

Kommt Element in Liste vor?

elem :: Eq a => a -> [a] -> Bool
elem 5 [1..10] == True

Länge einer Liste

length :: [a] -> Int
length [1..10] == 10

Verknüpfung zweier Listen

(++) :: [a] -> [a] -> [a]
[1..10] ++ [11..20] == [1..20]

Listenreihenfolge umkehren

reverse :: [a] -> [a]
reverse [1..10] == [10,9..1]

Liste von Listen zusammenfügen

concat :: [[a]] -> [a]
concat [[1..10],[11..20],[21..30]] == [1..30]

Summe aller Listenelemente (analog:

product

)

sum :: Num a => [a] -> a
sum [1..10] == 55

Liste filtern

filter :: (a -> Bool) -> [a] -> [a]
filter even [1..10] == [2,4..10]

Funktion auf alle Listenelemente anwenden

map :: (a -> b) -> [a] -> [b]
map (*2) [1..10] == [2,4..20]

Einfache Funktionen können einfach aufgeschrieben werden:

muenzen :: [Int]
muenzen = [1,2,5,10,20,50,100,200]

average :: (Fractional a) => a -> a -> a -> a
average a b c = (a+b+c)/3

inc :: (Integral a) => a -> a
inc = (+1) -- Partieller Aufruf

Form:

if Bedingung::Bool then Ausdruck1::a else Ausdruck2::a 

abs n = if n >= 0 then n else (-1)*n

fak n = if n == 0 then 1 else n*(fak (n-1))

Statt geschachtelter bedingter Ausdrücke können Guards verwendet werden:

-- verschachtelt:
sign n = if n < 0 then -1 else if n == 0 then 0 else 1

-- mit Guards:
sign' n | n < 0     = -1
        | n == 0    =  0
        | otherwise =  1

• Bedingungen werden der Reihe nach angewandt
• Eine Bedingung sollte erfüllt werden, daher...

• otherwise

  als letztes verwenden!

Vergleich auf Basis von Mustern, d.h. ohne Nutzung von Bedingungen.

Beispiele:

oder :: Bool -> Bool -> Bool
oder True  _ = True  -- Wildcard-Operator
oder False a = a

fak 0 = 1
fak n = n * fak (n-1)

• Funktionsanwendung von oben nach unten
• Bei Rekursionen: Basisfälle nach oben!
• Vgl. Prolog: kein Backtracking o.ä.

Als Muster können auch Variablen oder komplexe Muster dienen. Typisch ist dies etwa bei Listen.

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

Sollen mehrere Muster in einem Ausdruck dargestellt werden, bietet sich ein Case-Ausdruck an:

length l = case l of
                []     -> 0
                (x:xs) -> 1 + length xs

neg b = case b of
                True  -> False
                False -> True

Häufig braucht man Hilfsfunktionen nur in einem konkreten Funktionsaufruf und möchte sie daher nicht global definieren. Stattdessen können sie per

let

where

let

let Bezeichner = Ausdruck1 in Ausdruck2
          
let 
  m = [1,2,5,10,20,50,100,200]
in 
  [x+y+z | x <- m, y <- m, z <- m]

where

Ausdruck1 = Ausdruck2
  where Bezeichner = Ausdruck3

werte = [x+y+z | x <- m, y <- m, z <- m]
  where m = [1,2,5,10,20,50,100,200]

Ähnlich zu lokalen Funktionen: Angabe einer Funktion ohne Namen.

-- über lokale Definition
let myf i = i `mod` 3 == 1 && i `mod` 7 == 2 in filter myf [1..]
-- [16,37,58,79,100,121,142,163,184,...]

-- über Lambda-Ausdruck
filter (\i -> i `mod` 3 == 1 && i `mod` 7 == 2) [1..]

-- Resultat?
(\x y -> x*y) 2 3      -- 6
(\x y -> x*y) 2        -- (\y -> 2*y)

sum [] = 0
sum (x:xs) = x + sum xs

product [] = 1
product (x:xs) = x * product xs

and [] = True
and (x:xs) = x && and xs

foldr f i [] = i
foldr f i (x:xs) = f x (foldr f i xs)

Es gibt foldr für rechtsassoziative und foldl für linksassoziative Funktionen:

foldr f i [] = i
foldr f i (x:xs) = f x (foldr f i xs)

foldl f i []     = i
foldl f i (x:xs) = foldl f (f i x) xs

Durch Typsynonyme können weitere Namen für bereits existierende Typen gesetzt werden, etwa String für [Char].

type String = [Char]

type IntPaar = (Int, Int)

... können über das Schlüsselwort

data

Aufzählungstyp

data Programmiersprache = Haskell | Prolog | CHR | Java
deriving (Eq, Ord, Enum, Show)

Komplexer Datentyp

data Shape = Circle Float 
           | Rectangle Float Float 
           | Square Float

Typdefinitionen (Programmiersprache) und Konstruktoren (Haskell) werden groß geschrieben.

Den Konstruktoren können zusätzliche Informationen als Parameter übergeben werden:

data Shape = Circle Float
           | Rectangle Float Float
           | Square Float

area (Circle r) = 3.14159 * r^2
area (Rectangle a b) = a * b
area (Square a) = a^2

Rekursive Datentypen stellen Bäume dar. Ein einfacher Binärbaum wäre:

data BinTree = Empty
             | Node BinTree BinTree

-- Mögliche Instanz:
Node (Node Empty (Node Empty Empty)) Empty

Der eben gezeigte Baum ist wenig sinnvoll, da er keine Werte halten kann. Eine Alternative wäre:

data BinIntTree = Empty
                | Node Int BinIntTree BinIntTree
      
-- Typvariable a
data BinTree a = Empty
               | Node a (BinTree a) (BinTree a)

-- Mögliche Instanzen:
type BinCharTree = BinTree Char
Node 'c' (Node 'd' Empty (Node 'e' Empty Empty)) Empty

Gegeben sei folgender Datentyp aus Aufgabe 8:

type Quantity = Integer
data HuffmanTree = Node HuffmanTree HuffmanTree
                 | Char Quantity Char
  deriving (Eq, Ord, Show)

Allgemeines Vorgehen:

foldHuffmanTree :: 
    (Quantity -> Char -> a) -> (a -> a -> a) -> HuffmanTree -> a

foldHuffmanTree cf nf = m
  where m (Char q c)   = cf q c
        m (Node h1 h2) = nf (m h1) (m h2)

... gibt's mit Lösungsvorschlägen hier:
fnogatz.github.io/talks/pdp-rep-14/haskell/exercises.html

Credits

Thanks to Benjamin Erb for the html5slides and uulm template.

Title image: Miran Lipovača under CC BY-NC-SA 3.0