Haskell TKTL:n koneilla

GHC löytyy:

jkaasine@melkki:~$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.12.1

Uudempi GHC löytyy /opt:n alta

jkaasine@melkki:~$ /opt/ghc-7.0.3/bin/ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.3

Kumpikin kelpaa tämän kurssin tarkoituksiin.

Aloitetaanpa!

ghci on interaktiivinen Haskell-tulkki

$ ghci
GHCi, version 6.12.1: http://www.haskell.org/ghc/  :? for help
Prelude> 1+1
2
Prelude> "asdf"
"asdf"
Prelude> reverse "asdf"
"fdsa"
Prelude> :t "asdf"
"asdf" :: [Char]
Prelude> tail "asdf"
"sdf"
Prelude> :t tail "asdf"
tail "asdf" :: [Char]
Prelude> :t tail
tail :: [a] -> [a]

Lausekkeet ja tyypit

Haskellissa ei ole lauseita (statement), on vain lausekkeita (expression)
Lausekkeella on arvo ja tyyppi
Lauseke ja sen tyyppi kirjoitetaan näin: lauseke :: tyyppi

Lausekkeitten syntaksi

Haskellissa funktiokutsua ei merkitä mitenkään: f 1 on sama kuin f(1) monessa muussa kielessä
Suluilla voidaan kuitenkin ryhmitellä lausekkeita (kuten yleensäkin ohjelmointikielissä)
Funktiokutsut sitovat tiukemmin kuin operaattorit

Haskell	C
`f 1`	`f(1)`
`f 1 2`	`f(1,2)`
`g f 1`	`g(f,1)`
`g (f 1)`	`g(f(1))`
`a + b`	`a + b`
`f a + g b`	`f(a) + g(b)`
`f (a + g b)`	`f(a+g(b))`
`f a (g b)`	`f(a,g(b))`

Tyyppien syntaksi

Perustyyppejä:

Nimi	Literaalit	Selitys	Operaatioita
`Int`	`1`, `2`, `-3`	"Normaali" lukutyyppi	`+`, `-`, `*`, `div`, `mod`
`Integer`	`1`, `2`, `900000000000000000`	Rajoittamaton lukutyyppi	`+`, `-`, `*`, `div`, `mod`
`Double`	`0.1`, `1.2e5`	Liukuluvut	`+`, `-`, `*`, `/`, `sqrt`
`Bool`	`True`, `False`	Totuusarvot	`&&`, `\|\|`, `not`
`String`	`"abcd"`, `""`	Merkkijonot	`reverse`

Funktiot:
- Yhden argumentin funktio: argumenttityyppi -> paluutyyppi
- Kahden argumentin funktio: argumentti1 -> argumentti2 -> paluu
- Kolmen argumentin funktio: a1 -> a2 -> a3 -> p
- Hieman kummallisen näköistä, eikö? Palaamme tähän vielä.

Haskell-ohjelman rakenne

module Kultaa where

-- kultainen leikkaus
phi :: Double
phi = (sqrt 5 + 1) / 2

polynomi :: Double -> Double
polynomi x = x^2 - x - 1

f x = polynomi (polynomi x)

main = do
  print (polynomi phi)
  print (f phi)

Haskell-ohjelman rakenne

moduli / tiedosto

module Kultaa where

moduli koostuu määritelmistä
määritelmä (definition) koostuu (mahdollisesta) tyyppiannotaatiosta ja yhtälöistä
tyyppiannotaatioita (type signature)

phi :: Double
polynomi :: Double -> Double

yhtälöitä (equation)

phi = (sqrt 5 + 1) / 2
f x = polynomi (polynomi x)

lisäksi kommentteja

-- kultainen leikkaus

Miten tällä saa mitään aikaan?

ehtolausekkeet
alimääritelmät
rekursio

Ehtolausekkeet

Monissa muissa kielissä if on lause
Haskellissa if on lauseke
vastaa C:n ja Javan ?: operaattoria

Java:

int y = (x == 0) ? 3 : x;

Haskell:

y = if x == 0 then 3 else 4

Haskellin if siis palauttaa arvon. Siksi aina tarvitaan else!

Esimerkki

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

Alimääritelmät

Haskellissa on kaksi tapaa tehdä paikallisia muuttujia: let...in ja where
Huom! paikalliset muuttujatkin ovat määritelmiä: niitä ei voi siis muuttaa
where lisää määritelmään alamääritelmiä:

circleArea :: Double -> Double
circleArea r = pi * rsquare
    where pi = 3.1415926
          rsquare = r * r

let...in muodostaa lausekkeen:

circleArea r = let pi = 3.1415926
                   rsquare = r * r
               in pi * rsquare

Huom! alimääritelmät voivat olla funktioita

circleArea r = pi * square x
    where pi = 3.1415926
          square x = x * x

circleArea r = let pi = 3.1415926
                   square x = x * x
               in pi * square x

Näillä ei ole suurta eroa käytännössä, palataan eroihin myöhemmin

Hahmonsovitus (Pattern Matching)

Määritelmä voi koostua useammasta yhtälöstä (equation)
Yhtälöitä kokeillaan yksi kerrallaan kunnes sopiva löytyy
"Sopiva" yhtälö on sellainen jossa mahdolliset yhtälössä olevat literaalit vastaavat annettuja argumentteja
Hahmonsovituksen voimasta opitaan lisää ensi viikolla!

Esimerkkejä

tervehdi :: String -> String -> String
tervehdi "Suomi"    nimi = "Hei. " ++ nimi
tervehdi "Italia"   nimi = "Ciao bella! " ++ nimi
tervehdi "Englanti" nimi = "How do you do? " ++ nimi
tervehdi _          nimi = "Hello. " ++ nimi

kuvaile :: Integer -> String
kuvaile 0 = "nolla"
kuvaile 1 = "yksi"
kuvaile 2 = "parillinen alkuluku"
kuvaile n = "luku " ++ show n

hassu :: Bool -> Integer -> Integer
hassu True 0 = 1
hassu True n = n
hassu False 0 = 0
hassu False 1 = 1
hassu False n = -1

Rekursio

Kaikenlaiset "luupit" korvataan rekursiolla
Funktiokutsut ovat nopeita, älä huolehdi suorituskyvystä (ts. vakiokertoimista)
Rekursio on myös hyödyllinen tapa ajatella monien vaikeampien ongelmien ratkaisua

Esimerkkejä

-- kertoma
factorial 0 = 1
factorial n = n * factorial (n-1)

-- laske summa 1^2+2^2+3^2+...+n^2
squareSum 0 = 0
squareSum n = n^2 + squareSum (n-1)

-- fibonaccin luvut, hidas versio
fibonacci 1 = 1
fibonacci 2 = 1
fibonacci n = fibonacci (n-2) + fibonacci (n-1)

Lisää rekursiota

Monesti rekursiossa tarvitaan apumuuttujia: tällöin määritellään apufunktio
Apufunktion argumentit vastaavat muuttujia joita luuppi päivittää

Esimerkkejä

Java:

public int fibonacci(int n) {
    int a = 0;
    int b = 1;
    while (n>1) {
        int c = a+b;  
        a=b;  
        b=c;
        n--;
    }
    return b;
}

Haskell:

-- fibonaccin luvut, nopea versio
fibonacci :: Integer -> Integer
fibonacci n = fibonacci' 0 1 n

fibonacci' :: Integer -> Integer -> Integer -> Integer
fibonacci' a b 1 = b
fibonacci' a b n = fibonacci' b (a+b) (n-1)

Käytetäänpä näitä kaikkia yhdessä!

module Collatz where

step :: Integer -> Integer
step x = if even x then alas else ylos
  where alas = div x 2
        ylos = 3*x+1

collatz :: Integer -> Integer
collatz 1 = 0
collatz x = 1 + collatz (step x)

longest :: Integer -> Integer
longest upperBound = longest' 0 upperBound

longest' :: Integer -> Integer -> Integer
longest' l 0 = l 
longest' l n = if l' > l
                  then longest' l' (n-1)
                  else longest' l (n-1)
  where l' = collatz n

Sananen sisennyksestä

Edelliset esimerkit ovat olleet varsin hienosti sisennettyjä
Haskellissa sisennyksellä on väliä, vähän niin kuin Pythonissa
Nyrkkisäännöt:

Samantasoiset asiat alkavat samasta sarakkeesta
Jos lauseke menee useammalle riville, sisennä enemmän kuin lausekkeen alkukohtaa

Esimerkkejä sisennyksestä

Nämä ovat kaikki ok

i x = let y = x+x+x+x+x+x in div y 5

j x = let y = x+x+x
              +x+x+x
      in div y 5

k = a + b
  where a = 1
        b = 1

l = a + b
  where
    a = 1
    b = 1

Nämä eivät ole ok

i x = let y = x+x+x+x+x+x
in div y 5

j x = let y = x+x+x
      +x+x+x
      in div y 5

k = a + b
  where a = 1
      b = 1

l = a + b
where
  a = 1
  b = 1

l = a + b
  where
    a = 1
     b = 1

Harjoitusten tekeminen

Harjoitukset löydät kurssin kotisivulta.
Kaksi tiedostoa:
- W1.hs tehtävänannot ja tehtäväpohjat
- W1Test.hs yksikkötestit viikon tehtäville
Etene näin
- Lataa molemmat tiedostot ja laita ne samaan hakemistoon
- Muokkaa tiedostoa W1.hs
- Kokeile interaktiivisesti: ghci W1.hs
- Aja testit: runhaskell W1Test.hs
- Kun olet valmis, palauta muokkaamasi W1.hs
  - ohjeet tulossa!
Huomaa! pelkkä testien läpi meneminen ei riitä vaan myös tehtävänannon ohjeita pitää noudattaa, esim. "käytä rekursiota" :)

Luento 2: Catamorphic

Sisältö

Guardit
Listat
Funktionaalisuus
Hieman laiskuudesta
Hieman tyypeistä

Ehdot (guards)

if then else -rakenne on monesti hiukan työläs
Tästä syystä Haskellissa on erityinen syntaksi ehdollisille määritelmille (guarded definitions):

f x y z
  | ehto1 x y z   = jotain
  | ehto2 x z     = muuta
  | otherwise     = jotainmuuta

Ehto voi olla mikä tahansa lauseke tyyppiä Bool
Tapauksista valitaan ylin jonka ehto on True
otherwise tarkoittaa samaa kuin pelkkä True

Ehdot: Esimerkkejä

kuvaile :: Int -> String
kuvaile n
  | n==2      = "Kaksi"
  | even n    = "Parillinen"
  | n==3      = "Kolme"
  | n>100     = "Iso luku!"
  | otherwise = "Luku "++show n

factorial
  | n<0       = -1
  | n==0      = 1
  | otherwise = n * factorial (n-1)

monimutkainen :: Bool -> Double -> Double -> Double
monimutkainen True x y
  | x == y    = 0
  | otherwise = x / (x-y)
monimutkainen False x y
  | y < 0     = sin x
  | otherwise = sin x + sin y

Listat

Literaalit:

[0,3,4,1+1]

Tyyppi: laitetaan elementtien tyyppi hakasulkeisiin

[True,True,False] :: [Bool]
["Moi","Hei"] :: [String]
[] :: [a] -- lisää tästä myöhemmin!
[[1,2],[3,4]] :: [[Int]]

Huom! Listat ovat siis aina homogeenisiä, eli jokaisella elementilla on sama tyyppi.
Toteutukseltaan yhteen suuntaan linkitettyjä listoja, palataan tähän myöhemmin.

Listaoperaatioita

-- onko lista tyhjä?
null :: [a] -> Bool
-- palauttaa ensimmäisen alkion
head :: [a] -> a 
-- palauttaa kaikki paitsi ensimmäisen alkion
tail :: [a] -> [a]
-- palauttaa listan pituuden
length :: [a] -> Int
-- antaa n ensimmäistä alkiota
take :: Int -> [a] -> [a]
-- antaa kaikki paitsi n ensimmäistä alkiota
drop :: Int -> [a] -> [a]
-- listoja yhdistetään ++ operaattorilla
(++) :: [a] -> [a] -> [a]

listoja voi vertailla tutulla == operaattorilla
Muistatteko?

Prelude> :t "asdf"
"asdf" :: [Char]

String onkin vain [Char] eli lista merkkejä!
Kaikki listafunktiot siis toimivat merkkijonoille!

Esimerkkejä

f xs = take 2 xs ++ drop 4 xs

f [1,2,3,4,5,6]  ==>  [1,2,5,6]
f [1,2,3]        ==>  [1,2]

g xs = tail xs ++ [head xs]

g [1,2,3]      ==>  [2,3,1]
g (g [1,2,3])  ==>  [3,1,2]

Sananen tyypinpäättelystä (type inference) ja polymorfismista

Tyyppimuuttujat ovat tyyppejä jotka alkavat pienellä kirjaimella, esim a, b, ...
Tyyppimuuttuja kuvaa tyyppiä jota ei vielä tiedetä, tai toisaalta tyyppiä "mitä tahansa"
Tyyppimuuttujia voidaan tarkentaa toisiksi tyyppimuuttujiksi käännösaikana

Esimerkkejä listafunktioilla

tail :: [a] -> [a]
tail [True,False] :: [Bool]

head :: [a] -> a
head [True,False] :: Bool

Prelude> [True,False] ++ "Moi"

<interactive>:1:16:
    Couldn't match expected type `Bool' against inferred type `Char'
      Expected type: [Bool]
      Inferred type: [Char]
    In the second argument of `(++)', namely `"Moi"'
    In the expression: [True, False] ++ "Moi"

f xs ys = [head xs, head ys]
g xs = f "Moi" xs

Prelude> :t f
f :: [a] -> [a] -> [a]
Prelude> :t g
g :: [Char] -> [Char]

Funktionaalista ohjelmointia, vihdoin

Haskellissa funktio on arvo, aivan kuten luku tai lista tai merkkijono
Funktiot voivat siis myös olla parametreja funktioille
Katsotaanpa!

applyTo1 :: (Int -> Int) -> Int
applyTo1 f = f 1

addThree :: Int -> Int
addThree x = x + 3

applyTo1 addThree ==> addThree 1 ==> 1 + 3 ==> 4

Se oli tylsää, kokeillaanpa jotain mielenkiintoista

-- muuntaa listan toiseksi käyttäen annettua funktiota
map :: (a -> b) -> [a] -> [b]

map addThree [1,2,3] ==> [4,5,6]

Entäs tämä?

-- valitsee listasta vain ehdon täyttävät alkiot
filter :: (a -> Bool) -> [a] -> [a]

positive :: Int -> Bool
positive x = x>0

filter positive [0,1,-1,3,-3] ==> [1,3]

Esimerkkejä

Mitä "palindromilukuja" löytyy väliltä 1-n

palindromes n = filter palindrome (map show [1..n])
  where palindrome str = str == reverse str

length (palindromes 9999) ==> 198

Millaiset k:n merkin pätkät seuraavat merkkiä c merkkijonossa s?

-- Nämä löytyvät standardikirjaston Data.List modulista:
tails :: [a] -> [[a]]        -- palauttaa kaikki listan loppuosat
sort :: Ord a => [a] -> [a]  -- järjestää listan

contexts :: Int -> Char -> String -> [String]
contexts k c s = sort (map tail (filter match (map process (tails s))))
  where match [] = False
        match (c':_) = c==c'
        process x = take (k+1) x

contexts 2 'a' "abracadabra" ==> ["","br","br","ca","da"]

Partial application

Näitten apufunktioitten määrittely menee työlääksi
Onneksi Haskellin funktiot toimivat hiukan kummallisesti...

f :: Bool -> Integer -> Integer -> Integer -> Integer
f True  x _ z = x+z
f False _ y z = y+z

Lausekkeet:

Prelude> (f True) 1 2 3
4
Prelude> let g = (f True) in g 1 2 3
4
Prelude> let g = (f True 1) in g 2 3
4
Prelude> map (f True 1 2) [1,2,3]
[2,3,4]

Tyypit

Prelude> :t f True
f True :: Integer -> Integer -> Integer -> Integer
Prelude> :t f True 1
f True 1 :: Integer -> Integer -> Integer
Prelude> :t f True 1 2
f True 1 2 :: Integer -> Integer
Prelude> :t f True 1 2 3
f True 1 2 3 :: Integer

Partial application 2

BTW, tämä toimii myös operaattoreilla!

Prelude> map (*2) [1,2,3]
[2,4,6]
Prelude> map (2*) [1,2,3]
[2,4,6]
Prelude> map (1/) [1,2,3,4,5]
[1.0,0.5,0.3333333333333333,0.25,0.2]

Operaattori `.`

Tässä pari operaattoria jotka helpottavat funktionaalisen koodin kirjoittamista
Funktioitten yhdistäminen: .

(.) :: (b -> c) -> (a -> b) -> a -> c

Toimii näin

(f.g) x ==> f (g x)

Esimerkkejä

double x = 2*x
quadruple = double . double  -- laskee 2*(2*x) == 4*x
f = quadruple . (+1)         -- laskee 4*(x+1)

third = head . tail . tail   -- hakee listan kolmannen alkion

Operaattori `$`

Operaattori $ on hienovaraisempi

($) :: (a -> b) -> a -> b

Se ei tee mitään, mutta sillä on hyvin matala presedenssi, jonka takia sitä voi käyttää sulkujen eliminointiin!
Siis: f x y z $ g z w on sama kuin (f x y z) (g z w)
Kun yhdistetään nämä kaksi operaattoria, voimme kirjoittaa lausekkeen

f x (g y (h x y (i z z)))

muodossa

f x . g y . h x y $ i z z

katso vaikka!

        f x . g y . h x y $ i z z
  ==>  (f x . g y . h x y) (i z z)
  ==>  (f x . g y) (h x y  (i z z))
  ==>  (f x  (g y  (h x y  (i z z))))

Lambdat

Viimeinen meisseli jonka lisäämme funktionaaliseen työkalupakkiin on λ (lambda)
Lambda-lausekkeet ovat anonyymejä funktioita

Prelude> (\x -> x*x) 3
9
Prelude> (\x -> reverse x == x) "ABBA"
True
Prelude> filter (\x -> reverse x == x) ["ABBA","ACDC","otto","lothar","anna"]
["ABBA","otto","anna"]
Prelude> (\x y -> x^2+y^2) 2 3
13

Yleisesti ottaen

\x0 x1 x2 ... -> e

on sama kuin

let f x0 x1 x2 ... = e in f

kunhan nimi f valitaan sopivasti.

Funktionaalinen tyyli

Kirjoitetaanpa nyt funktio contexts nätimmin
Alkuperäinen

contexts :: Int -> Char -> String -> [String]
contexts k c s = sort (map tail (filter match (map process (tails s))))
  where match [] = False
        match (c':_) = c==c'
        process x = take (k+1) x

contexts k c s = sort (map tail (filter match (map (take (k+1)) (tails s))))
  where match [] = False
        match (c':_) = c==c'

contexts k c s = sort . map tail . filter match . map (take $ k+1) $ tails s
  where match [] = False
        match (c':_) = c==c'

contexts k c = sort . map tail . filter ((==[c]).take 1) . map (take $ k+1) . tails

BOOYAH!

Lisää esimerkkejä funktionaalisesta listojen pyörittelystä

-- etsitään ensimmäinen annetuista merkeistä koostuva alimerkkijono
findSubString :: [String] -> [String] -> [String
findSubString chars = takeWhile (\x -> elem x chars)
                      . dropWhile (\x -> not $ elem x chars)

findSubString "abcd" "xxxyyyzabaaxxabcd"  ==>  "abaa"

-- pilkotaan merkkijono paloihin annetun merkin kohdalta
split :: Char -> [String] -> [[String]]
split c [] = []
split c xs = start : split c (drop 1 rest)
  where start = takeWhile (/=c) xs
        end = dropWhile (/=c) xs

split 'x' "fooxxbarxquux"   ==>   ["foo","","bar","quu"]

-- modulista Data.Ord
-- vertailee kahta arvoa annetun funktion "läpi"
comparing :: (Ord a) => (b -> a) -> b -> b -> Ordering
comparing f x y = compare (f x) (f y)

-- modulista Data.List
-- lajittelee listan käyttäen annettua vertailuoperaattoria
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

-- lajitellaan lista listoja pituuden mukaan
sortByLength :: [[a]] -> [[a]]
sortByLength = sortBy (comparing length)

sortByLength [[1,2,3],[4,5],[4,5,6,7]]   ==>  [[4,5],[1,2,3],[4,5,6,7]]

Kaksoispiste

Esitellään uusi operaattori ":"

Prelude> 1:[]
[1]
Prelude> 1:[2,3]
[1,2,3]
Prelude> tail (1:[2,3])
[2,3]
Prelude> head (1:[2,3])
1
Prelude> :t (:)
(:) :: a -> [a] -> [a]

: siis rakentaa uuden listan kun sille annetaan "head" ja "tail"
: on itseasiassa listakonstruktori: se palauttaa uuden linkitetyn listan solmun
Tässä kuva siitä, millaisen linkitetyn rakenteen [1,2,3] rakentaa:

   (:)
  /   \
 1    (:)
     /   \
    2    (:)
        /   \
       3    []

Listan rakentaminen

Nyt voimme määritellä listoja luovia rekursiivisia funktioita

laskevat 0 = []
laskevat n = n:laskevat (n-1)

laskevat 4 ==> [4,3,2,1]

iteroi f 0 x = [x]
iteroi f n x = x : iteroi f (n-1) (f x)

iteroi (*2) 4 3 ==> [3,6,12,24,48]

let xs = "terve"
in iteroi tail (length xs) xs
  ==> ["terve","erve","rve","ve","e",""]

Listojen hahmonsovitus

Koska : on konstruktori, sitä voi hahmonsovituksessa (lisää konstruktoreista myöhemmin)
Toinen listakonstruktori on []

myhead :: [Int] -> Int
myhead [] = -1
myhead (eka:loput) = eka

mytail :: [Int] -> [Int]
mytail [] = []
mytail (eka:loput) = loput

Hahmonsovitusta voi käyttää sisäkkäin: (a:b:_) on sama kuin (a:(b:_))

sumFirstTwo :: [Integer] -> Integer
sumFirstTwo (a:b:_) = a+b
sumFirstTwo _       = 0

Listan kuluttaminen

Listojen hahmonsovituksen avulla voimme helposti määritellä (rekursiivisen) funktion joka käsittelee listan kaikki alkiot

summaa :: [Int] -> Int
summaa [] = 0
summaa (x:xs) = x + summaa xs

maksimi :: [Int] -> Int
maksimi [] = 0       -- oikeastaan virhetilanne...
maksimi (x:xs) = go x xs
  where go suurin [] = suurin
        go suurin (x:xs) = go (max suurin x) xs

summaa2d :: [[Int]] -> Int
summaa2d []           = 0
summaa2d ([]:xss)     = summaa2d xss
summaa2d ((x:xs):xss) = x + summaa2d (xs:xss)

Listan rakentaminen ja kuluttaminen

Nyt osaamme rakentaa ja kuluttaa listoja. Tehdäänpä molemmat samassa funktiossa!

tuplaaLista :: [Int] -> [Int]
tuplaaLista [] = []
tuplaaLista (x:xs) = 2*x : tuplaaLista xs

tuplaaLista [1,2,3] ==> [2,4,6]

GHC:n toteutus mapille:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

GHC:n toteutus filterille:

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

Äärettömät listat

Huom! Tämä kalvo jää vähän roikkumaan sillä luennolla ei ehditty käsitellä laiskuutta. Esimerkit kuitenkin lienevät ymmärrettävissä.

Laiskuutta on helpoin demonstroida listoilla

Prelude> repeat 1
[1,1,1,1,
^C
Prelude> take 10 $ repeat 1
[1,1,1,1,1,1,1,1,1,1]
Prelude> take 20 $ repeat 1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Prelude> repeat 1 !! 13337
1

Prelude> take 10 . map (2^) $ [0..]
[1,2,4,8,16,32,64,128,256,512]

Prelude> take 4 . map (take 4) . tails $ cycle "asdf"
["asdf","sdfa","dfas","fasd"]

Tämä pyörii vakiomäärässä muistia

Prelude> head . filter (>10^4) $ map (3^) [0..]

Luento 3: `RealWorld -> (a,RealWorld)`

Sisältö

puhtaus
IO

Laiskuus & Puhtaus

Ensimmäisellä luennolla todettiin että Haskell on laiska
Laiskuus tarkoittaa, että mitään arvoa ei evaluoida jos sitä ei tarvita

f x = f x
g x y = x

Tämä ei pysähdy:

f 1

Mutta tämä toimii:

g 2 (f 1)  ==>  2

Laiskuus ei ole ongelma koska Haskell on puhdas (sivuvaikutukseton)
Siis vain funktioitten paluuarvoilla on merkitystä

Esimerkki

Laiskuus selittää miksi tämä viime luennon esimerkki toimii:

Prelude> head . filter (>100) $ map (3^) [0..]
243

Evaluoidaanpa!

    head (filter (>100) (map (3^) [0..]))
==> head (filter (>100) (map (3^) (0:[1..])))
==> head (filter (>100) (1 : map (3^) [1..]))
==> head (filter (>100) (map (3^) [1..]))
==> head (filter (>100) (map (3^) (1:[2..])))
==> head (filter (>100) (3 : map (3^) [2..]))
==> head (filter (>100) (map (3^) [2..]))
-- nyt ruvetaan hyppimään vähän isompia askelia
==> head (filter (>100) (9 : map (3^) [3..]))
==> head (filter (>100) (27 : map (3^) [4..]))
==> head (filter (>100) (81 : map (3^) [5..]))
==> head (filter (>100) (243 : map (3^) [6..]))
==> head (243 : filter (>100) (map (3^) [6..]))
==> 243

Teitä on huijattu

Oikeasti Haskell on (maailman paras) imperatiivinen ohjelmointikieli!
Aloitetaanpa:

kysely = do
  putStrLn "Kirjoita jotain!"
  s <- getLine
  putStrLn $ "Kirjoitit :"++s

import Network.HTTP
import Control.Monad

foo = do
  rsp <- Network.HTTP.simpleHTTP $ getRequest "http://www.cs.helsinki.fi/u/jkaasine/sanat"
  s <- getResponseBody rsp
  forM_ (words s) $ \s -> do
     putStrLn "sana:"
     putStrLn s

Hetkonen, mitä tässä oikein tapahtuu?

Prelude> :t putStrLn
putStrLn :: String -> IO ()
Prelude> :t getLine
getLine :: IO String

IO a on operaatio joka tuottaa tyyppiä a olevan tuloksen
() on nk. yksikkötyyppi, sen ainoa arvo on ()
Siispä:

Haskell-tyyppi	Java-tyyppi
`foo :: IO ()`	`void foo()`
`bar :: IO a`	`a bar()`
`f :: a -> b -> IO ()`	`void f(a arg0, b arg1)`
`g :: c -> IO d`	`d g(c arg)`

`do` as thou wilt

Näistä IO-operaatioista voi rakentaa isompia operaatioita käyttämällä do-syntaksia:

do operaatio
   operaatio
   muuttuja <- operaatioJokaPalauttaaJotain
   let muuttuja = lauseke
   operaatioJokaTuottaaPaluuarvon

Esimerkkejä

Standardikirjaston IO-operaatioita löytyy moduleista Prelude ja System.IO

kysely :: IO ()
kysely = do
  putStrLn "Kirjoita jotain!"
  s <- getLine
  let n = length s
  putStrLn $ "Kirjoitit "++show n++" merkkiä: "++s

palauttavaKysely :: String -> IO String
palauttavaKysely kysymys = do
  putStrLn kysymys
  getLine

`return`

return muuttaa normaalin arvon operaatioksi, joka palauttaa sen

tuotaKolme :: IO Int
tuotaKolme = return 3

Ei vaikuta kauhean hyödylliseltä, mutta do-syntaksin kanssa:

kyllaEiKysymys :: String -> IO Bool
kyllaEiKysymys kysymys = do
  putStrLn kysymys
  s <- getLine
  return $ s == "K"

HUOMIO! return ei lopeta operaation suoritusta vaikka nimen perusteella niin voisikin päätellä
return on funktio joka ottaa arvon ja palauttaa operaation, ei mitään muuta!
operaation paluuarvo tulee sen viimeisestä rivistä
tämä siis palauttaa 2:

do return 1
   return 2

`do` ja tyypit

do rakentaa IO <jotain> tyyppisen arvon

Esimerkki 1

foo = do
  ...
  vikaOp

vikaOp:n tyyppi on oltava muotoa IO X
foon tyyppi on myös sama IO X

Esimerkki 2

foo x y = do
  ...
  vikaOp arg

vikaOp:n tyyppi on oltava muotoa Y -> IO X
foon tyyppi on A -> B -> IO X, siten että x :: A ja y :: B.

Esimerkki 3

foo x = do
  ...
  return arg

foo:n tyyppi on A -> IO B, missä x :: A ja arg :: B

Kontrollirakenteita 1

Viime luvuista tutut keinot kuten rekursio, ehdot ja if-then-else toimivat IO-maailmassakin

tulostaKuvaus n
  | even n    = putStrLn "parillinen"
  | n==3      = putStrLn "kolme"
  | otherwise = print n

lueLukujaJaSummaa 0 = return 0
lueLukujaJaSummaa n = do
  i <- readLn
  s <- lueLukujaJaSummaa (n-1)
  return $ i+s

kysy :: [String] -> IO [String]
kysy [] = return []
kysy (kysymys:kysymykset) = do
  putStr kysymys
  putStrLn "?"
  vastaus <- getLine
  vastaukset <- kysy kysymykset
  return $ vastaus:vastaukset

Kontrollirakenteita 2

Lisäksi on kaikenlaisia kivoja kombinaattoreita (modulissa Control.Monad)

-- ehdollinen operaatio
when :: Bool -> IO () -> IO ()
-- ehdollinen operaatio, päinvastoin
unless :: Bool -> IO () -> IO ()
-- tee jotain monta kertaa
replicateM :: Int -> IO a -> IO [a]
-- tee jotain monta kerta, unohda tulos
replicateM_ :: Int -> IO a -> IO ()
-- tee jokin operaatio jokaiselle listan alkiolle
mapM :: (a -> IO b) -> [a] -> IO [b]
-- samoin mutta tuloksesta ei välitetä
mapM_ :: (a -> IO b) -> [a] -> IO ()
-- argumentit eri järjestyksessä, kätevämpi usein
forM  :: [a] -> (a -> IO b) -> IO [b]
forM_ :: [a] -> (a -> IO b) -> IO ()

lueLukujaJaSummaa n = do
  luvut <- replicateM n readLn
  return $ sum luvut

kysy :: [String] -> IO [String]
kysy kysymykset = do
  forM kysymykset $ \kysymys -> do
    putStr kysymys
    putStrLn "?"
    getLine

Hyödyllisiä operaatioita

stdin/stdout:

-- tulostaminen
putStr :: String -> IO ()
putStrLn :: String -> IO ()
print :: Show a => a -> IO ()
print = putStr . show
-- lukeminen
getLine :: IO String
readLn :: Read a => IO a

tiedostot (modulista System.IO):

-- yksinkertaiset operaatiot:
readFile :: FilePath -> IO String
writeFile :: FilePath -> String -> IO ()
-- tiedostokahvat
openFile :: FilePath -> IOMode -> IO Handle   -- IOMode on joko ReadMode, WriteMode, tai ReadWriteMode
hPutStr :: Handle -> String -> IO ()
hPutStrLn :: Handle -> String -> IO ()
hPrint :: (Show a) => Handle -> a -> IO ()
hGetLine :: Handle -> IO String
-- jne

Merkkijonojen käsittelyä

Tässä muutama hyödyllinen funktio:

-- pilko merkkijono riveiksi
lines :: String -> [String]
-- rakenna merkkijono riveistä
unlines :: [String] -> String
-- pilko merkkijono sanoiksi
words :: String -> [String]
-- rakenna merkkijono sanoista
unwords :: [String] -> String
-- lue merkkijono arvoksi
read :: Read a => String -> a
-- muuta arvo merkkijonoksi
show :: Show a => a -> String

Tehdäänpä jotain oikeaa

Haetaan kaikista tämän hakemiston alla olevista .hs-tiedostoista tyyppiannotaatiot

import System.IO
import System.Directory
import Data.List
import Control.Monad

isTypeSignature :: String -> Bool
isTypeSignature s = not (elem '=' s) && find == "::"
  where find = take 2 $ dropWhile (/=':') s

readTypesFile :: FilePath -> IO [String]
readTypesFile file = do content <- readFile file
                        let ls = lines content
                        return $ filter isTypeSignature ls

readTypesDir :: FilePath -> IO [String]
readTypesDir path = do contents <- getDirectoryContents path
                       typess <- forM (filter ok contents) $ \entry -> do
                           let qualified = path ++ "/" ++ entry
                               match = isSuffixOf "hs" qualified
                           dir <- doesDirectoryExist qualified
                           case (dir,match) of
                             (True,  _)    -> readTypesDir qualified
                             (False, True) -> readTypesFile qualified
                             _             -> return []
                       return $ concat typess
  where ok "." = False
        ok ".." = False
        ok _ = True

Mitä tämä tarkoittaa?

Palataanpa funktionaaliseen maailmaan
putStrLn :: String -> IO () on puhdas funktio joka palauttaa operaation
Mitä puhtaus tarkoittikaan? Sitä, että putStrLn x on aina sama kun x on sama.
Siis: operaatio on puhdas kuvaus sivuvaikutusketjusta
Vasta operaation suorittaminen aiheuttaa sivuvaikutukset
Kun Haskell-ohjelma ajetaan, ainoastaan yksi operaatio suoritetaan
- sen nimi on main :: IO ()
- muita operaatioita saa suoritettua vain liittämällä ne osaksi mainia
Lisäksi GHCi suorittaa operaatioita

Operaatiot ovat arvoja

Operaatiot ovat arvoja, aivan niin kuin luvut, listat, funktiotkin
Tehdäänpä siis hieman korkeamman tason koodia

valinta :: IO a -> IO a -> IO a
valinta a b =
  do putStr "1 vai 2? "
     i <- readLn
     case i of 1 -> a
               2 -> b
               _ -> do putStrLn "Väärin!"
                       valinta a b

C-perheen kielissä on oikosulkeva &&-operaattori, joka on hyödyllinen sivuvaikutuksellisissa kielissä.
Toteutetaanpa sama Haskellissa!

cand :: IO Bool -> IO Bool -> IO Bool
cand a b = do bool <- a
              if bool
                then b
                else return False

b:n sivuvaikutukset tapahtuvat vain jos a palautti True

Operaatiot ovat arvoja: lisäesimerkki

Koodataanpa "open process close" idiomi funktioksi opc

opc :: IO a -> (a -> IO b) -> (a -> IO ()) -> IO b
opc open process close = do
   resource <- open
   result <- process resource
   close resource
   return result

Nyt voidaan esimerkiksi määritellä:

firstLineOfFile path = opc (openFile path ReadMode) hGetFile hClose
withFile path op = opc (openFile path ReadMode) op hClose

Tai (tietokantafunktiot kuvitteellisia):

connectDatabase :: IO Connection
execStmt :: Connection -> Statement -> IO Result
closeConnection :: Connection -> IO ()

execSqls :: [Statement] -> IO [Result]
execSqls stmts = opc connectDatabase (\conn -> mapM (execStmt conn) stmts) closeConnection

Vielä pari pikkujuttua: `case`

Ensimmäisen viikon tehtävissäkin kummitellut case-lauseke toimii näin:

case lauseke of
  hahmo -> lauseke
  hahmo -> lauseke

Esimerkiksi:

myHead :: [Int] -> Int
myHead xs = case xs of (x:_) -> x
                       []    -> -1

Vielä pari pikkujuttua: tuplet

Tuplet eli parit (ja kolmikot, nelikot, jne) ovat tapa iskeä monta erityyppistä arvoa yhteen
Tyyppi kirjoitetaan näin: (a,b) tai (a,b,c) jne
Arvot kirjoitetaan näin: (1+1,True)
Tuplesta saa arvoja ulos kahdella funktiolla:

fst :: (a, b) -> a
snd :: (a, b) -> b

Esimerkkejä

findWithIndex :: (a -> Bool) -> [a] -> (a,Int)
findWithIndex p xs = go 0 xs
  where go i (x:xs)
          | p x       = (x,i)
          | otherwise = go (i+1) xs

Prelude Data.List> :t partition
partition :: (a -> Bool) -> [a] -> ([a], [a])
Prelude Data.List> partition (>0) [-1,1,-4,3,2,0]
([1,3,2],[-1,-4,0])

Tupleja voi tietenkin hahmonsovittaa

Prelude Data.List> case partition (>0) [-1,1,-4,3,2,0] of (a,b) -> a++b
[1,3,2,-1,-4,0]

Luento 4: You Need String for a Knot

Sisältö

Tyyppijärjestelmää
Omien tietotyyppien määritteleminen

Algebralliset tietotyypit: intro

Tässä tuttujen tietotyyppien Bool ja Ordering määritelmät suoraan standardikirjastosta:

data Bool = True | False
data Ordering = LT | EQ | GT

Tällä syntaksilla voit itsekin määritellä Orderingin tapaisia asioita:

data Color = Red | Green | Blue

rgb :: Color -> [Double]
rgb Red = [1,0,0]
rgb Green = [0,1,0]
rgb Blue = [0,0,1]

Prelude> :t Red
Red :: Color
Prelude> :t [Red,Blue,Green]
[Red,Blue,Green] :: [Color]
Prelude> rgb Red
[1.0,0.0,0.0]

Algebralliset tietotyypit: kentät

data-syntaksi yleistyy muunkinlaisiin tietotyyppeihin. Tässä esimerkiksi määrittelemme raportin, jolla on id-numero, otsikko ja sisältö.

data Report = MkReport Int String String

Raportteja voi luoda esimerkiksi näin:

Prelude> :t MkReport 1 "a" "b"
MkReport 1 "a" "b" :: Report

Ja niitä voi käsitellä hahmonsovituksella:

reportContents :: Report -> String
reportContents (MkReport id title contents) = contents
setReportContents :: String -> Report -> Report
setReportContents contents (MkReport id title _contents) = MkReport id title contents

Algebralliset tietotyypit: konstruktorit

data-määritelmän oikealla puolella olevia asioita kutsutaan konstruktoreiksi: True, False, LT, MkReport, ...
Kuten näimme aikaisemmin, voidaan yhteen tyyppiin liittää useita konstruktoreita |-syntaksilla
Esitetäänpä korttipakan kortit:

data Card = Joker | Heart Int | Club Int | Spade Int | Diamond Int

Konstruktorit ovat funktioita:

Prelude> :t Heart
Heart :: Int -> Card
Prelude> :t Nothing
Nothing :: Maybe a
Prelude> :t Left
Left :: a -> Either a b

Niitä voi käyttää kuten funktioita:

Prelude> map Left [1,2,3]
[Left 1,Left 2,Left 3]
Prelude> (Just . Just . Just) 3
Just (Just (Just 3))

`deriving Show`

Pieni huomautus tähän väliin

Prelude> EQ
EQ
Prelude> True
True
Prelude> Joker
<interactive>:1:0:
    No instance for (Show Card)
      arising from a use of `print' at <interactive>:1:0-4
    Possible fix: add an instance declaration for (Show Card)
    In a stmt of a 'do' expression: print it

GHC ei osaa tulostaa määrittelemiämme tyyppejä toisin kuin valmiiksi määriteltyjä
Tähän on helppo ratkaisu: deriving Show:

data Card = Joker | Heart Int | Club Int | Spade Int | Diamond Int
  deriving Show

Prelude> Joker
Joker

Opimme mitä deriving ja Show ovat ensi viikolla!

Esimerkki 1: Maybe I'm Amazed

Joskus operaatiolla ei ole järkevää paluuarvoa. Tällöin mahdollisuuksia ovat:
- Keksitään arvo, esim -1 — rumaa, ei aina mahdollista
- Poikkeus — epäpuhdas
- Maybe — puhdas ja turvallinen
Maybe a on tyyppi, jonka arvoja ovat Nothing ja Just x, missä x :: a

Tyyppi	Arvot
`Maybe Bool`	`Nothing`, `Just False`, `Just True`
`Maybe Int`	`Nothing`, `Just 0`, `Just 1`, ...
`Maybe [Int]`	`Nothing`, `Just []`, `Just [1,1337]`, ...

Voit ajatella että Maybe a on hieman niinkuin [a], paitsi että arvoja on 0 tai 1 kpl eikä mielivaltainen määrä.

Esimerkki 1: jatkuu

Mayben käyttäminen on helppoa: hahmonsovitus

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x

headOrZero :: [Int] -> Int
headOrZero xs = case safeHead xs of Nothing -> 0
                                    Just x -> x

Maybe tyypin määritelmä on:

data Maybe a = Nothing | Just a

mikä on a? Se selviää seuraavaksi.

Algebralliset tietotyypit: tyyppiparametrit

Haskellin tietotyypeillä voi olla parametreina tosia tyyppejä
Tässä on jotain samaa Javan genericsien ja C++:n templatejen kanssa
- vertaa: [Integer], List<Integer>
Yksinkertaisin esimerkki:

data Wrap a = MkWrap a
unwrap (MkWrap a) = a

Prelude> :t MkWrap
MkWrap :: a -> Wrap a
Prelude> :t unwrap
unwrap :: Wrap a -> a
Prelude> :t MkWrap True
MkWrap True :: Wrap Bool
Prelude> :t MkWrap []
MkWrap [] :: Wrap [a]

Kertauksena:

data Maybe a = Nothing | Just a

Syntaktinen huomautus

Tyyppimuuttujat ja funktioitten ja arvojen nimet alkavat pienellä kirjaimella
- a, map, xs, ...
Tyyppien nimet ja tyyppien konstruktorit alkavat molemmat isoilla kirjaimilla
- Maybe, Just, Card, Heart, ...
Tyypeissä ja konstruktoreissa on sekaannuksen vaara
varsinkin koska tyypin ja konstruktorin nimi voi olla sama:

data Wrap a = Wrap a
data Report = Report Int String String

Onneksi tyypit ja konstruktorit eivät voi koskaan esiintyä samassa paikassa:

Prelude> Maybe

<interactive>:1:0: Not in scope: data constructor `Maybe'
Prelude> undefined :: Nothing

<interactive>:1:13:
    Not in scope: type constructor or class `Nothing'

Esimerkki 2: Either

Joskus olisi kiva jos Nothingiin voisi liittää esim. kuvauksen virheestä
Hätiin astuu tyyppi Either!

data Either a b = Left a | Right b

Maybe antoi meidän palauttaa jonkin arvon tai ei mitään
Either antaa meidän palauttaa arvon joka on joko tyyppiä a tai tyyppiä b
Huomatkaa: kaksi tyyppiparametriä (a ja b)!
Yksinkertainen esimerkki: virheen raportointi

readInt :: String -> Either String Int
readInt "0" = Right 0
readInt "1" = Right 1
readInt s = Left ("Unsupported string "++show s)

Esimerkki 2: jatkuu

Esimerkki: välitetään Eitherillä tieto siitä milloin iterointi pitää lopettaa:

iterateE :: (a -> Either b a) -> a -> b
iterateE f x = case f x of Left y  -> y
                           Right y -> iterateE f y

step :: Int -> Int -> Either Int Int
step k x = if x>k then Left x else Right (2*x)

goThru :: [a] -> Either a [a]
goThru [x] = Left x
goThru (x:xs) = Right xs

Prelude> iterateE (step 100) 1
128
Prelude> iterateE (step 1000) 3
1536
Prelude> iterateE goThru [1,2,3,4]
4

Rekursiiviset tietotyypit

Tietotyypitkin voivat olla rekursiivisia
Tämä ei ole yhtään sen ihmeellisempää kuin olio, jossa on viittaus saman luokan olioon
Esimerkki: lista kokonaislukuja

data IntList = Empty | Node Int IntList
  deriving Show

ihead :: IntList -> Int
ihead (Node i _) = i

itail :: IntList -> IntList
itail (Node _ t) = t

ilength Empty = 0
ilength (IntList _ t) = 1 + ilength t

Esimerkki 3: Lista

Tehdäänpä sama tyyppiparametrilla!
Tämä tyyppi on käytännössä sama kuin listatyyppi [a]:

data List a = Empty | Node a (List a)
  deriving Show

lhead :: List a -> a
lhead (Node h _) = h

ltail :: List a -> List a
ltail (Node _ t) = t

lnull :: List a -> Bool
lnull Empty = True
lnull _     = False

llength :: List a -> Int
llength Empty = 0
llength (Node _ t) = 1 + llength t

Esimerkki 4: Puu

Vastaavasti kuin listan, voimme esittää binääripuun:

data Tree a = Leaf | Node a (Tree a) (Tree a)

Puussamme on lehtiä eli tyhjiä puita: Leaf
ja solmuja, Node, joilla on arvo ja kaksi alipuuta
Esimerki: puun korkeuden laskeminen

treeHeight :: Tree a -> Int
treeHeight Leaf = 0
treeHeight (Node _ l r) = 1 + max (treeHeight l) (treeHeight r)

treeHeight Leaf ==> 0
treeHeight (Node 2 Leaf Leaf)
  ==> 1 + max (treeHeight Leaf) (treeHeight leaf)
  ==> 1 + max 0 0
  ==> 1
treeHeight (Node 1 Leaf (Node 2 Leaf Leaf))
  ==> 1 + max (treeHeight Leaf) (treeHeight (Node 2 Leaf Leaf))
  ==> 1 + max 0 1
  ==> 2
treeHeight (Node 0 (Node 1 Leaf (Node 2 Leaf Leaf)) Leaf)
  ==> 1 + max (treeHeight (Node 1 Leaf (Node 2 Leaf Leaf))) (treeHeight Leaf)
  ==> 1 + max 2 0 
  ==> 3

Esimerkki 4: jatkuu

Lisäesimerkki: binäärihakupuun lisäys ja haku

insert :: Int -> Tree Int -> Tree Int
insert x Leaf = Node x Leaf Leaf
insert x (Node y l r)
  | x < y = Node y (insert x l) r
  | x > y = Node y l (insert x r)
  | otherwise = Node y l r

lookup :: Int -> Tree Int -> Bool
lookup x Leaf = False
lookup x (Node y l r)
  | x < y = lookup x l
  | x > y = lookup x r
  | otherwise = True

Yhteenveto

omia tyyppejä määritellään näin:

data TyypinNimi = Konstruktori1 Tyyppi1 Tyyppi2 | Konstruktori2 Tyyppi3 | Konstruktori3

tai näin, jos käytämme tyyppimuuttujia

data TyypinNimi muuttuja = Kons1 muuttuja Tyyppi1 | Kons2 Tyyppi2 muuttuja

konstruktoreita voi olla yksi tai useampi, ja jokaisella voi olla nolla tai useampi kenttää
konstruktorin ja tyypin nimi Alkavat Isolla Alkukirjaimella, tyyppimuuttujan nimi pienellä
arvoja käsitellään hahmonsovituksella

foo (Konstruktori1 a b) = a+b
foo (Konstruktori2 _) = 0
foo Konstruktori3 = 7

konstruktorit ovat vain funktioita

Konstruktori1 :: Tyyppi1 -> Tyyppi2 -> TyypinNimi
Kons1 :: a -> Tyyppi1 -> TyypinNimi a

Yleisön pyynnöstä: listakomprehensiot

Hauska syntaksi listojen rakentamiseen
Yhdistää mapin ja filterin

[2*i | i<-[1,2,3]]
  ==> [2,4,6]

let f = (2*)
    lis = [0..10]
in [f x | x<-lis]
  ==> [0,2,4,6,8,10,12,14,16,18,20]

[(x,y) | x <- [1..7], even x, y <- [True,False]]
  ==> [(2,True),(2,False),(4,True),(4,False),(6,True),(6,False)]

Nämä ovat ekvivalentteja:

[f x | x <- lis, p x]
map f (filter p lis)

Muuta hauskaa: omat operaattorit

Haskellissa operaattori on mikä tahansa merkeistä !#$%&*+./<=>?@\^|-~ koostuva merkkijono
Operaattoreita määritellään aivan kuin funktioita (mutta huomaa hiukan erilainen tyyppiannotaatio):

(<+>) :: [Int] -> [Int] -> [Int]
xs <+> ys = zipWith (+) xs ys

(+++) :: String -> String -> String
a +++ b = a ++ " " ++ b

Funktioita voi käyttää operaattoreina `foo`-syntaksilla:

Prelude> 5 `div` 2
2
Prelude> (+1) `map` [1,2,3]
[2,3,4]

Luento 5: fmap fmap fmap

Sisältö

Tyyppiluokat
Evaluoinnista

Tyyppiluokat

Miksi Haskellissa sama operaattori + osaa lisätä sekä Intejä että Doubleja?
Miksi operaattorilla == voi vertailla kaikenlaista?

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

Tyyppi (Eq a) => a -> a -> Bool voidaan lukea: sellaisille tyypeille a, jotka kuuluvat luokkaan Eq, tämä on funktio a -> a -> Bool
Tyyppiluokka (type class) on tapa määritellä operaatioita jotka toimivat usealle tyypille. Esimerkiksi luokka Eq määrittelee tutun vertailuoperaattorin ==.

data Color = Black | White

instance Eq Color where
  Black == Black  = True
  White == White  = True
  _     == _      = False

Huom! tyyppiluokka on luokka eli joukko tyyppejä. Sillä ei ole paljoakaan tekemistä olio-ohjelmoinnin luokan kanssa!
Jos jonkun analogian haluaa, niin tyyppiluokat vastaavat (joissain käyttötarkoituksissaan) rajapintaluokkia
Valitettavasti sekaannusta lisää se että tyyppiluokan määrittelemiä funktioita kutsutaan usein metodeiksi

Tyyppirajoitteet

Luokkametodien käyttö kun käytössä on konkreettinen tyyppi (ei tyyppimuuttuja) on suoraviivaista

f :: (Int -> Int) -> Int -> Bool
f g x = x == g x

Tyyppimuuttujien tapauksessa pitää tyyppiin lisätä tyyppirajoite (type constraint)
Ei toimi:

f :: (a -> a) -> a -> Bool
f g x = x == g x

Onneksi virhe on hyvä:

    Could not deduce (Eq a) from the context ()
      arising from a use of `==' at <interactive>:1:40-47
    Possible fix:
      add (Eq a) to the context of the type signature for `f'
    In the expression: x == g x
    In the definition of `f': f g x = x == g x

Toimii:

f :: (Eq a) => (a -> a) -> a -> Bool
f g x = x == g x

Tyyppirajoitteet: jatkuu

Tyyppiannotaation puuttuessa tyypinpäättely osaa tuottaa tyyppirajoitteet!

Prelude> let f g x = x == g x
Prelude> :t f
f :: (Eq a) => (a -> a) -> a -> Bool

Tyyppirajoitteita voi olla useampiakin

g :: (Eq a, Eq b) => a -> a -> b -> b -> Bool
g a0 a1 b0 b1 = a0 == a1 || b0 == b1

Tyyppiluokan määritteleminen

Tyyppiluokka määritellään class-syntaksilla. Luokan metodeille annetaan tyypit.

class Size a where
  size :: a -> Int

Instanssit määritellään instance-syntaksilla

instance Size Int where
  size x = x

instance Size [a] where
  size xs = length xs

Luokka voi sisältää useita funktioita ja vakioita

class Foo a where
  empty :: a
  size :: a -> Int
  sameSize :: a -> a -> Bool

instance Foo (Maybe a) where
  empty = Nothing

  size Nothing = 0
  size (Just a) = 1

  sameSize x y = size x == size y

instance Foo [a] where
  empty = []
  size xs = length xs
  sameSize x y = size x == size y

Huom! Yllä näet yhden (Haskell2010-) tyyppiluokkien oleellisimmista rajoituksista:
- Tyypille Maybe Int ei voi määritellä instansseja mutta tyypille Maybe a voi
- Instanssit eivät siis saa riippua tyyppiparametreista
- Kieleen on laajennoksia jotka sallivat monimutkaisempia instansseja

Oletustoteutukset

Tyyppiluokan metodeille voi antaa oletustoteutukset (ajattele: oliokielien abstrakti luokka)

class Example a where
  example :: a
  examples :: [a]
  examples = [example]

instance Example Int where
  example = 1
  examples = [0,1,2]

instance Example Bool where
  example = True

class Combine a where
  combine :: a -> a -> a
  combine3 :: a -> a -> a -> a
  combine3 x y z = combine x (combine y z)

Jos haluaa käyttää oletustoteutusta, voi vastaavan metodin vain jättää määrittelemättä instance-määritelmässä.

Instanssihierarkia

Sekä luokat että instanssit voivat muodostaa hierarkioita
Instanssihierarkiassa tarvitset jotain toista instanssia määritelläksesi uuden instanssin

class Foo a where
  foo :: a -> Int

instance Foo Int where
  foo x = x

instance Foo a => Foo [a] where
  foo xs = sum (map foo xs)

Huom: Näin tavallaan kierrämme rajoitusta siitä että instanssi Foo [Int] ei ole mahdollinen!

Luokkahierarkia

Vastaavasti luokka voi vaatia että toinen luokka on toteutettuna
Tästä on apua esimerkiksi jos haluaa käyttää toisen luokan metodeja oletustoteutuksissa

class Foo a where
  foo :: a -> Int

class Foo a => Bar a where
  bar :: a -> a -> Int
  bar x y = foo x + foo y

Näemme lisää esimerkkejä seuraavilla kalvoilla
Terminologiaa: Sanotaan että Bar on Foon aliluokka (subclass)
- Taas lainataan olemassaolevaa sanastoa ja annetaan sille eri merkitys...

Valmiita tyyppiluokkia: Eq, Ord

Eq kuvaa yhtäsuuruutta, Ord vertailua
Huomaa: kaikilla operaatioilla oletustoteutukset toistensa suhteen
Näin koodaaja saa valita helpoimman toteutustavan

class  Eq a  where  
      (==), (/=)  ::  a -> a -> Bool  

      x /= y  = not (x == y)  
      x == y  = not (x /= y)

class  (Eq a) => Ord a  where  
  compare              :: a -> a -> Ordering  
  (<), (<=), (>=), (>) :: a -> a -> Bool  
  max, min             :: a -> a -> a  

  compare x y | x == y    = EQ  
              | x <= y    = LT  
              | otherwise = GT  

  x <= y  = compare x y /= GT  
  x <  y  = compare x y == LT  
  x >= y  = compare x y /= LT  
  x >  y  = compare x y == GT  

  -- Note that (min x y, max x y) = (x,y) or (y,x)  
  max x y | x <= y    =  y  
          | otherwise =  x  
  min x y | x <= y    =  x  
          | otherwise =  y

Esimerkki: parityyppi

Tässä erään tyypin Eq ja Ord -instanssit
Huomaa että pelkkä <=-operaattorin määritteleminen riittää oletustoteutusten takia!
- Termi tälle on minimal complete definition, ja sitä käytetään usein luokkien dokumentaatiossa (ks. Ord)

data Pair a = MkPair a a
  deriving Show

instance Eq a => Eq (Pair a) where
  MkPair a b == MkPair c d  = a==c && b==d

instance Ord a => Ord (Pair a) where
  MkPair a b <= MkPair c d
     | a<c       = True
     | a>c       = False
     | otherwise = b<=d

*Main> (MkPair 1 2) < (MkPair 2 3)
True
*Main> (MkPair 1 2) > (MkPair 2 3)
False
*Main> compare (MkPair 1 2) (MkPair 2 3)
LT

Valmiita tyyppiluokkia: Num

Num-luokka sisältää osan normaaleista laskutoimituksista, sekä muutaman kummallisen operaation.
Haskellissa on myös muita luokkia lukutyyppejä varten, ks. esim. seuraava kalvo.
On kyllä hiukan kummallista että Num vaatii Eq:n ja Show:n ...

class  (Eq a, Show a) => Num a  where  
    (+), (-), (⋆)  :: a -> a -> a  
    negate         :: a -> a  
    abs, signum    :: a -> a  
    fromInteger    :: Integer -> a

Muita valmiita tyyppiluokkia

Read: arvojen lukeminen, read :: Read a => String -> a
Show: arvojen tulostaminen, show :: Show a => a -> String
Enum: mahdollistaa [x..y]-syntaksin
Integral: kokonaislukutyypit: div, mod, toInteger
Fractional: jakolasku
Floating: liukulukuoperaatiot: exp, sin, pi...

Haskell 2010 -tyyppiluokat

`deriving`

Kalvoilla ja tehtävissä kummitellut deriving on tapa tuottaa automaattisia instansseja muutamasta perustyyppiluokasta:
- Read, Show, Eq ovat tärkeimmät
Automaattiset instanssit ovat suoraviivaisia
- show tulostaa arvon kuten se kirjoitetaan lähdekoodissa
- read lukee arvoja joita show tuottaa
- == vertailee kaikkia kenttiä

Kaikenlaisia mappeja

map, eli kasan arvoja muuttaminen funktion avulla on hyvin yleinen idea:

mapList :: (a->b) -> [a] -> [b]
mapList _ [] = []
mapList f (x:xs) = f x : mapList f xs

mapMaybe :: (a->b) -> Maybe a -> Maybe b
mapMaybe _ Nothing = Nothing
mapMaybe f (Just x) = Just (f x)

data Tree a = Leaf | Node a (Tree a) (Tree a)

mapTree _ Leaf = Leaf
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)

Kaikenlaisia funktoreita

Määritellään siis tyyppiluokka, joka vastaa yleistä map-operaatiota:

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

Nimi Functor on se jolla tämä luokka on standardikirjastossa
Huom! f ei ole tyyppi vaan tyyppimuodostin
- Instansseja voi siis määritellä tyyppien lisäksi tyyppimuodostimille. Tällöin muodostimelle annettu tyyppiargumentti pääsee vaihtumaan kuten fmapissa.
- Listatyypin tyyppimuodostin kirjoitetaan [], hassua

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

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

instance Functor Tree where
  fmap _ Leaf = Leaf
  fmap f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)

Functor on siis tyyppiluokka joka kuvaa jotain joka käyttäytyy kuten säiliö

Miten Haskell toimii?

Pari luentoa sitten puhuttiin hieman laiskuudesta
Syvennetäänpä aihetta hieman!
Näytän alla miten sama lauseke sieventyy (eli miten se lasketaan) C-tyylisessä kielessä ja Haskellissa.

not True = False
not False = True
map f [] = []
map f (x:xs) = f x : map f xs
length [] = 0
length (x:xs) = 1+length xs

C-tyyliset kielet

Funktion argumentit evaluoidaan täysin ennen funktiokutsua

length (map not (True:False:[]))
  ==> length (False:True:[])
  ==> 2

Haskell

Funktion argumentteja evaluoidaan vain sen verran kuin tarvitsee

length (map not (True:False:[]))
  ==> length (not True : map not (False:[]))
  ==> 1 + length (map not (False:[]))
  ==> 1 + length (not False : map not ([]))
  ==> 1 + 1 + length (map not [])
  ==> 1 + 1 + length []
  ==> 1 + 1 + 0
  ==> 2

Sieviä normaalimuotoja

Haskellista puhuttaessa on hyödyllistä tunnistaa erityyppisiä sievennyksen tuotteita
Arvo on lauseke jota ei enää voi sieventää, t.s. täysin laskettu lauseke
- Esimerkkejä: 1, True, Just (1,2), 0:4:[] eli [0,4]
Heikossa päämuodossa (Weak Head Normal Form eli tuttavallisesti WHNF) oleva lauseke on sellainen jonka ylintä tasoa ei enää voi sieventää.
- Konstruktorit: Just (f 1), 0:filter f xs, ...
- Funktiot: (\x -> 1+1)
Haskell ei evaluoi mitään ellei ole pakko
Evaluoinnin pakottaa (lähinnä) hahmonsovitus
Kun halutaan evaluoida (esimerkiksi) lauseke tyyppiä

case x of Foo y -> ...
          Bar w z -> ...

on pakko laskea x heikkoon päämuotoon että tietäisimme kumpaa haaraa seurata

Yksityiskohtainen esimerkki 1

not :: Bool -> Bool
not True = False
not False = True

(||) :: Bool -> Bool -> Bool
True || _ = True
_    || x = x

even x  =  x == 0  ||  not (even (x-1))

Huomaa että || pakottaa vasemman argumenttinsa, muttei oikeaansa. (Hahmonsovitus)
Tästä seuraa että even pakottaa (välillisesti) ensimmäisen argumenttinsa: || pakottaa x==0:n ja == pakottaa x:n.

even 2
  ==> 2 == 0  ||  not (even (2-1))
  ==> False   ||  not (even (2-1))
  ==> not (even (2-1))
  ==> not ((2-1) == 0 || not (even ((2-1)-1)))
  ==> not (  1   == 0 || not (even (  1  -1)))               -- jakaminen
  ==> not (  False    || not (even (1-1)))
  ==> not (not (even (1-1)))
  ==> not (not ((1-1) == 0 || not (even ((1-1)-1))))
  ==> not (not (  0   == 0 || not (even (  0  -1))))         -- jakaminen
  ==> not (not (   True    || not (even (0-1))))
  ==> not (not True)
  ==> not False
  ==> True

Tällä määritelmällä even ei olisi toiminut:

even' x =  not (even (x-1))  ||  x == 0

Jakaminen

Semanttisesti let sievennetään tällä tavalla:

let x = e in f x (g x y)
  ==> f e (g e y)

Kuitenkin oikeasti letillä (tai millä tahansa muulla keinolla) luotu nimi evaluoidaan korkeintaan kerran
- Tämä on loistava nyrkkisääntö koodatessa: nimi evaluoidaan korkeintaan kerran
Esimerkki: kun * pakottaa vasemman argumenttinsa, lasketaan samalla myös oikea sillä ne viittasivat samaan nimeen

let x = (2+2) in x*x
  ==> 4*4
  ==> 16

Sanotaan että arvo x jaetaan
Jakamista tapahtu myös tietorakenteitten kanssa. Esimerkiksi tämä:

let x = [1,2,3] in (0:x,1:x)

Näyttää täysin evaluoituna muistissa tältä:

Jakamisen vaarat

Jakaminen on monesti hyödyksi: tarvitaan vähemmän laskentaa
Kuitenkin joskus liika jakaminen aiheuttaa muistinkäytön kasvamisen
Esimerkki: Tämä toimii nopeasti ja vakiotilassa koska lista kulutetaan heti kun se luodaan:

length [1..100000000] + length [1..100000000]

mutta tämä täyttää muistin koska lista x lasketaan vain kerran:

let x = [1..100000000] in length x + length x

Yksityiskohtainen esimerkki 2

Nyt voimme ymmärtää jo pariin kertaan kierrätetyn laiskuusesimerkin oikeasti:

    head (filter (>100) (map (3^) [0..]))
==> head (filter (>100) (map (3^) (0:[1..])))
==> head (filter (>100) ((3^0) : map (3^) [1..]))
==> head (filter (>100) (1 : map (3^) [1..]))     -- (>100) pakottaa 3^0:n evaluoinnin
==> head (filter (>100) (map (3^) (1:[2..])))
==> head (filter (>100) ((3^1) : map (3^) [2..]))
==> head (filter (>100) (3 : map (3^) [2..]))
==> head (filter (>100) (map (3^) [2..]))
-- nyt ruvetaan hyppimään vähän isompia askelia
==> head (filter (>100) (9 : map (3^) [3..]))
==> head (filter (>100) (27 : map (3^) [4..]))
==> head (filter (>100) (81 : map (3^) [5..]))
==> head (filter (>100) (243 : map (3^) [6..]))
==> head (243 : filter (>100) (map (3^) [6..]))
==> 243

Luento 6: A Monoid in the Category of Problems

Esimerkki 1: Maybejä

Jos työskentelemme useitten Maybe-tyyppien kanssa, koodista tulee helposti ikävää

lookup :: (Eq a) => a -> [(a, b)] -> Maybe b

increase :: Eq a => a -> Int -> [(a,Int)] -> Maybe [(a,Int)]
increase key val assocs =
  case lookup key assocs
  of Nothing -> Nothing
     Just x -> if (val < x)
                then Nothing
                else Just ((key,val) : delete (key,x) assocs)

Tälläinen koodi on hyvin yleistä ja hyvin säännöllistä: jos yksikin välitulos on Nothing, koko laskenta on Nothing
Määritellään siis ketjutusoperaattori ?>
- tulos + laskennan seuraava vaihe ==> uusi tulos

(?>) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing ?> _ = Nothing   -- kun on kerran epäonnistuttu, ei tehdä enää mitään
Just x  ?> f = f x       -- jos onnistuttiin, jatketaan

increase key val assocs =
    lookup key assocs ?> 
    check ?>
    mk
  where check x
           | x < val   = Nothing
           | otherwise = Just x
        mk x = Just ((key,val) : delete (key,x) assocs)

Esimerkki 1 jatkuu

Tässä yksinkertaisempi esimerkki: safeHeadin ja safeTailin käyttöä ketjutuksen kanssa

(?>) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing ?> _ = Nothing   -- kun on kerran epäonnistuttu, ei tehdä enää mitään
Just x  ?> f = f x       -- jos onnistuttiin, jatketaan

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (x:xs) = Just xs

safeThird xs = safeTail xs ?> safeTail ?> safeHead

safeNth 0 xs = safeHead xs
safeNth n xs = safeTail xs ?> safeNth (n-1)

safeThird [1,2,3,4]
  ==> Just 3
safeThird [1,2]
  ==> Nothing
safeNth 5 [1..10]
  ==> Just 6
safeNth 11 [1..10]
  ==> Nothing

Esimerkki 2: Loki

Tyyppi Logger liittää arvoon listan lokiviestejä (jotka arvon laskeminen on tuottanut)
Käytetään samaa ketjutusideaa kuin edellä

data Logger a = Logger [String] a  deriving Show

getVal (Logger _ a) = a
getLog (Logger s _) = s

nomsg x = Logger [] x
annotate s x = Logger [s] x
msg s = Logger [s] ()

(#>) :: Logger a -> (a -> Logger b) -> Logger b
Logger la a #> f = Logger (la++lb) b
  where Logger lb b = f a

(##>) :: Logger a -> Logger b -> Logger b
Logger la _ ##> Logger lb b = Logger (la++lb) b

-- lasketaan lauseke 2*(x^2+1)
laske x = 
  annotate "^2" (x*x)
  #>
  \x -> annotate "+1" (x+1)
  #>
  \x -> annotate "*2" (x*2)

filterLog :: (Eq a, Show a) => (a -> Bool) -> [a] -> Logger [a]
filterLog f [] = nomsg []
filterLog f (x:xs)
   | f x       = msg ("keeping "++show x) ##> filterLog f xs #> (\xs -> nomsg (x:xs))
   | otherwise = msg ("dropping "++show x) ##> filterLog f xs

laske 3
  ==> Logger ["^2","+1","*2"] 20
filterLog (>0) [1,-2,3,-4,0]
  ==> Logger ["keeping 1","dropping -2","keeping 3","dropping -4","dropping 0"] [1,3]

Esimerkki 3: Tilan päivittäminen

Edellisessä esimerkissä vain tallensimme tilaa (eli lokia)
Joskus haluamme että laskenta riippuu tilasta
Yksinkertainen esimerkki: numeroidaan puun solmut vasemmalta oikealle

data Tree a = Leaf | Node a (Tree a) (Tree a)

numeroi tree = t
  where (t,i) = numeroi' 0 tree

numeroi' :: Int -> Tree a -> (Tree Int, Int)
numeroi' start Leaf = (Leaf,start)
numeroi' start (Node _ l r) = (Node i l' r', end)
  where (l',i)   = numeroi' start l
        (r',end) = numeroi' (i+1) r

numeroi (Node 0 (Node 0 (Node 0 Leaf Leaf) Leaf) (Node 0 (Node 0 Leaf Leaf) (Node 0 Leaf Leaf)))
     ==> Node 2 (Node 1 (Node 0 Leaf Leaf) Leaf) (Node 4 (Node 3 Leaf Leaf) (Node 5 Leaf Leaf))

Numeroitten kuljettaminen edes takas on ikävää

Tilan päivittäminen ketjuttamisella

Katsotaan yksinkertaistuisiko tämä ketjuttamisella
Päivitämme tilaa joka on tyyppiä Int
Olemme siis kiinnostuneet funktioista Int -> (a,Int)
- a on esimerkiksi Tree Int
Kääritään tällaiset funktiot tyyppiin Tila a

data Tila a = Tila (Int -> (a,Int))

ajaTila :: Tila a -> Int -> (a,Int)
ajaTila (Tila f) s = f s

-- Palauttaa tämänhetkisen tilan, kasvattaa tilaa yhdellä
haeJaKasvata :: Tila Int
haeJaKasvata = Tila (\i -> (i,i+1))

-- Palauttaa annetun arvon, ei muuta tilaa
eiMuutosta :: a -> Tila a
eiMuutosta x = Tila (\i -> (x,i))

-- Tilallisten laskutoimitusten ketjuttaminen
yhdista :: Tila a -> (a -> Tila b) -> Tila b
yhdista op f = Tila g
  where g i = let (arvo,uusi) = ajaTila op i
                  op2 = f arvo
              in ajaTila op2 uusi

numeroi :: Tree a -> Tree Int
numeroi tree = t
  where (t,_) = ajaTila (numeroi' tree) 0

numeroi' :: Tree a -> Tila (Tree Int)
numeroi' Leaf = eiMuutosta Leaf
numeroi' (Node _ l r) =
  numeroi' l
  `yhdista`
  (\l' -> haeJaKasvata
          `yhdista`
          (\i -> numeroi' r
                 `yhdista`
                 (\r' -> eiMuutosta (Node i l' r'))))

numeroi (Node 0 (Node 0 (Node 0 Leaf Leaf) Leaf) (Node 0 (Node 0 Leaf Leaf) (Node 0 Leaf Leaf)))
     ==> Node 2 (Node 1 (Node 0 Leaf Leaf) Leaf) (Node 4 (Node 3 Leaf Leaf) (Node 5 Leaf Leaf))

Ei mennyt kauhean nätiksi, mutta laskuriparametri on nyt piilossa!

Monad

Olemme nyt nähneet kolme eri tyyppiä joilla on ketjutusoperaatio.

(?>) :: Maybe a -> (a -> Maybe b) -> Maybe b
(#>) :: Logger a -> (a -> Logger b) -> Logger b
yhdista :: Tila a -> (a -> Tila b) -> Tila b

Kuten aikaisemminkin (map ja Functor), on tyyppiluokka joka auttaa yhdistämään nämä

class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b

Lisäksi Monad-tyyppiluokassa on seuraavat operaatiot

  -- nosta normaali arvo monadiin
  return :: a -> m a
  -- simppelimpi ketjutus (muista ##>)
  (>>) :: m a -> m b -> m b
  a >> b  =  a >>= \_x -> b
  -- laskennan epäonnistuminen
  fail :: String -> m a

Älä panikoi!

Functoreissa oli kyse geneerisestä map-operaatiosta

fmap :: Functor f :: (a->b) -> f a -> f b

Monadeissa on kyse vain geneerisestä ketjutusoperaatiosta

(>>=) :: Monad m => m a -> (a -> m b) -> m b

eli siitä miten monadisesta operaatiosta (m a) ja funktiosta joka palauttaa monadisen operaation (a -> m b) saadaan monadinen lopputulos (m b)

Jos tämä tuntuu liian abstraktilta, palauta mieleen miten Mayben ketjutus toimi:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing   -- kun on kerran epäonnistuttu, ei tehdä enää mitään
Just x  >>= f = f x       -- jos onnistuttiin, jatketaan

Maybe on monadi!

Tässä Mayben Monad-instanssi.

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (Just _) >>  k      = k
    Nothing  >>  _      = Nothing

    return              = Just
    fail _              = Nothing

Maybe-monadin toiminta on varsin suoraviivaista

Just 1 >>= \x -> return (x+1)
  ==> Just 2
Just "MOI" >>= \x -> return (length x) >>= \x -> return (x+1)
  ==> Just 4
Just "MOI" >>= \x -> Nothing
  ==> Nothing
Just "MOI" >> Just 2
  ==> Just 2
Just 2 >> Nothing
  ==> Nothing

Tässä increase-esimerkki monadioperaatioilla kirjoitettuna
Ainoat muutokset, ?> --> >>= ja Just --> return

increase key val assocs =
    lookup key assocs >>=
    check >>= 
    mk
  where check x
           | val < x   = fail ""
           | otherwise = return x
        mk x = return ((key,val) : delete (key,x) assocs)

`do`:n paluu

Muistanette viikolta 3 do-syntaksin:

f = do x <- op1
       op2
       y <- op3
       op4
       op5 x y

Itseasiassa do-syntaksi on vain kuorrutetta monadioperaatioille.
Tällaista siistiä koodia osaamme kirjoittaa monadioperaattoreilla:

f = op1 >>= jatko
  where jatko  x   = op2 >> op3 >>= jatko2 x
        jatko2 x y = op4 >> op5 x y

Kelataanpa määritelmät auki:

f = op1 >>= (\x ->
               op2 >>
               op3 >>= (\y ->
                          op4 >>
                          op5 x y))

Ja sisennetään uusiksi

f = op1 >>= \x ->
    op2 >>
    op3 >>= \y ->
    op4 >>
    op5 x y

Huomaatko yhtäläisyyden kalvon ensimmäiseen koodinpätkään?

Esimerkkejä do-syntaksilla

Tässä safeNth do-syntaksilla.

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (x:xs) = Just xs

safeNth 0 xs = safeHead xs
safeNth n xs = do t <- safeTail xs
                  safeNth (n-1) t

Tässä increase vielä kerran, tällä kertaa do-syntaksilla.

increase key val assocs = do
    val <- lookup key assocs
    check val
    return ((key,val) : delete (key,x) assocs)

Aika miellyttävää, eikö!

Logger on monadi!

Tässä Loggerin Monad-instanssi
Huomaa miten filterLog on aika suoraviivainen do-syntaksilla

data Logger a = Logger [String] a  deriving Show

instance Monad Logger where
  return x = Logger [] x
  Logger la a >>= f = Logger (la++lb) b
    where Logger lb b = f a

msg s = Logger [s] ()

laske x = do
  a <- annotate "^2" (x*x)
  b <- annotate "+1" (a+1)
  annotate "*2" (b*2)

filterLog :: (Eq a, Show a) => (a -> Bool) -> [a] -> Logger [a]
filterLog f [] = return []
filterLog f (x:xs)
   | f x       = do msg ("keeping "++show x) 
                    xs' <- filterLog f xs
                    return (x:xs')
   | otherwise = do msg ("dropping "++show x)
                    filterLog f xs

filterLog (>0) [1,-2,3,-4,0]
  ==> Logger ["keeping 1","dropping -2","keeping 3","dropping -4","dropping 0"] [1,3]

State-monadi

Haskellin State-monadi (aka tilamonadi) on yleistetty versio Tila-tyypistämme

data State s a = State (s -> (a,s))

runState (State f) s = f s

-- kirjoita tilaan
put state = State (\_state -> ((),state))
-- hae tila
get = State (\state -> (state,state))
-- muuta tilaa funktiolla
modify f = State (\state -> ((), f state))

instance Monad (State s) where
  return x = State (\s -> (x,s))

  op >>= f = State h
    where h state0 = let (val,state1) = runState op state0
                         op2 = f val
                     in runState op2 state1

Huom! State s on tyyppimuodostin, koska siltä puuttuu vielä yksi tyyppiparametri
State-monadi esittää laskentaa, jossa on yksi globaali muuttuja

State-esimerkkejä

Statella on helppo tehdä laskuri-tyyppistä koodia

lisaa :: Int -> State Int ()
lisaa i = do vanha <- get
             put (vanha+i)

runState (lisaa 1 >> lisaa 3 >> lisaa 5 >> lisaa 6) 0
  ==> ((),15)

oo = do lisaa 3
        arvo <- get
        lisaa 1000
        put (arvo + 1)
        return arvo

runState oo 1
(4,5)

Listatyyppiseen tila voi korvata akkumulaattoriparametrin

muista :: a -> State [a] ()
muista x = modify (x:)

alkiotNollanJalkeen xs = runState (go xs) []
  where go (0:y:xs) = do muista y
                         go (y:xs)
        go (x:xs) = go xs
        go [] = return ()

alkiotNollanJalkeen [0,1,2,3,0,4,0,5,0,0,6]
  ==> ((),[6,0,5,4,1])

Monimutkaisempi State-esimerkki

Katsotaan ovatko sulkeet tasapainossa merkkijonossa:

parensMatch xs = v
  where (v,_) = runState (matcher xs) 0

matcher :: String -> State Int Bool
matcher [] = do s <- get
                return (s==0)
matcher (c:cs) = do case c of '(' -> modify (+1)
                              ')' -> modify (-1)
                              _ -> return ()
                    s <- get
                    if (s<0) then return False else matcher cs

Tässä vielä puun numerointi, kauniisti

numeroi tree = t
  where (t,_) = runState (go tree) 0
        go Leaf = return Leaf
        go (Node _ l r) = do l' <- numeroi l
                             i <- get
                             put (i+1)
                             r' <- numeroi r
                             return (Node i l' r')

`mapM`:n paluu

IO-luennolta tutut operaatiot toimivat kaikki kaikissa monadeissa
Tässä oikeat tyypit niille:

-- ehdollinen operaatio
when :: Monad m => Bool -> m () -> m ()
-- ehdollinen operaatio, päinvastoin
unless :: Monad m => Bool -> m () -> m ()
-- tee jotain monta kertaa
replicateM :: Monad m => Int -> m a -> m [a]
-- tee jotain monta kerta, unohda tulos
replicateM_ :: Monad m => Int -> m a -> m ()
-- tee jokin operaatio jokaiselle listan alkiolle
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
-- samoin mutta tuloksesta ei välitetä
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
-- argumentit eri järjestyksessä, kätevämpi usein
forM  :: Monad m => [a] -> (a -> m b) -> m [b]
forM_ :: Monad m => [a] -> (a -> m b) -> m ()

safeHead [] = Nothing
safeHead (x:xs) = Just x
firsts xs = mapM safeHead xs

firsts [[1,2,3],[4,5],[6]]
  ==> Just [1,4,6]
firsts [[1,2,3],[],[6]]
  ==> Nothing

let op = modify (+1) >> get
    ops = replicateM 4 op
in runState ops 0
  ==> ([1,2,3,4],4)

Toteutetaan filter uudelleen tilamonadilla

sfilter :: (a -> Bool) -> [a] -> [a]
sfilter f xs = reverse . snd $ runState (go xs) []
  where go xs = mapM_ maybePut xs
        maybePut x = when (f x) (modify (x:))

Polymorfisia Monad-esimerkkejä

Voimme itsekin kirjoittaa koodia monadista riippumatta
Tämän mahdollistavat tyyppiluokat kuten viime viikolla käsittelimme

mywhen b op = if b then op else return ()

mymapM_ op [] = return ()
mymapM_ op (x:xs) = do op x
                       mymapM_ op xs

*Main> :t mywhen
mywhen :: (Monad m) => Bool -> m () -> m ()
*Main> :t mymapM_
mymapM_ :: (Monad m) => (t -> m a) -> [t] -> m ()

Monadit ovat Funktoreita

Eräs hyvin hyödyllinen operaatio on mainitsematta: liftM

liftM :: Monad m => (a->b) -> m a -> m b
liftM f op = do x <- op
                return (f x)

liftM yksinkertaistaa monesti koodia jossa on sekä monadisia että puhtaita osia:

liftM sort $ firsts [[4,6],[2,1,0],[3,3,3]]
  ==> Just [2,3,4]

Näyttääkö liftM:n tyyppi tutulta?

fmap :: Functor f => (a->b) -> f a -> f b

Monadille on helppo määritellä Functor-instanssi: fmap = liftM!
Kaikki standardikirjaston monadit ovat myös funktoreita

Vielä yksi monadi

Listamonadi (eli Monad-instanssi haskellin listatyypille []) esittää laskutoimituksia joilla on monia tuloksia
Se on hyödyllinen erilaisiin läpikäynteihin
Ensimmäinen esimerkki:

[1,2,3] >>= \x -> [-x,x]
  ==> [-1,1,-2,2,-3,3]

Esimerkki: löydä listasta kaksi lukuparit joitten summa on k

findSum :: [Int] -> Int -> [(Int,Int)]
findSum xs k = do a <- xs
                  b <- xs
                  if (a+b==k) then [(a,b)] else []

Tai toisin kirjoitettuna:

findSum :: [Int] -> Int -> [(Int,Int)]
findSum xs k = do a <- xs
                  b <- xs
                  if (a+b==k) then return (a,b) else fail ""

findSum [1,2,3,4,5] 5
  ==> [(1,4),(2,3),(3,2),(4,1)]

Vielä yksi esimerkki listamonadista

Löydetään pisin palindromi joka esiintyy merkkijonon osana

osajono :: String -> [String]
osajono xs = do i <- [0..length xs - 1]
                let maxlen = length xs - i
                j <- [1..maxlen]
                return $ take j $ drop i $ xs

palindromit :: String -> [String]
palindromit xs = do s <- osajono xs
                    if (s==reverse s) then return s else fail ""

pisinpalindromi xs = head . sortBy f $ palindromit xs
  where f s s' = compare (length s') (length s)  -- pidempi on pienempi

pisinpalindromi "aabbacddcaca"
  ==> "acddca"

Listamonadin toteutus

Tässä vielä listamonadin toteutus: se on yllättävän yksinkertainen

instance Monad [] where  -- listan tyyppimuodostin kirjoitetaan []
  return x = [x]         -- operaatio joka tuottaa vain yhden arvon
  lis >>= f = concat (map f lis)  -- lasketaan f kaikille syötteille, yhdistetään kaikki tulokset

Ainiin, IO

Kuten olette varmaan tähän mennessä päätelleet, IO on monadi

instance Monad IO where

IO:n toteutus on kuitenkin jokseenkin maaginen, mutta onneksi sitä ei tarvitse lukea!
Aito sivuvaikutuksellisuus (eli IO) istuu monadimuottiin aivan yhtä hyvin kuin yksinkertaisemmat Maybe ja State
Bonus: IO:n kanssa voidaan käyttää samoja korkeamman tason operaatioita (mapM ja kumppanit) kuin muittenkin.

Yhteenveto

Monad-tyyppiluokka on tapa esittää eri tavoilla eteneviä suorituksia
- epäonnistuminen
- tila
- moniarvoinen laskenta
- IO
Kun M on monadi, on tyypin M a hyvä ajatellä operaatioina jotka tuottavat tuloksen tyyppiä a
- muista IO-operaatiot!
Monadit ovat design pattern ja kirjasto (mapM jne)
- yhteisten abstraktioitten käyttö helpottaa koodin ymmärtämistä
- "haa, State [Int] Int, tiedän mikä tämä on" sen sijaan että koittaa tulkita monimutkaista rekursiivista funktiota
Kaiken mitä voi tehdä monadeilla voi tehdä myös ilman niitä (pl. IO ja pari muuta erikoistapausta)
- mutta monadin käyttäminen voi yksinkertaistaa koodia roimasti
Varoituksen sana: internet on täynnä materiaalia joka koittaa selittää monadit yksinkertaisen vertauskuvan avulla
- tämä ei toimi
- Monadien käytön harjoitteleminen toimii
Jos tunnet ymmärtäneesi Monadien käytön muttet tajua mitä järkeä niissä on, suosittelen tätä blogipostausta

Johdatus Funktionaaliseen Ohjelmointiin

Luento 1: ...And So It Begins

Sisältö

Yleistä

Perustiedot

Lue näitä

Kurssin rakenne

Haskell

Haskell TKTL:n koneilla

Aloitetaanpa!

Lausekkeet ja tyypit

Lausekkeitten syntaksi

Tyyppien syntaksi

Haskell-ohjelman rakenne

Haskell-ohjelman rakenne

Miten tällä saa mitään aikaan?

Ehtolausekkeet

Esimerkki

Alimääritelmät

Hahmonsovitus (Pattern Matching)

Esimerkkejä

Rekursio

Esimerkkejä

Lisää rekursiota

Esimerkkejä

Käytetäänpä näitä kaikkia yhdessä!

Sananen sisennyksestä

Esimerkkejä sisennyksestä

Harjoitusten tekeminen

Luento 2: Catamorphic

Sisältö

Ehdot (guards)

Ehdot: Esimerkkejä

Listat

Listaoperaatioita

Esimerkkejä

Sananen tyypinpäättelystä (type inference) ja polymorfismista

Esimerkkejä listafunktioilla

Funktionaalista ohjelmointia, vihdoin

Esimerkkejä

Partial application

Partial application 2

Operaattori .

Operaattori $

Lambdat

Funktionaalinen tyyli

Lisää esimerkkejä funktionaalisesta listojen pyörittelystä

Kaksoispiste

Listan rakentaminen

Listojen hahmonsovitus

Listan kuluttaminen

Listan rakentaminen ja kuluttaminen

Äärettömät listat

Luento 3: RealWorld -> (a,RealWorld)

Sisältö

Laiskuus & Puhtaus

Esimerkki

Teitä on huijattu

Hetkonen, mitä tässä oikein tapahtuu?

do as thou wilt

Esimerkkejä

return

do ja tyypit

Esimerkki 1

Esimerkki 2

Esimerkki 3

Kontrollirakenteita 1

Kontrollirakenteita 2

Hyödyllisiä operaatioita

Merkkijonojen käsittelyä

Tehdäänpä jotain oikeaa

Mitä tämä tarkoittaa?

Operaatiot ovat arvoja

Operaatiot ovat arvoja: lisäesimerkki

Vielä pari pikkujuttua: case

Vielä pari pikkujuttua: tuplet

Esimerkkejä

Luento 4: You Need String for a Knot

Sisältö

Algebralliset tietotyypit: intro

Operaattori `.`

Operaattori `$`

Luento 3: `RealWorld -> (a,RealWorld)`

`do` as thou wilt

`return`

`do` ja tyypit

Vielä pari pikkujuttua: `case`

`deriving Show`

`deriving`

`do`:n paluu

`mapM`:n paluu