Opintopiiri funktionaalisesta ohjelmoinnista

[snifi]

Tämän viestiketjun puitteissa olisi tarkoitus seurailla Phil Wadlerin luentosarjaa Edinburghin yliopistossa. Luentojen kotisivu on osoitteessa http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/ ja videoidut luennot http://groups.inf.ed.ac.uk/vision/VIDEO/2011/inf1fp.htm

Ohjelmointikielenä on Haskell.

Yritän ajan kuluessa pitää luetteloa luentovideoista tässä, sekä ohjeita videoiden tallentamiseen:

Koodia: [Valitse]

# Luento 01:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-09-20/Informatics_1___Functional_Programming-video.m4v" -O Lecture_01.m4v;
# Luento 02:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-09-26/Informatics_1___Functional_Programming-video.m4v" -O Lecture_02.m4v;
# Luento 03:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-09-27/Informatics_1___Functional_Programming-video.m4v" -O Lecture_03.m4v;
# Luento 04:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-03/Informatics_1___Functional_Programming-video.m4v" -O Lecture_04.m4v;
# Luento 05:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-04/Informatics_1___Functional_Programming-video.m4v" -O Lecture_05.m4v;
# Luento 06:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-10/Informatics_1___Functional_Programming-video.m4v" -O Lecture_06.m4v;
# Luento 07:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-11/Informatics_1___Functional_Programming-video.m4v" -O Lecture_07.m4v;
# Luento 08:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-17/Informatics_1___Functional_Programming-video-1.m4v" -O Lecture_08.m4v;
# Luento 09:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-18/Informatics_1___Functional_Programming-video-1.m4v" -O Lecture_09.m4v;
# Luento 12:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-31/Informatics_1___Functional_Programming-video.m4v" -O Lecture_12.m4v;
# Luento 13:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-01/Informatics_1___Functional_Programming-video.m4v" -O Lecture_13.m4v;
# Luento 14:
wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-07/Informatics_1___Functional_Programming-video.m4v" -O Lecture_14.m4v
# Luento 15:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-09/Informatics_1___Functional_Programming-video.m4v" -O Lecture_15.m4v
# Luento 16:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-14/Informatics_1___Functional_Programming-video.m4v" -O Lecture_16.m4v
# Luento 17:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-15/Informatics_1___Functional_Programming-video.m4v" -O Lecture_17.m4v
# Luento 18:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-21/Informatics_1___Functional_Programming-video.m4v" -O Lecture_18.m4v
# Luento 19:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-22/Informatics_1___Functional_Programming-video.m4v" -O Lecture_19.m4v
#
#

Kaksi ensimmäistä luentoa sisältävät käytännön järjestelyitä ja esittelyä, ja ne voi hypätä ylitse. (Luento 01 on unix-komentoihin tutustumista, käytännössä unixin komennot ls, pwd, file, cp, rm, mv, mkdir, rmdir. Luento 02 on pääasiassa Edinburghin omille opiskelijoille tarkoitettu informaatio harjoitustehtävistä ja tenttijärjestelyistä, lopussa lyhyt Haskell-kielen historiikki)

Aloitataan siis luennosta 03. Koska luentoja on kahdesti viikossa, niin ajattelin, että opiskelisimme aluksi tahtia noin yksi luento kolmessa päivässä.

Kysymyksiä, vinkkejä ja omia kokemuksia voi kirjata ylös ja muiden luettaviksi tähän.

[snifi]

Ubuntulle Haskell-kääntäjä (Glasgow Haskell Compiler) löytyy pakettivarastosta (ghc, ghc6, ghc7, Haskell Platform tai vastaava). Interaktiivinen tulkki käynnistyy pääteikkunasta komennolla: ghci

Määritellään muutama funktio:

Koodia: [Valitse]

$ ghci
GHCi, version 6.12.1: http://www.haskell.org/ghc/  :? for help
Prelude> let succ x = x + 1
Prelude> let pred x = x - 1
Prelude> let double x = 2*x
Prelude> let triple x = 3*x
Prelude> let square x = x*x
Prelude> let add x y = x + y
Prelude> let subtract x y = x - y
Kokeillaan niitä:

Koodia: [Valitse]

Prelude> add 3 4
7
Prelude> 4 `add` 5
9
Prelude> succ 1
2
Prelude> succ (succ 1)
3
Prelude> succ (succ (succ 1))
4
Prelude> double 2
4
Prelude> triple 2
6
Prelude> add (double 2) (triple 2)
10
Prelude> square (triple (double 2))
144
Prelude> (triple 2) `add` (double 2)
10

Muutama tärkeä tyyppimäärittely:

Koodia: [Valitse]

True :: Bool
5 :: Int
5.5 :: Float
'c' :: Char
"Hello" :: String
-- funktioiden tyyppejä:
min :: (Ord a) => a -> a -> a
succ :: (Num a) => a -> a
Merkintä "::" luetaan "on tyyppiä". Ja vielä pakollinen "hypetys":

Koodia: [Valitse]

Prelude> let don'tForget = "Haskell is Cool!"
Prelude> don'tForget
"Haskell is Cool!"
Prelude>

[snifi]

Luennon 04 aiheena on listat ja rekursio.

Koodia: [Valitse]

# Luento 04:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-03/Informatics_1___Functional_Programming-video.m4v" -O Lecture_04.m4v;
#
Luentomuistiinpanot löytyvät täältä:
http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect03.pdf

Aikaisemman luennon muistiinpanot ovat täällä:
http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect01.pdf

[Tommi S.]

Olipa hauska yhteensattuma löytää tällainen ketju täältä, sillä aloin itse juuri pari päivää sitten lukemaan Real World Haskell kirjaa, jota voi lukea osoitteesta: http://book.realworldhaskell.org/read/

Olen joskus aiemmin lukenut hieman Learn You a Haskell for Great Good! kirjaa, joka on eräänlainen kuvitettu ja sarjakuvamainen Haskell oppikirja. (voi lukea osoitteessa: http://learnyouahaskell.com/ )

Nyt kun olen noita molempia kirjoja jonkin verran lukenut, niin mielipiteeni on että tuo Real World Haskell on jotenkin selkeämpi ja helpommin ymmärrettävä, vaikka se onkin paljon asiallisempi eikä yritä olla yhtä viihdyttävä kuin tuo Learn You a Haskell for Great Good!.

Näköjään tuolla Learn You a Haskell kirjan FAQ:ssa on linkki tällaiselle sivulle jossa voi kokeilla Haskellia interaktiivisessa päätteessä suoraan selaimesta: http://tryhaskell.org/

Rekursion ja rekursiivisten tietotyyppien hahmottamisessa itseäni ainakin on auttanut huomattavasti How To Design Programs kirja. (voi lukea osoitteessa: http://htdp.org/ )
Kirjan käyttämä ohjelmointikieli ei tosin ole Haskell, vaan Lisp perheeseen kuuluva Scheme, mutta itse asia eli rekursio ja rekursiiviset tietotyypit toimivat samalla periaatteella kaikilla kielillä, ja tuossa kirjassa ne selitetään mielestäni erittäin selkeästi ja aloittelijaystävällisesti.
Lisäksi kirjaan kuuluu DrScheme niminen ohjelmointiympäristö jossa on oma moodinsa juuri tuolle kirjalle, jonka avulla mm. ohjelmointiympäristön uusia ominaisuuksia kytketään päälle sitä mukaa kun kirja etenee. Rajoittamalla ohjelmointiympäristön ominaisuuksia voidaan esim. antaa alkuvaiheessa aloittelijalle hyvin selkeitä virheilmoituksia.

[snifi]

Nyt on käsitelty funktiot ja listat:

Koodia: [Valitse]

$ ghci
Prelude> let ts = [2,3,5,7,11,13]
Prelude> ts !! 4
11
Prelude> ts ++ [17,19]
[2,3,5,7,11,13,17,19]
Prelude> map negate ts
[-2,-3,-5,-7,-11,-13]
Prelude> map (+2) ts
[4,5,7,9,13,15]
Prelude> map (*2) ts
[4,6,10,14,22,26]
Prelude> take 4 ts
[2,3,5,7]
Prelude> take 8 (cycle [1,2])
[1,2,1,2,1,2,1,2]
Prelude> ts
[2,3,5,7,11,13]
Prelude> 9 `elem` ts
False
Prelude> 2 `elem` ts
True
Prelude> filter (<10) ts
[2,3,5,7]
Prelude> filter even ts
[2]
Prelude> let p = (2,5)
Prelude> fst p
2
Prelude> snd p
5
Prelude> ts
[2,3,5,7,11,13]
Prelude> head ts
2
Prelude> tail ts
[3,5,7,11,13]
Prelude> last ts
13
Prelude> let len = length
Prelude> len ts
6
Prelude> maximum ts
13
Prelude> minimum ts
2
Prelude> 2 `notElem` ts
False
Prelude> null []
True
Prelude> filter odd ts
[3,5,7,11,13]
Prelude> product ts
30030
Prelude> sum ts
41
Prelude> take 6 (repeat 2)
[2,2,2,2,2,2]
Prelude> replicate 5 3
[3,3,3,3,3]
Prelude> reverse ts
[13,11,7,5,3,2]
Prelude> splitAt 3 ts
([2,3,5],[7,11,13])
Prelude> take 4 ts
[2,3,5,7]
Prelude> let ns = [1..]
Prelude> take 10 ns
[1,2,3,4,5,6,7,8,9,10]
Prelude> takeWhile (<5) ns
[1,2,3,4]
Prelude> dropWhile (<5) ts
[5,7,11,13]
Prelude> take 6 (zip ns ts)
[(1,2),(2,3),(3,5),(4,7),(5,11),(6,13)]
Prelude>
Haskellin standardifunktiot ovat kirjastossa Prelude.hs.  Tämä kirjasto ladataan oletuksena ghci:ssä. Luettelon standardikirjaston funktioista saat esimerkiksi ghci:llä komennolla ":browse Prelude":

Koodia: [Valitse]

$ ghci
Prelude> :browse Prelude
($!) :: (a -> b) -> a -> b
(!!) :: [a] -> Int -> a
($) :: (a -> b) -> a -> b
(&&) :: Bool -> Bool -> Bool
(++) :: [a] -> [a] -> [a]
(.) :: (b -> c) -> (a -> b) -> a -> c
... pitkän luettelon alku ja loppu ...
words :: String -> [String]
writeFile :: FilePath -> String -> IO ()
zip :: [a] -> [b] -> [(a, b)]
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
(||) :: Bool -> Bool -> Bool
Prelude>

Luennoissa käytettiin funktiota toLower. Se ei kuulu standardikirjastoon. Miten löydämme sen? Yksi ratkaisu on asentaa ghci:hin hoogle-lisäosa.

Koodia: [Valitse]

Prelude> :hoogle toLower
Data.Char toLower :: Char -> Char
Data.Text toLower :: Text -> Text
Data.Text.Lazy toLower :: Text -> Text
Prelude> import Data.Char
Prelude Data.Char> [toLower x | x <- "XsTsNsXssTss"]
"xstsnsxsstss"

[snifi]

Tänään olisi vuorossa Labweek sekä Tutoriaali 01. Tehtäviin kuluu varmaan muutama päivä, ja neuvoa voi kysellä täällä sitä mukaa kun tarvitsee. Yritetään tehdä jonkunlainen yhteenveto kun saadaan valmiiksi.

Tarvittavat tiedostot latautuvat näillä komennoilla:

Koodia: [Valitse]

# Tutoriaali 01:
mkdir Tutorial_01; cd Tutorial_01;
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/tutorials/labweek.zip
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/tutorials/labweek-solns.zip
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/tutorials/tutorial1.zip
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/tutorials/solutions/tutorial1-solns.hs
unzip labweek.zip; unzip labweek-solns.zip; unzip tutorial1.zip;
#
Lisäksi voisi kokeilla, miten yksinkertaiset funktiot tallennetaan tiedostoon ja ladataan ghci:hin:

Koodia: [Valitse]

succ x = x + 1
pred x = x - 1
double x = 2*x
triple x = 3*x
square x = x*x
add x y = x + y
subtract x y = x - y

Luento 05 huomenna:

Koodia: [Valitse]

# Luento 05:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-04/Informatics_1___Functional_Programming-video.m4v" -O Lecture_05.m4v;
#

[Tommi S.]

Kun yritin ladata tuota harjoitustiedostoa labweekexercise.hs ghci:ssa niin tuli virheilmoitus että moduulia Test.Quickcheck ei löydy. (Could not find module `Test.QuickCheck')

Haskellille on olemassa moduulien latain nimeltä cabal joka on hieman samanlainen kuin Rubyn Rubygems, tai Debianin apt-get, eli komentorivillä annetaan käsky mikä moduuli halutaan, ja cabal lataa, kääntää ja asentaa kyseisen moduulin.

Sain harjoitustiedoston ladattua Haskell tulkkiin näiden komentojen jälkeen:

Koodia: [Valitse]

sudo apt-get install cabal-install
cabal update
cabal install Quickcheck
cabal update käskyllä haetaan uusimmat pakettilistaukset palvelimelta, ja cabal install komennolla asennetaan haluttu moduuli.

[snifi]

Tässä on vielä jonkinlainen kertaus ensimmäisen viikon luennoista. Tutoriaali 01 on hyvin työläs, ja sitä voi ratkoa omalla ajallaan. Vastaukset löytyvät omalta tiedostoltaan ja ne ovat varsin kattavat ja soveltuvat  omatoimiopiskeluun.

Koodia: [Valitse]

Listamuodostimia:
[x*x | x <- [1,2,3]]
[toLower c | c <- "BsTssCsXss"]
[(x,even x) | x <- [1,2,3]]

Lyhennysmerkintöjä:
[1..] => [1,2,3,...]
[5..] => [5,6,7,...]
[1..4] => [1,2,3,4]
[1,3..11] => [1,3,5,7,9,11]
[2,4..10] => [2,4,6,8,10]
[0,4..] => [0,4,8,12,...]

[x | x <- [1,2,3], odd x]
[x*x | x <- [1,2,3], odd x]
[x | x <- [42,-5,24,0,-3], x>0]
[toLower c | c <- "Bs, Tss Cs", isAlpha c]

sum [1,2,3]
sum []
sum [x*x | x <- [1,2,3], odd x]
product [1,2,3,4]
product []

Funktion määrittely listamuodostimella:

squares xs = [x*x | x <- xs]
odds xs = [x | x <- xs, odd x]
sumSqOdd xs = sum [x*x | x <- xs, odd x]

1:[2,3]
[1]++[2,3]
[1,2]++[3]
'l':"ist"
"l"++"ist"
"li"++"st"

"Lista muodostuu päästä ja hännästä." Tämä kuva listasta on Phil Wadlerin blogista http://wadler.blogspot.com/2010/11/list-is-odd-creature-take-5.html

Koodia: [Valitse]

"Lista muodostuu päästä ja hännästä. Häntä on lista."
[1,2,3] = 1:(2:(3:[]))
"list" = ['l','i','s','t'] = 'l':('i':('s':('t':[])))

Rekursion eteneminen listassa ts:
ts = [1,2,3,4]
ts                           => [1,2,3,4]
head ts                      => 1
tail ts                      => [2,3,4]
head (tail ts)               => 2
tail (tail ts)               => [3,4]
head (tail (tail ts))        => 3
tail (tail (tail ts))        => [4]
head (tail (tail (tail ts))) => 4
tail (tail (tail (tail ts))) => []

Funktion määrittely rekursion avulla (käytetään argumenttien sovitusta):

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

Ei voida kirjoittaa sum x:xs, sillä (sum x) sitoo voimakkaammin kuin (x:xs):
sum x:xs == (sum x):xs /= sum (x:xs)

squaresRec [] = []
squaresRec (x:xs) = x*x : squaresRec

oddsRec [] = []
oddsRec (x:xs)
  | odd x = x : oddsRec xs
  | otherwise = oddsRec xs

len [] = 0
len (x:xs) = 1 + len xs

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


Standardikirjaston eli Preluden funktioita:
head, tail, filter, maximum, minimum, take, takeWhile, drop, dropWhile, elem,
notElem, sum, product, splitAt, repeat, replicate, cycle, reverse, and, or,
even, odd, null, fst, snd, min, max, (==), (/=), (>), (<), (<=, (>=), id,
succ, pred, last, length, map, not, (++), (&&), (||), (+), (-), (*), (**),
div, mod, negate, abs, sqrt, pi, sin, cos, tan

Tähän mennessä esiintyneitä tietotyyppejä:
Integer, Float, Char, String, Picture, Bool

knight :: Picture
invert :: Picture -> Picture
beside :: Picture -> Picture -> Picture
(+) :: Integer -> Integer -> Integer
(*) :: Integer -> Integer -> Integer
(:) :: a -> [a] -> [a]
(++) :: [a] -> [a] -> [a]

square x = x*x
pyth a b = square a + square b
factorial n = product [1..n]

[snifi]

Luento 06 jatkaa siitä mihin edellisellä viikolla päästiin

Koodia: [Valitse]

# Luento 06:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-10/Informatics_1___Functional_Programming-video.m4v" -O Lecture_06.m4v;
# Luentomuistiinpanot:
 wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect05.pdf
#

Edellisessä viestissäni listan määritelmässä oli pieni virhe:

 "Lista muodostuu päästä ja hännästä. Häntä on lista."

Tällainen lista olisi päättymätön. Tarvitaan siis tyhjän listan käsite:

 "Lista on joko tyhjä lista tai se muodostuu päästä ja hännästä. Häntä on lista."

Josko määritelmä olisi nyt oikein

[Tommi S.]

Tuossa aiemmin mainitsemassani htdp kirjassa neuvotaan kätevä sääntö rekursiivisten tietotyyppien käsittelyyn. Sääntö on sellainen että jokaista rekursiivisesti määriteltyä tietotyyppiä voi käsitellä funktiolla jonka määritelmä on samaa muotoa kuin tietotyypin määritelmä.

Esim. kun lista määritellään rekursiivisesti näin:

Koodia: [Valitse]

lista = []        (tyhjä lista)
lista = pää:häntä (jossa häntä on lista)
niin listan käsittelyyn käy funktio jonka määritelmä näyttää melkein samalta kuin listan määritelmä:

Koodia: [Valitse]

käsitteleLista []        = jotain
käsitteleLista pää:häntä = käsittele pää
                           ja käsitteleLista häntä
eli kun listan määritelmä hännän kohdalla palaa rekursiivisesti takaisin itseensä, niin samoin funktio joka käsittelee listaa palaa hännän kohdalla rekursiivisesti takaisin itseensä, eli jos tietää miltä tietotyypin määritelmä näyttää niin siitä voi ottaa suoraan mallia kun laatii funktiota joka käsittelee kys. tietotyyppiä. Tämä sama pätee myös muihin rekursiivisiin tietotyyppeihin kuin vain listoihin.

Tässä muutama harjoitelmafunktio jotka käsittelevät listoja. 

Koodia: [Valitse]

import Char

-- laskee yhteen listan numeroita
laskeYhteen :: [Int] -> Int
laskeYhteen [] = 0
laskeYhteen (pää:häntä) = pää + laskeYhteen häntä

-- etsii suurimman numeron listalta
-- suurin [] tapausta ei ole määritelty koska suurin alkio tyhjästä ei ole mielekäs toimenpide
suurin :: [Int] -> Int
suurin (pää:[])    = pää
suurin (pää:häntä) = if pää > suurin häntä
                     then pää
                     else suurin häntä
                     
-- laskee montako kertaa x esiintyy listalla
laskeEsiintymät :: (Eq a) => a -> [a] -> Int
laskeEsiintymät x []          = 0
laskeEsiintymät x (pää:häntä) = if pää == x
                                then 1 + laskeEsiintymät x häntä
                                else     laskeEsiintymät x häntä

-- muuntaa merkkijonon isoiksi kirjaimiksi
isoiksiKirjaimiksi :: String -> String
isoiksiKirjaimiksi []          = []
isoiksiKirjaimiksi (pää:häntä) = (toUpper pää):(isoiksiKirjaimiksi häntä)

[Tommi S.]

Tässä helmi luennosta 6:

Laskuoperaation suoritusjärjestys vaikuttaa siihen miten kyseisen laskuoperaation voi suorittaa rinnakkain esim. useammalla prosessorilla.

Esimerkiksi peräkkäiset jakolaskut täytyy suorittaa tietyssä järjestyksessä jotta saataisiin oikea tulos, mutta kertolaskut voi suorittaa missä järjestyksessä tahansa. Esimerkki:

Koodia: [Valitse]

let a = 500.0; b = 2.0; c = 7.0; d = 8.0; e = 4.0; f = 3.5

a / b / c / d / e / f 
-- tulos: 0.31887755102040816

-- Jos yritetään laskea eri järjestyksessä, tulos ei ole enää sama.
-- Yritetän laskea alkuosa ja loppuosa erikseen, ja sitten jakaa lopuksi ensimmäinen tulos jälkimmäisellä:
(a / b / c) / (d / e / f)
-- tulos: 62.50000000000001

-- Jakolasku voidaan muuntaa kertolaskuksi muuntamalla jakajat käänteisluvuiksi.
let _b = 1/b; _c = 1/c; _d = 1/d; _e = 1/e; _f = 1/f

a * _b * _c * _d * _e * _f
-- tulos: 0.31887755102040816

-- Kertolaskun voi laskea missä järjestyksessä tahansa, ja saadaan silti aina sama tulos.
(a * _b * _c) * (_d * _e * _f)
-- tulos: 0.31887755102040816

a/b/c/d/e/f == (a*_b*_c) * (_d*_e*_f)
a/b/c/d/e/f == (a*_b) * (_c*_d) * (_e*_f)

a/b/c/d/e/f /= (a/b/c) / (d/e/f)
a/b/c/d/e/f /= (a/b) / (c/d) / (e/f)
Jakolaskun a/b/c/d tapauksessa, ennen kuin voidaan jakaa d:llä täytyy odottaa että laskun a/b/c tulos on valmistunut, mutta käänteislukujen kertolaskussa a*_b*_c*_d ei tarvitse odottaa muiden tulosten valmistumista, joten a*_b voidaan lähettää laskettavaksi prosessorille 1, ja _c*_d voidaan lähettää prosessorille 2, ja lopuksi prosessorien palauttamat tulokset voidaan kertoa keskenään.

[Tommi S.]

Poimintoja luennosta 7:

Haskell on laiska kieli, mikä tarkoittaa että laskutoimituksia ei suoriteta ennen kuin niiden tuloksia tarvitaan. Tämä mahdollistaa esim. äärettömien listojen käsittelyn, koska ääretöntä listaa ei luoda muistiin kerralla, vaan listan seuraava alkio lasketaan vasta kun rekursiivinen funktio tai muu sitä pyytää.

Tässä esimerkki hitaalla fibonaccin lukuja laskevalla funktiolla:

Koodia: [Valitse]

-- tallennetaan tämä tiedostoon fib.hs
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)


-- käynnistetään ghci ja ladataan yllä oleva fib funktio
:load fib.hs

-- lasketaan 30. fibonaccin luku
fib 30
-- laskeminen kestää kauan... 832040

-- tallennetaan 30. fibonaccin luku muuttujaan
let a = fib 30
-- toimenpide on heti valmis, sillä 30. fibonaccin lukua ei vielä oikeasti laskettu
-- Haskell laskee sen vasta kun a:n arvoa kysytään:
a
-- laskeminen kestää kauan... 832040

-- a:n arvoa ei kuitenkaan lasketa joka kerralla uudestaan, vaan kun se on kerran laskettu niin palautetaan valmiiksi laskettu arvo
a
-- toimenpide on heti valmis - 832040

[snifi]

Alkavalla viikolla jos ahkeroimme luennot 08 ja 09, niin olemme samassa tahdissa Edinburghin kanssa. Ensi viikolla pitäisi olla välitentti, joten luennoissa tulee yhden luennon helpotus.

Näiden luentomoniste on tässä: http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect07.pdf

Koodia: [Valitse]

# Luento 08:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-17/Informatics_1___Functional_Programming-video-1.m4v" -O Lecture_08.m4v;
# Luento 09:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-18/Informatics_1___Functional_Programming-video-1.m4v" -O Lecture_09.m4v;
#
Välipalaksi voi katsella Google TechTalkista uuden videon "Haskell Amuse-Bouche":

http://www.youtube.com/watch?v=b9FagOVqxmI

[snifi]

Mitä tyyppiä on tyhjä lista? Se ei voi olla mitään tyyppiä ja sen täytyy olla kaikkia tyyppejä.

Aikaisemmasta muistamme:

Koodia: [Valitse]

Prelude> 1:2:3:[]
[1,2,3]
Prelude>
Listan alkioiden tulee olla samaa tyyppiä, joten tyhjä lista on siis tyyppiä [Integer]. Toisaalta

Koodia: [Valitse]

Prelude> True:False:True:[]
[True,False,True]
Prelude>
Nyt tyhjän listan tyyppi on [Boolean].

Tyhjä lista on myös tyyppiä [String]:

Koodia: [Valitse]

Prelude> "a":"i":"u":[]
["a","i","u"]
Prelude>
Samoin se on tyyppiä [Char].

Koodia: [Valitse]

Prelude> 'a':'i':'u':[]
"aiu"
Prelude>

data String = [Char]

Kysytään tyhjän listan tyyppi ghci:ltä:

Koodia: [Valitse]

Prelude> :t []
[] :: [a]
Prelude>

Tyhjä lista on siis mitä tahansa tyyppiä. Merkintä [a] tarkoittaa tätä. Huomaa, että tyyppi a kirjoitetaan tässä pienellä alkukirjaimella.

Silti myös alussa kuvatut tapaukset pitävät paikkansa. Tyhjä lista saa siis tyyppimääreen asiayhteydestä eli kontekstista riippuen. "Asiayhteyksiä" käsitellään todennäköisesti lisää loman jälkeen.

[snifi]

Luennot jatkuvat, aiheena algebralliset tietotyypit.

Tämän viikon luentomoniste, luentoihin liittyvä Haskell-ohjelma ja videot ovat tässä:

Koodia: [Valitse]

# Luentomoniste:
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect11.pdf
# Haskell-ohjelma:
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect11.hs
# Luento 12:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-10-31/Informatics_1___Functional_Programming-video.m4v" -O Lecture_12.m4v;
# Luento 13:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-01/Informatics_1___Functional_Programming-video.m4v" -O Lecture_13.m4v;
#
On varmaan hyvä miettiä ennen luentojen katselemista, mitä merkitsevät seuraavat tyyppimäärittelyt:

Koodia: [Valitse]

data Bool = True | False
data Season = Winter | Spring | Summer | Fall
data Colors = Red | Green | Blue | Indigo | Violet
data Shape =  Circle Float | Rect Float Float
data Expr = Lit Int | Add Expr Expr | Mul Expr Expr
data List a = Nil | Cons a (List a)
data Tree a = Empty | Leaf a | Branch (Tree a) (Tree a)
Vasemmalla puolella avainsanan data jälkeen tulee tietotyypin nimi. Oikealla puolella ovat tietotyypin mahdolliset arvot erotettuina tai-merkillä "|". Arvot koostuvat konstruktorista ja konstruktorin mahdollisista parametreista.

True ja False ovat konstruktoreita ilman parametria. Niillä ei myöskään ole toteutusta, eivätkä ne tarvitse toteutusta, ne ovat käyttökelpoisia ja riittäviä pelkkinä niminä.

Geometriset kuviot (Shape) ovat tässä joko ympyröitä tai suorakulmioita. Ympyrä on muotoa Circle Float. Suorakulmio on muotoa Rect Float Float. Tässä Circle ja Rect ovat konstruktoreita ja molemmilla niillä on eri määrä parametreja. Ympyrän kohdalla parametri kuvaa ympyrän sädettä, suorakulmion kohdalla suorakulmion leveyttä ja korkeutta.

Listat (List), ilmaisut (Expr) ja puut (Tree) ovat esimerkkejä rekursiivisesta tietotyypistä. Rekursiivisessa tietotyypissä konstruktorin parametrit voivat osoittaa tietotyyppiin itseensä.

Kolmiulotteisessa avaruudessa voisi olla määriteltynä piste Point:

Koodia: [Valitse]

data Point = Point Float Float Float
Tämä ei ole rekursiivinen tietotyyppi. Tässä oikean puolen konstruktorilla Point on kolme parametria, jotka ovat tyyppiä Float. Itse konstruktori on nimetty samoin kuin tietotyyppi, mutta tällä ei ole merkitystä. Konstruktorit eivät varsinaisesti osoita mihinkään, ainoastaan parametrit osoittavat. (Ja tässä parametrit ovat tyyppiä Float, eivät siis tyyppiä Point.)

Ilmaisu eli tyyppi Expr käsitellään läpikotaisin myöhemmin parsereiden yhteydessä. Tässä ilmaisu voi olla literaali kuten Lit 2, yhteenlaskuoperaatio kuten Add (Lit 2) (Lit 3) tai kertolaskuoperaatio Mul (Lit 2) (Lit3).

[Tommi S.]

Haskell ohjelmissa funktioiden yhteydessä näkee funktioiden tyyppimäärittelyjä, jotka näyttävät tältä:

Koodia: [Valitse]

funktio :: a -> b -> c
Nämä tyyppimäärittelyt eivät ole varsinaista funktion koodia, vaan niillä vain määritellään minkä tyyppisiä parametreja funktio käsittelee ja minkä tyyppisiä arvoja funktio palauttaa. Haskellissa tyyppimäärittelyt eivät ole useimmiten (koskaan?) pakollisia, vaan koodi toimii ilmankin, kun taas Javassa tai C:ssä kääntäjä ei pysty kääntämään ohjelmaa ellei se tiedä minkä tyyppisiä parametreja funktiot käsittelevät.

Tässä muutama funktio ilman tyyppimäärittelyjä:

Koodia: [Valitse]

import Char

tuplaa a = 2 * a

sulkuihin t = "(" ++ t ++ ")"

tuplaaLista []    = []
tuplaaLista (a:b) = (2 * a):(tuplaaLista b)

isoiksiKirjaimiksi []          = []
isoiksiKirjaimiksi (pää:häntä) = (toUpper pää):(isoiksiKirjaimiksi häntä)
Tässä samat tyyppimäärittelyjen kanssa:

Koodia: [Valitse]

import Char

tuplaa :: Int -> Int
tuplaa a = 2 * a

sulkuihin :: String -> String
sulkuihin t = "(" ++ t ++ ")"

tuplaaLista :: [Int] -> [Int]
tuplaaLista []    = []
tuplaaLista (a:b) = (2 * a):(tuplaaLista b)

isoiksiKirjaimiksi :: String -> String
isoiksiKirjaimiksi []          = []
isoiksiKirjaimiksi (pää:häntä) = (toUpper pää):(isoiksiKirjaimiksi häntä)
Molempia versioita voi testata ja ne toimivat aivan samalla tavalla.

Vaikka tyyppejä ei tarvitse erikseen funktioille määritellä, niin Haskellin tyypit ovat kuitenkin erittäin "vahvoja" ja "tiukkoja", mikä tarkoittaa sitä että kääntäjä pystyy kääntämisen aikana päättelemään käytetäänkö jossain funktiossa väärän tyyppisiä parametreja. Tästä johtuen Haskell ohjelmissa ei voi koskaan esiintyä mm. Javasta tuttuja "null pointer exception" tyyppisiä virheitä, sillä Haskell kääntäjä antaa varoituksen jos edes tuollaisen virheen mahdollisuus on olemassa.

Vaikka funktion tyyppejä ei ole pakko määritellä, niin tyyppimäärittelyjen kirjoittaminen kuitenkin helpottaa ymmärtämään mitä minkäkin funktion on tarkoitus tehdä, joten on suositeltua että esim. uuden funktion laatiminen aloitetaan siitä että kirjoitetaan funktion tyyppimäärittely, koska tämän jälkeen on paljon selkeämpää hahmottaa mitä funktion on tarkoitus tehdä.

[Tommi S.]

Tyyppejä määritellessä käytetään kahta avainsanaa, type ja data.
Type toimii kuten esim. C-kielen typedef, eli sillä voi antaa synonyymin jollekin tyypille, jotta koodi olisi helppolukuisempaa.
Data avainsanalla taas määritellään varsinaiset tietotyypit.
Tietotyypin määrittelyssä annetaan tietotyypin =-merkin vasemmalla puolella tietotyypin nimi, ja oikealla puolella tietotyypin konstruktorimääritelmiä. Tietotyypin nimeä käytetään tyyppimäärittelyissä, eli esim. kun ilmoitetaan minkä tyyppisiä parametreja funktio hyväksyy, ja konstruktoreita puolestaan käytetään ns. "oikean koodin" puolella.

Esimerkki:

Koodia: [Valitse]

type Nimi   = String
type Ikä    = Int
type Pituus = Double

data HenkilöTyyppi = Henkilö Nimi Ikä Pituus

henkilönNimi :: HenkilöTyyppi -> Nimi
henkilönNimi (Henkilö nimi ikä pituus) = nimi

henkilönNimi :: HenkilöTyyppi -> Ikä
henkilönNimi (Henkilö nimi ikä pituus) = ikä

henkilönNimi :: HenkilöTyyppi -> Pituus
henkilönNimi (Henkilö nimi ikä pituus) = pituus
Ylläolevassa koodissa HenkilöTyyppi on tyyppinimi, ja sitä käytetään tyyppimäärittelyissä. Henkilö on puolestaan konstruktori jolla voidaan luoda Henkilö-tyyppiä oleva "olio" tai arvo. Kuulemma usein Haskell koodissa tyyppinimi ja konstruktori ovat samannimisiä, eli ylläoleva HenkilöTyyppi määritelmä voisi olla tämänlainen:

Koodia: [Valitse]

data Henkilö = Henkilö Nimi Ikä PituusTässä kannattaa pitää mielessä että vaikka tässä Henkilö-tyyppi ja Henkilö-konstruktori ovatkin samannimisiä niin ne ovat aivan eri asioita.

Interaktiivisessa tulkissa voidaan luoda henkilö näin:

Koodia: [Valitse]

let h = Henkilö "Matti" 38 183.4Kyseinen Henkilö poikkeaa esim. Pythonin olioista siten että ei ole mitään kätevää keinoa tutkia henkilön "attribuutteja", vaan täytyy luoda funktio joka ottaa parametrina Henkilön ja palauttaa jonkun henkilön attribuutin. Koko ajattelutapa on funktionaalisessa ohjelmoinnissa täysin erilainen kuin proseduraalisessa olio-ohjelmoinnissa.

Funktion argumenttien sovituksessa käytetään nimenomaan konstruktoreita, mutta ikäänkuin käänteisesti, eli jos argumentti voitaisiin luoda kyseisellä konstruktorilla niin silloin sovitus tapahtuu, ja argumentin arvot sijoitetaan sovituksessa annettuihin muuttujiin.

Haskellissa on valmiina tyyppi nimeltä Maybe, jolla on kaksi konstruktoria, Just sekä Nothing.
Haskellissa lista voi sisältää vain yhden tyyppisiä alkioita, mutta jos esim. listalla säilytetään vaikka lämpötiloja eri vuorokauden aikoina, niin miten esitetään lämpötila sellaisena aikana jolloin lämpömittari on ollut rikki? Tällaiselle paikalle ei voi laittaa esim. tekstiä "ei saatavilla", sillä numeroita sisältävä lista ei voi sisältää tekstiä (esim. Pythonissa voitaisiin listalle laittaa puuttuviin paikkoihin arvo 'None'). Toinen vaihtoehto olisi laittaa kys. paikalle todella korkea tai todella matala lämpötila, esim. -99999999 tai +999999999, mutta tämä tekee lämpötilojen käsittelystä monimutkaista.
Ratkaisu tähän on Maybe-tyyppi. Listan voidaan määritellä olevan tyyppiä [Maybe Int], jolloin lista voi sisältää joko alkioita jotka sisältävät numeroita tai myös alkioita joiden arvona on Nothing. Esim:

Koodia: [Valitse]

>>> let lista = [Just 1, Just 2, Nothing]
>>> :type lista
  lista :: [Maybe Integer]Nyt lämpötiloja käsittelevät funktiot voidaa määritellä niin että Nothing-konstruktorilla luodun arvon kohdatessaan ne käsittelevät sen oikein, esim. päivän keskilämpötilaa laskettaessa Nothing-arvot hypätään kokonaan yli. Näin olemme saaneet käyttöön Pythonin 'None'-arvoa muistuttavan arvon Nothing, jota voidaan käyttää minkä tahansa tietotyypin kanssa.

[snifi]

Tämän viikon luennot on nimetty "Algebralliset tietotyypit osa 3 ja 4".

Luentomonisteet ja videot tässä:

Koodia: [Valitse]

# Luentomoniste:
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect13.pdf
# Haskell-ohjelmat:
wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect13.zip
# Luento 14:
wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-07/Informatics_1___Functional_Programming-video.m4v" -O Lecture_14.m4v
# Luento 15:
wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-09/Informatics_1___Functional_Programming-video.m4v" -O Lecture_15.m4v
#
#

[snifi]

Luentoja ei ole enää pitkästi jäljellä, nyt tulevat "Tyyppiluokat osa 1 ja 2":

Koodia: [Valitse]

# Luentomoniste:
 wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect15.pdf
# Haskell-ohjelmat:
 wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect15.zip
# Luento 16:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-14/Informatics_1___Functional_Programming-video.m4v" -O Lecture_16.m4v
# Luento 17:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-15/Informatics_1___Functional_Programming-video.m4v" -O Lecture_17.m4v
#
#

[snifi]

Tänään joudumme häädetyiksi täydellisestä rinnakkaisesta universumista, sillä nyt ovat vuorossa "IO ja monadit".

Koodia: [Valitse]

# Luentomoniste:
 wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect17.pdf
# Haskell-ohjelmat:
 wget http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/lectures/2011/lect17.zip
# Luento 18:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-21/Informatics_1___Functional_Programming-video.m4v" -O Lecture_18.m4v
# Luento 19:
 wget -c "http://podcast.is.ed.ac.uk:8080/Podcasts/capturED/D747/INFR08013/2011-11-22/Informatics_1___Functional_Programming-video.m4v" -O Lecture_19.m4v
#
#
Ensi viikon luentojen sisällöstä en ole enää ihan varma, saattaa olla että nämä olivat nyt viimeiset tällä kertaa.