Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
1446 lines (1369 sloc) 48.2 KB

• maloi <mm@noexample.de>
• Astro <astro@spaceboyz.net>

Chaos Computer Club Dresden

2012-08-29

Genesis: 1990

Hilfe

Paket-Management mit Cabal

apt-get install ghc ghc-prof cabal-install

# Updates list of known packages
cabal update

# Installs package with library profiling
cabal install -p yesod-platform

Mit Dependencies

-p für Profiling

als User alles nach ~/.cabal

Syntax

Funktionen

fac :: Integer -> Integer
fac 1 = 1
fac n = n * fac (n - 1)

Fakultät

-> Implikation, rechtsassoziativ

Pattern matching des Parameters

Integer is bignum, Int nicht

case

fac' :: Integer -> Integer
fac' n =
case n of
1 -> 1
_ -> n * fac (n - 1)

Pattern matching

Anonyme Variable

Guards

fac'' :: Integer -> Integer
fac'' n
| n <= 1    = 1
| otherwise = n * fac (n - 1)

Boolean expression

if then else

fac''' :: Integer -> Integer
fac''' n =
if n <= 1
then 1
else n * fac (n - 1)

Boolean expression

Listen

\$ ghci

REPL

Prelude> 2 : [] [2] Prelude> 23 : [] [23] Prelude> 23 : 42 : [] [23,42] Prelude> 23 : 42 : 5 : [] [23,42,5] Prelude> :t (:) (:) :: a -> [a] -> [a]
Prelude> :t map
map :: (a -> b) -> [a] -> [b]
Prelude> :t filter
filter :: (a -> Bool) -> [a] -> [a]
Prelude> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

Zeige mehr containers

let

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n =
let r = fib \$ n - 1
r' = fib \$ n - 2
in r + r'

where

facs = 1 : go 2
where go :: Integer -> [Integer]  “Unterfunktion”
go n = n : map (* n) (go \$ n + 1)

Prelude> :t facs  Inferred type
facs :: [Integer]
Prelude> facs !! 500   Unendlich, lazy
611288549821546144419320631496946510053040745744399613938399207781308531950094880800353720198603844213369821855051249995665852739761166777440873387784823972024431693541604632490253390402221485016448489094881275898497140756808655499992463957536774753658273522343143352081610678258299859781290947510064133164625417126214683287364306533202043771696934819148200603488701298578593288295101675375228475039194518540926501811512211084741146359555616051391364512171815202852428391973770531819587555590747725222707870915089204322125602187745638954304887403405330317436980872692673627514602895425139803517823839455807896878364709108235036658336397561844224198282288969461157203049314666899393600517284430144216183492154249948251192663554129489210224225335784718743202172831724716080857069568307715110065035130707514179942202121569852186583424945734289322385681601382444331381680307765142985006245859526451817213228740320341074735777885270328149239431528071389670544598095262337701383222299067569757970109034425702794542448640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

(\$)

Lambdas

Num: Interface für (+), (*)

Prelude> :t (\n -> n + 1)
(\n -> n + 1) :: Num a => a -> a
Prelude> (\n -> n + 1) 22
23
Prelude> :t (\a b c -> a * b * c)
(\a b c -> a * b * c) :: Num a => a -> a -> a -> a
Prelude> :t (\a -> \b -> \c -> a * b * c)
(\a -> \b -> \c -> a * b * c) :: Num a => a -> a -> a -> a

Umkehrschluß: Currying

Currying

:t map (\a -> a + 1)
map (\a -> a + 1) :: Num b => [b] -> [b]

Sections

Prelude> :t (+ 1)
(+ 1) :: Num a => a -> a
Prelude> map (+ 1) [1..10]
[2,3,4,5,6,7,8,9,10,11]

Function Composition

Prelude> :i (.)
(.) :: (b -> c) -> (a -> b) -> a -> c 	-- Defined in `GHC.Base'
infixr 9 .
Prelude> :t (+ 5) . (* 3)
(+ 5) . (* 3) :: Num c => c -> c
Prelude> ((+ 5) . (* 3)) 23
74

data

Statt NULL-Pointer

data Maybe a = Nothing
| Just a
Prelude> :t Nothing   Constructors
Nothing :: Maybe a   Passt auf alle a
Prelude> :t Just
Just :: a -> Maybe a
data [] a = []
| a : [a]

type

Typ-Alias

type String = [Char]

newtype

newtype Name = Name String  Typename = Ctor
• Darf nur 1 Feld haben
• Billig zur Laufzeit
• Typsicher zur Compile-Zeit

Record-Syntax

data MeinTyp = MeinKonstruktor String Integer
Prelude> :t MeinKonstruktor
MeinKonstruktor :: String -> Integer -> MeinTyp

Für data & newtype weiterhin mit nur 1 Feld

data MeinTyp = MeinKonstruktor {
meinString :: String
, meinInteger :: Integer
}
-- Lesbare Konstruktion
fnord = MeinKonstruktor {
meinString = "fnord"
, meinInteger = 23
}
Prelude> :t meinString  Accessor
meinString :: MeinTyp -> String
Prelude> :t meinInteger
meinInteger :: MeinTyp -> Integer
Prelude> meinInteger fnord
23

Parameterisierte Typen!

Classes & Instances

class Show a where
show :: a -> String
instance Show MeinTyp where
show (MeinDatum n) = "MeinDatum " ++ show n

Wie interface in Java

Prelude> :i Num
class Num a where
(+) :: a -> a -> a
(*) :: a -> a -> a
(-) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
-- Defined in `GHC.Num'
instance Num Integer -- Defined in `GHC.Num'
instance Num Int -- Defined in `GHC.Num'
instance Num Float -- Defined in `GHC.Float'
instance Num Double -- Defined in `GHC.Float'

deriving

Funktioniert mit grundlegenden Datentypen:

class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
class Eq a => Ord a where
compare :: a -> a -> Ordering
class Enum a where
succ :: a -> a
pred :: a -> a
class Bounded a where
minBound :: a
maxBound :: a
class Show a where
show :: a -> String

Anwendungsbeispiel:

Prelude> newtype Zeigbar =
Zeig String deriving Show
Prelude> putStrLn \$ show \$ Zeig "Hello"
Zeig "Hello"

Module

Am Beginn von Quellcode-Dateien:

module MeinKram where
module Main (main) where

import MainKram
import qualified Data.Text as T

fnord :: T.Text
fnord = T.pack "fnord"

Operator-Schreibweise

Prelude> :i (+)
class Num a where
(+) :: a -> a -> a
infixl 6 +
Prelude> :i (/)
class Num a => Fractional a where
(/) :: a -> a -> a
infixl 7 /
Prelude> :i (^)
(^) :: (Num a, Integral b) => a -> b -> a
infixr 8 ^
Prelude> "bar" `elem` ["foo","bar","baz"]
True

Functors - Motivation

• Eine Funktion, die jeder liebt:

map :: (a -> b) -> [] a -> [] b -- map :: (a -> b) -> [a] -> [b]
• Wie sieht so eine Funktion z.B. fuer Baeume aus?

data Tree a = Leaf a | Node a (Tree a) (Tree a)
mapTree :: (a -> b) -> Tree a -> Tree b
• Maybe just nothing

data Maybe a = Just a | Nothing
mapMaybe :: (a -> b) -> Maybe a -> Maybe b

Functors - Motivation (2)

• map      :: (a -> b) -> []    a -> []    b
mapTree  :: (a -> b) -> Tree  a -> Tree  b
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
• Die Funktionen haben - bis auf Umbenennung des Typ-Konstruktors - die gleiche Signatur

• Type classes to the rescue!

• Zuvor aber ein kleiner Ausflug

Kinds: Typen von Typen - WTF?

• In Haskell hat jeder Ausdruck einen Typ

• Diese Typen haben wiederum "Typen" - Kinds

• * ist der Kind jedes Datentyps (nullstelliger Typ-Konstruktor)

Diese Typen beschreiben Werte

• k1->k2 ist der Kind von einstelligen Typ-Konstruktoren, die Typen von Kind k1 nehmen und Typen von Kind k2 erzeugen

Kinds: Beispiele

• Monomorph

Int        :: * -- z.B. 42
Maybe Int  :: * -- z.B. Just 23
Int -> Int :: * -- z.B. (+23)
• Polymorph

Maybe :: * -> *
(->)  :: * -> *
(,,)  :: * -> * -> *
• Lustig

data Funny f a = Funny a (f a)
Funny :: (* -> *) -> * -> *

Functors redux

• map      :: (a -> b) -> []    a -> []    b
mapTree  :: (a -> b) -> Tree  a -> Tree  b
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
• Zusammengefasst ergibt sich also folgendes:

map :: (a -> b) -> f a -> f b
• f ist demnach vom Kind * -> *

• Ist es moeglich die Funktion einmalig fuer alle Typen dieses Kinds schreiben?

• Nein, natuerlich nicht!

Functor - the easy type class

• class Functor f where
fmap :: (a -> b) -> f a -> f b
• Intuition

• Ein Functor stellt eine Art Container dar, der es ermoeglicht (mit fmap) eine Funktion (uniform) auf alle Elemente in diesem Container anzuwenden

• Alternativ dazu kann man Functor auch als einen computational context sehen und fmap wendet eine Funktion auf einen Wert in einem Kontext an ohne diesen Kontext zu aendern

Functor - Kind is kind of important

• instance Functor Int where
fmap = ...
• [1 of 1] Compiling Main             ( 2012-03-15.lhs, interpreted )

2010-10-25.lhs:145:19:
Kind mis-match
The first argument of `Functor' should have kind `* -> *',
but `Int' has kind `*'
In the instance declaration for `Functor Int'

• Wie die Fehlermeldung vermuten laesst, hat Int den Kind *

Functor moechte aber, dass sein erstes Argument Kind * -> * hat

Functor - Listen

• instance Functor [] where
fmap _ []     = []
fmap g (x:xs) = g x : fmap g xs -- oder einfach fmap = map
• Listen sind ein gutes Beispiel fuer einen Functor, der als Container - ueber den man mappen kann - aufgefasst werden kann

• Kann aber auch als Berechnung mit nicht-deterministischen Ergebnis gesehen werden

• Da fmap den Kontext nicht aendert ist das Resultat wiederum nicht-deterministisch

• \$ ghci
Prelude> fmap (+1) [1,2,3]
[2,3,4]

Functor - Maybe baby

• instance Functor Maybe where
fmap _ Nothing  = Nothing
fmap g (Just a) = Just (g a)
• Maybe kann als Container gesehen werden, der ein Element haben kann

• Oder als Berechnung mit moeglichem Fehlschlag

• \$ ghci
Prelude> fmap (+23) (Just 19)
Just 42
Prelude> fmap (+23) Nothing
Nothing

Functor - Do you read me?

• instance Functor ((->) r) where
fmap f g = (.) -- (\x -> f (g x))
• fmap :: (a -> b) -> f a        -> f b
fmap :: (a -> b) -> ((->) r a) -> ((->) r b)
fmap :: (a -> b) -> (r -> a)   -> (r -> b)
• (.)  :: (b -> c) -> (a -> b)   -> a -> c
• Container, der mit Werten vom Typ r indiziert ist

• Berechnung, die Werte in einer (read-only) Umgebung nachschlagen kann

• (->) r wird deshalb oftmals auch als reader monad bezeichnet (mehr dazu spaeter)

• \$ ghci
Prelude Control.Monad.Instances> fmap (*3) (+10) \$ 1
33
Prelude Control.Monad.Instances> (fmap (*3) (+10) \$ 1) == ((*3) . (+10) \$ 1)
True

Functor - Sin is lawlessness

• 1. fmap id = id -- id = (\x -> x) und damit id :: a -> a
2. fmap (g . h) = (fmap g) . (fmap h)
• Sichern, dass fmap nur die Werte, nicht aber deren Kontext aendert

• 1. Wenn man id ueber einen Functor mapped, sollte der resultierende Functor gleich dem urspruenglichen sein

• 2. Es ist egal ob man die Komposition zweier Funktionen ueber einen Functor mapped oder erst die eine Funktion mapped und dann die andere

Functor - I break the law

• instance Functor [] where
fmap _ [] = []
fmap g (x:xs) = g x : g x : fmap g xs

• Gueltige Functor Instanz

• Aber: haelt sich nicht an das erste Gesetz!

fmap id [1,2,3] == [1,1,2,2,3,3]
id [1,2,3]      == [1,2,3]

• Und: haelt sich nicht an das zweite Gesetz!

fmap (id . id) [1,2,3]          == [1,1,2,2,3,3]
(fmap id) . (fmap id) \$ [1,2,3] == [1,1,1,1,2,2,2,2,3,3,3,3]

Applicative - Motivation

• fmap liftet eine (normale) Funktion zu einer Funktion, die in einem Kontext verwendet werden kann

• Auch fmap unterliegt natuerlich wie jede andere Funktion currying/partial application

\$ ghci
Prelude> :t fmap (+) (Just 2)
fmap (+) (Just 2) :: Num a => Maybe (a -> a)

• Man kann aber mit fmap keine Funktion, die selbst in einem Kontext liegt, auf Werte in einem Kontext anwenden

\$ ghci
Prelude> fmap Just (+) Just 5
:9:6:
Couldn't match expected type `t1 -> t0' with actual type `Maybe a0'

Applicative - Intuition incoming

• [[ g x1 x2 ... xn ]] soll eine Notation fuer eine Funktionsapplikation in einem Kontext sein

• g sei nun vom Typ t1 -> t2 -> ... -> tn -> t und xi vom Typ f ti dann ist [[ g x1 x2 ... xn ]] vom Typ f t wobei f ein Functor ist

• Das kann man sich als Funktionsapplikation auf mehrere moeglicherweise seiteneffekt habende Argumente vorstellen

• Das ist eine Generalisierung von fmap, die ja nur auf ein einzelnes Argument in einem Kontext angewendet werden kann

• Wendet man g auf x1 an bekommen wir eine Funktion f (t2 -> ... -> t)

• Diese Funktion kann aber mit fmap nicht auf das naechste Argument angewendet werden - !#*"§"\$

Applicative - let me handle it

• class Functor f => Applicative f where
pure  :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
• Oha - <*> erlaubt uns also jetzt [[ g x1 x2 ... xn ]] in Haskell umzusetzen

g <\$> x1 <*> x2 <*> ... <*> xn -- <\$> = fmap
• Na das sieht doch aus wie normale Funktionsapplikation

• Applicative Programming with Effects

• pure nimmt ein Argument beliebigen Typs und packt es in einen default Container oder einen effektfreien Kontext

• Damit lassen sich auch effektfreie Argumente inmitten dieser Berechnung einbauen

g <\$> x1 <*> pure x2 <*> x3

Applicative - Liste

• instance Applicative [] where
pure x    = [x]
gs <*> xs = [ g x | g <- gs, x <- xs ]
• Wende jede Funktion der ersten Liste auf jedes Element der zweiten Liste an

• \$ ghci
Prelude Control.Applicative> (+) <\$> [2,3,4] <*> pure 4
[6,7,8]

\$ ghci
Prelude Control.Applicative> (*) <\$> [7,8,9] <*> [1,2]
[7,14,8,16,9,18]

Applicative - Liste (2)

• newtype ZipList a = ZipList { getZipList :: [a] } -- pro Datentyp nur eine Instanz einer Typklasse
• Elementweise Applikation - die Listen werden zusammen gezipped

• instance Applicative ZipList where
pure = ZipList (repeat x)
(ZipList gs) <*> (ZipList xs) = ZipList (zipWith (\$) gs xs)
• \$ ghci
Prelude Control.Applicative> getZipList \$ (mod) <\$> ZipList [9,27,56] <*> ZipList [1..10]
[0,1,2]

Applicative - Gesetze

• Es gibt mehre Gesetze aber wichtig fuer das Verstaendnis ist nur eins:

Wie haengt Applicative mit Functor zusammen?

• fmap g x = pure g <*> x

Eine normale Funktion die ueber einen Kontext x gemapped wird ist aequivalent dazu diese Funktion in den Kontext zu liften und sie dann mit <*> auf x anzuwenden

• Die restlichen Gesetze sichern nur, dass sich pure so verhaelt wie man es erwartet

A monad is just a monoid in the category of endofunctors, what's the problem?

Monad - Just another type class

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b
(>>)   :: m a -> m b -> m b
m >> n = m >>= \_ -> n

fail   :: String -> m a
• return entspricht pure aus Applicative: return IS pure

Jede Monad ist ein Applicative Warum aber kein Constraint wie bei Applicative?

Nachtraeglich zu verlangen ein Monad muss ein Applicative sein, wuerde viel Code kaputt machen etc.

Monad - Just another type class (2)

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b
(>>)   :: m a -> m b -> m b
m >> n = m >>= \_ -> n

fail   :: String -> m a
• (>>) ist ein Spezialfall von (>>=) und es gibt eine Default Implementierung

(>>) ignoeriert das Ergebnis einer Berechnung aber nicht ihre Effekte

• fail ist ein Hack und gehoert eigtl. nicht in Monad - daher der Name? ;)

do (x:xs) <- foo -- Pattern matching fails wenn foo eine leere Liste produziert -> fail
bar x

Monad - Just another type class (3)

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b
(>>)   :: m a -> m b -> m b
m >> n = m >>= \_ -> n
• (>>=) nennt man bind und ermoeglicht eine Berechnung abhaengig von dem Ergebnis einer davor stattfinden Berechnung zu machen

• Looking at the types

(>>=)  :: m a -> (a -> m b) -> m b
• Das zweite Argument, (a -> m b), ist eine Berechnung, die als Eingabe das Ergebnis der ersten Berechnung nimmt und dann die Berechnung m b durchfuehren kann

x >>= k ist also eine Berechnung, die x ausfuehrt und dann das Ergebnix von x nutzt um zu entscheiden welche Berechnung es als zweites ausfuehrt und nimmt das Ergebnis dieser (zweiten) Berechnung als Ergebnis der gesamten Berechnung

Monad - Warum reicht Applicative nicht

• Kann man (>>=) nur mit fmap, pure und <*> darstellen?

• Wenn x vom Typ m a ist und k vom Typ a -> m b, kann man nur k auf x anwenden

Das geht natuerlich nur mit fmap und fmap k hat dann den Typ m a -> m (m b)

Wenn man das jetzt auf m a anwendet bekommt man etwas mit dem Typ m (m b)

Hier ist Schluss - Wir wollen aber etwas vom Typ m b

• Wir brauchen also eine Funktion, die mehrere ms zusammenfuehrt

join :: m (m a) -> m a
• Man kann Monad auch wie folgt definieren: (Categorytheorists can dance now)

class Applicative m => Monad' m where
join :: m (m a) -> m a

return = Just
(Just x) >>= g = g x
Nothing  >>= _ = Nothing
• Sobald die erste Berechnung fehlschlaegt, schlaegt die gesamte Berechnung fehl

• data Dude = Dude { name, favDrink, favLang :: String } deriving Show

isCool :: Dude -> Maybe Dude
isCool d
| favLang d == "Haskell" = Just d
| otherwise              = Nothing

isHip :: Dude -> Maybe Dude
isHip d
| favDrink d == "Club Mate" = Just d
| otherwise                 = Nothing

spj = Dude "Simon P. J."      "Club Mate" "Haskell"
srd = Dude "Some Random Dude" "Club Mate" "PHP"

tuersteher :: Dude -> Maybe Dude
tuersteher d = return d >>= isCool >>= isHip -- isCool d >>= isHip
\$ghci
*Main> tuersteher spj
Just (Dude {name = "Simon P. J.", favDrink = "Club Mate", favLang = "Haskell"})
*Main> tuersteher srd
Nothing

Monad - I never try anything, I just do it

• Haskell bietet eine spezielle Notation an um aehnlich wie in imperativen Sprachen zu programmieren - Do

• a >>= \x -> b >> c >>= \y -> d
a >>= \x -> -- x bindet das Ergebnis von a
b >>
c >>= \y -> -- y bindet das Ergebnis von c
d

b,c und d duerfen auf x zugreifen, und d darf auch auf y zugreifen

• In Zucker gegossen sieht das so aus:

do { x <- a ; -- die ; sind optional
b      ;
y <- c ;
d
}

• return a >>= k  =  k a
m >>= return    =  m
m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h

fmap f xs  =  xs >>= return . f  =  liftM f xs

Das erste und zweite Gesetz sichert, dass return sich benimmt

Das dritte Gesetz sichert eine Art Assoziativitaet

Das vierte besagt, dass fmap und liftM das selbe sind fuer Typen, die gleichzeitig Monad und Functor sind

liftM :: Monad m => (a -> b) -> m a -> m b und ist das selbe wie fmap ist. Wir haben beide, weil die Monad Typklasse keine Functor Instanz verlangt

• import Data.Char

main = do
firstName <- getLine
lastName <- getLine
let bigFirstName = map toUpper firstName
bigLastName = map toUpper lastName
putStrLn \$ "hey " ++ bigFirstName ++ " " ++ bigLastName ++ ", how are you?"
• *Main> main
Hasi
Hasenmann
hey HASI HASENMANN, how are you?
*Main>

Real World Haskell, Chapter 16: Parsec

import Text.ParserCombinators.Parsec

{- A CSV file contains 0 or more lines, each of which is terminated
by the end-of-line character (eol). -}
csvFile :: GenParser Char st [[String]]
csvFile =
do result <- many line
eof
return result

-- Each line contains 1 or more cells, separated by a comma
line :: GenParser Char st [String]
line =
do result <- cells
eol                       -- end of line
return result

-- Build up a list of cells.  Try to parse the first cell, then figure out
-- what ends the cell.
cells :: GenParser Char st [String]
cells =
do first <- cellContent
next <- remainingCells
return (first : next)

-- The cell either ends with a comma, indicating that 1 or more cells follow,
-- or it doesn't, indicating that we're at the end of the cells for this line
remainingCells :: GenParser Char st [String]
remainingCells =
(char ',' >> cells)            -- Found comma?  More cells coming
<|> (return [])                -- No comma?  Return [], no more cells

-- Each cell contains 0 or more characters, which must not be a comma or
-- EOL
cellContent :: GenParser Char st String
cellContent =
many (noneOf ",\n")

-- The end of line character is \n
eol :: GenParser Char st Char
eol = char '\n'

parseCSV :: String -> Either ParseError [[String]]
parseCSV input = parse csvFile "(unknown)" input

Real World Haskell, Chapter 16: Parsec

import Text.ParserCombinators.Parsec

csvFile = endBy line eol
line = sepBy cell (char ',')
cell = many (noneOf ",\n")
eol = char '\n'

parseCSV :: String -> Either ParseError [[String]]
parseCSV input = parse csvFile "(unknown)" input

• Bedingte Kompilierung - Versionen fuer unterschiedliche Betriebssysteme, Debuginformationen
• Programm Reifikation - (Introspektion) Eigene Struktur erkennen. Programm kann sich selbst analysieren, veraendern oder neue Programme erstellen
• Algorithmische Programmkonstruktion - Lange Programme durch kurzen Algorithmus konstruieren. TH ubernimmt Konstruktion zu Compilezeit
• Erweiterung der Abstraktionsmechanismen - Nutzer kann z.B. eigene Compilererweiterungen schreiben, ohne dass diese im Compiler integriert sein muessen
• Optimierungen - Unrolling (Verlagerung von Rekursion von Laufzeit in Compilezeit

Template Haskell - Programmcode als Abstrakte Datentypen

AST wird mit Hilfe einfacher ADTs dargestellt

Im untersten Layer existieren Exp, Pat, Dec, Typ

Will man ein Tupel-Ausdruck erzeugen benutzt man den Konstruktor TupE

LamE fuer Lambda Ausdruecke

• E fuer Ausdruecke
• P fuer Patterns
• D fuer Deklarationen
• T fuer Typdefinitionen

TupE ist nicht gleich TupP (Tupel innerhalb eines Patterns

Template Haskell - Programmcode als Abstrakte Datentypen

• LamE [ TupP [ VarP \$ mkName "x",
VarP \$ mkName "y" ]
]
( TupE [ VarE \$ mkName "x",
VarE \$ mkName "y"]
)

• InfixE (Just (LitE (IntegerL 1))) (VarE \$ mkName "+") (Just (LitE (CharL 'a')))

Ergibt 1+'a' aber es gibt kein Typfehler

• LamE [VarP mkName "x"](VarE mkName "notInScope")

Nach Umwandlung in Haskell Code erfolgt eine Compilierung nur wenn es auch eine FUnktion notInScope im Scope gibt

•     cross :: Exp -> Exp -> Exp
cross f g
= LamE [TupP [ VarP \$ mkName "x",
VarP \$ mkName "y"
]
] \$
TupE [ AppE f (VarE \$ mkName "x"),
AppE g (VarE \$ mkName "y")
]

Erwartet zwei Ausdruecke f und g vom Typ Exp um einen Lambdaausdruck zu erstellen

Uebergibt man nun die Ausdruecke VarE \$ mkName "x" und VarE \$ mkName "y" als Parameter an die Funktion cross, meldet der Compiler zunaechst keinen Fehler.

Nach Umwandlung in Haskell Code kommt jedoch folgender Fehler:

• Occurs check: cannot construct the infinite type: t = t -> t1
Probable cause: `x' is applied to too many arguments
In the expression: x x
In the expression: (x x, y y)

Erweiterung der IO Monade um einige Features

WIchtigstes Feature: Globaler Namenspeicher - Erzeugung von Namen, so dass es zu keinen Namenskonflikten kommen kann

newName :: String -> Q Name -- erzeugt einzigartige Namen
cross :: ExpQ -> ExpQ -> ExpQ
cross f g = do
x <- newName "x"
y <- newName "y"
ft <- f
gt <- g
return (LamE [ TupP [ VarP x,
VarP y
]
]
( TupE [ AppE ft (VarE x),
AppE gt (VarE y)
]
)
)

> let f = LamE [VarP \$ mkName "x"] (VarE \$ mkName "x")

> :t f
f :: Exp

> let g = \$(return f)

> :t g
g :: t -> t

> g 42
42

data Expr  = IntExpr Integer
| BinopExpr (Integer -> Integer -> Integer) Expr Expr
deriving(Show)
> [expr|1 + 3 + 5|]
cross :: ExpQ -> ExpQ -> ExpQ
cross f g = [| \ (x,y) -> (\$f x, \$g y) |]

Profiling

Beispiel aus Real World Haskell, Chapter 25:

import System.Environment
import Text.Printf

main = do
[d] <- map read `fmap` getArgs
printf "%f\n" (mean [1..d])

mean :: [Double] -> Double
mean xs = sum xs / fromIntegral (length xs)
% time ./prof1 1e5
50000.5
./prof1 1e5  0.03s user 0.01s system 89% cpu 0.049 total
% time ./prof1 1e6
500000.5
./prof1 1e6  0.31s user 0.09s system 98% cpu 0.400 total
% time ./prof1 1e7
5000000.5
./prof1 1e7  2.95s user 0.60s system 97% cpu 3.626 total
% time ./prof1 1e8
zsh: killed     ./prof1 1e8
./prof1 1e8  6.72s user 2.71s system 91% cpu 10.368 total

sum iteriert durch, Liste kann aber nicht GCed werden, da length sie auch noch benötigt

Time Profiling

% ghc --make -O2 -prof -caf-all -auto-all prof1
% ./prof1 1e7 +RTS -p  -P, -pa
5000000.5
% cat prof1.prof
Wed Aug 29 02:04 2012 Time and Allocation Profiling Report  (Final)

prof1 +RTS -p -RTS 1e7

total time  =        1.74 secs   (1738 ticks @ 1000 us, 1 processor)
total alloc = 1,680,119,104 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

main        Main     86.6  100.0
mean        Main     13.4    0.0

individual     inherited
COST CENTRE MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                     55           0    0.0    0.0   100.0  100.0
main       Main                    111           0   86.6  100.0   100.0  100.0
mean      Main                    113           1   13.4    0.0    13.4    0.0
CAF:main1  Main                    108           0    0.0    0.0     0.0    0.0
main      Main                    110           1    0.0    0.0     0.0    0.0
CAF:main3  Main                    107           0    0.0    0.0     0.0    0.0
main      Main                    112           0    0.0    0.0     0.0    0.0
CAF        GHC.Conc.Signal         101           0    0.0    0.0     0.0    0.0
CAF        GHC.IO.Encoding         100           0    0.0    0.0     0.0    0.0
CAF        GHC.IO.Handle.FD         99           0    0.0    0.0     0.0    0.0
CAF        Text.Read.Lex            95           0    0.0    0.0     0.0    0.0
CAF        GHC.Float                90           0    0.0    0.0     0.0    0.0
CAF        GHC.IO.Encoding.Iconv    82           0    0.0    0.0     0.0    0.0

Space Profiling

% ghc --make -rtsopts -prof -caf-all -auto-all prof1
% ./prof1 1e6 +RTS -K256M -hc -i0.01
% hp2ps -c prof1.hp

Space Profiling

% ./prof1 1e6 +RTS -K256M -hy -i0.01
% hp2ps -c prof1.hp

Auch: GHC Core output

Strictness

import System.Environment
import Text.Printf
import Data.List (foldl')

main = do
[d] <- map read `fmap` getArgs
printf "%f\n" (mean [1..d])

mean :: [Double] -> Double
mean xs = s / fromIntegral n
where
(n, s)     = foldl' k (0, 0) xs
k (n, s) x = n `seq` s `seq` (n+1, s+x)
% ./prof2 1e8 +RTS -sstderr
50000000.5
53,600,200,824 bytes allocated in the heap
31,319,592 bytes copied during GC
62,720 bytes maximum residency (1 sample(s))
26,816 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)

Tot time (elapsed)  Avg pause  Max pause
Gen  0     102796 colls,     0 par    0.66s    0.66s     0.0000s    0.0003s
Gen  1         1 colls,     0 par    0.00s    0.00s     0.0006s    0.0006s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time   32.71s  ( 32.84s elapsed)
GC      time    0.66s  (  0.66s elapsed)
RP      time    0.00s  (  0.00s elapsed)
PROF    time    0.00s  (  0.00s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time   33.38s  ( 33.50s elapsed)

%GC     time       2.0%  (2.0% elapsed)

Alloc rate    1,638,238,233 bytes per MUT second

Productivity  98.0% of total user, 97.7% of total elapsed

In RWH: unboxed strict fields, fusion w/o heap alloc

Strictness

Stream processing

Gegen unkontrollierte Lazyness

ResourceT m a

Control.Applicative.Applicative m) => MonadResource m where
register :: IO () -> m ReleaseKey
release :: ReleaseKey -> m ()
allocate :: IO a -> (a -> IO ()) -> m (ReleaseKey, a)
((forall a. ResourceT IO a -> ResourceT IO a) -> ResourceT IO b)
-> m b

Pipe Type

Data.Conduit> :i Pipe
data Pipe l i o u m r
= Data.Conduit.Internal.HaveOutput (Pipe l i o u m r) (m ()) o
| Data.Conduit.Internal.NeedInput (i -> Pipe l i o u m r)
(u -> Pipe l i o u m r)
| Data.Conduit.Internal.Done r
| Data.Conduit.Internal.PipeM (m (Pipe l i o u m r))
| Data.Conduit.Internal.Leftover (Pipe l i o u m r) l
instance Monad m => Functor (Pipe l i o u m)
Data.Conduit> :i Conduit
type Conduit i m o = Pipe i i o () m ()
Data.Conduit> :i Source
type Source m o = Pipe () () o () m ()
Data.Conduit> :i Sink
type Sink i m r = Pipe i i Data.Void.Void () m r

Conduit Operators

Data.Conduit> :i (\$\$)
(\$\$) :: Monad m => Source m a -> Sink a m b -> m b
infixr 0 \$\$
Data.Conduit> :i (=\$=)
(=\$=) :: Monad m => Conduit a m b -> Conduit b m c -> Conduit a m c
infixr 2 =\$=
Data.Conduit> :i (\$=)
(\$=) :: Monad m => Source m a -> Conduit a m b -> Source m b
infixl 1 \$=
Data.Conduit> :i (=\$)
(=\$) :: Monad m => Conduit a m b -> Sink b m c -> Sink a m c
infixr 2 =\$

Beispiel: cp

module Main (main) where

import Data.Conduit
import qualified Data.Conduit.Binary as CB
import System.Environment (getArgs)

copyFile :: FilePath -> FilePath -> IO ()
copyFile src dest = runResourceT \$ CB.sourceFile src \$\$ CB.sinkFile dest

main = getArgs >>= \[src, dest] ->
copyFile src dest

Beispiel: Bytes zählen

{-# LANGUAGE BangPatterns #-}
module Main (main) where

import Data.Conduit
import qualified Data.Conduit.Binary as CB
import System.Environment (getArgs)
import qualified Data.ByteString as B

copyFile :: FilePath -> FilePath -> IO ()
copyFile src dest = runResourceT \$
CB.sourceFile src \$=
countBytes \$\$
CB.sinkFile dest

main = getArgs >>= \[src, dest] ->
copyFile src dest

countBytes :: MonadIO m => Conduit B.ByteString m B.ByteString
countBytes =
let loop !total =
do mBuf <- await
case mBuf of
Just buf ->
do yield buf
loop \$ total + B.length buf
Nothing ->
do liftIO \$ putStrLn \$
"Transferred " ++
show total ++
" bytes"
return ()
in loop 0

WAI: Web Application Interface

Network.Wai> :i Application
type Application =
Request -> ResourceT IO Response
Network.Wai> :i Middleware
type Middleware = Application -> Application
Network.Wai.Middleware.Gzip> :t gzip
gzip :: GzipSettings -> Network.Wai.Middleware

WAI Request & Response

Prelude Network.Wai> :i Request
data Request
= Request {requestMethod :: Method,
httpVersion :: HttpVersion,
rawPathInfo :: ByteString,
rawQueryString :: ByteString,
serverName :: ByteString,
serverPort :: Int,
isSecure :: Bool,