Inleiding tot Func.oneel Programmeren Kris Luyten, Jo Vermeulen {kris.luyten,jo.vermeulen}@uhasselt.be
Exper.secentrum voor Digitale Media Universiteit Hasselt
Wat is func.oneel programmeren?
Alles via func&es
Wat is func.oneel programmeren?
Alles via expressies die geëvalueerd worden
Wat is func.oneel programmeren?
volgende 5 = 6
Wat is func.oneel programmeren?
volgende x = x+1
Wat is func.oneel programmeren?
volgende :: Integer -‐> Integer volgende x = x+1
Wat is func.oneel programmeren? Type signature declara&on volgende :: Integer -‐> Integer volgende x = x+1 Func&on Defini&on
Wat is func.oneel programmeren? fac 5 = 5 * 4 * 3 * 2 * 1 fac 4 = 4 * 3 * 2 * 1
Wat is func.oneel programmeren? fac 5 = 5 * 4 * 3 * 2 * 1 fac 4 = 4 * 3 * 2 * 1
Wat is func.oneel programmeren? fac 5 = 5 * (fac 4) fac 4 = 4 * 3 * 2 * 1
Wat is func.oneel programmeren? fac 5 = 5 * (fac 4) fac 4 = 4 * 3 * 2 * 1 fac n = n * (n-‐1) * (n-‐2) * … * 2 * 1 fac n = n * fac (n-‐1)
Wat is func.oneel programmeren? fac 5 = 5 * (fac 4) fac 4 = 4 * 3 * 2 * 1 fac n = n * (n-‐1) * (n-‐2) * … * 2 * 1 fac :: Int -‐> Int fac n = n * fac (n-‐1)
Waarom func.oneel programmeren?
Anders leren denken.
Waarom func.oneel programmeren?
Anders leren denken.
Beter Efficiënter Leesbaarder
Programmeren
Waarom func.oneel programmeren? “LISP is worth learning for a different reason — the profound enlightenment experience you will have when you finally get it. That experience will make you a beGer programmer for the rest of your days, even if you never actually use LISP itself a lot.” – Eric S. Raymond “SQL, Lisp, and Haskell are the only programming languages that I've seen where one spends more &me thinking than typing.” – Philip Greenspun “I do not know if learning Haskell will get you a job. I know it will make you a beGer soRware developer.” – Larry O’ Brien
Waarom func.oneel programmeren? • Programmeren met func.es • Geen “side effects” – Geen expliciete toekenning van waardes aan variabelen x := 4; x:= x + 9;
• Gebaseerd op een goed gedefinieerde wiskundige basis (bijv. de lambda calculus) • Idempotente uitvoering van func.es – Opnieuw uitvoeren geee hetzelfde effect
Waarom func.oneel programmeren? • Programmeren met func.es • Geen “side effects” – Geen expliciete toekenning van waardes aan variabelen x := 4; Destruc&ve x:= x + 9; update
• Gebaseerd op een goed gedefinieerde wiskundige basis (bijv. de lambda calculus) • Idempotente uitvoering van func.es – Opnieuw uitvoeren geee hetzelfde effect
Waarom func.oneel programmeren? • Eenvoudig programmeerparadigma • Ingebouwde abstrac.e inclusief data abstrac.e (ADT) • Krach.ge ondersteuning voor genericiteit, polymorfisme en overloading
Waarom func.oneel programmeren? • • • •
Correctheid Paralleliseerbaarheid Expressiviteit Modulariteit
Waarom func.oneel programmeren? Paralleliseerbaarheid
Mul&-‐core
Cloud compu&ng
Waarom func.oneel programmeren? Betere modulariteit
Hogere orde func.es Func&es met func&es als input / output
Luie evalua.e Berekening uitstellen tot resultaat nodig is
Waarom func.oneel programmeren? Betere modulariteit
Hogere orde func.es Func&es met func&es als input / output
Luie evalua.e Berekening uitstellen tot resultaat nodig is
Waarom func.oneel programmeren? Toenemend belang in verschillende domeinen – Soeware engineering – Web applica.es (Map/Reduce, Hadoop, CouchDB) – Impera.eve en object-‐georienteerde programmeertalen (Python, Ruby, C#, Java, JavaScript) – Opkomende func.onele talen (F#, Scala, Clojure)
C# LINQ (.NET) int someValue = 5; var results = from c in SomeCollection where c.SomeProperty < someValue * 2 select new {c.SomeProperty, c.OtherProperty}; foreach (var result in results) { Console.WriteLine(result); }
hpp://en.wikipedia.org/wiki/Language_Integrated_Query
Python >>> vec = [2, 4, 6] >>> [3*x for x in vec] [6, 12, 18] >>> def mul9(x): return x % 9 == 0 ... >>> filter(mul9, vec) [18] hpp://en.wikipedia.org/wiki/Language_Integrated_Query
backend
Func&onele programmeertaal bovenop de Java VM
hpp://www.ar.ma.com/scalazine/ar.cles/twiper_on_scala.html hpp://www.scala-‐lang.org
Welke talen zijn er? Ik wil func.oneel programmeren,met welke taal begin ik? • Lisp, Scheme, Guile • ML, Haskell, Ocaml, Scala, Clojure, Mozart/Oz, Mercury, … • Ruby, Python, … • C, Java, … • XSLT Talen verschillen in “zuiverheid”. bv. Scheme is niet side-‐effect free
Welke taal gebruiken wij? Haskell hpp://www.haskell.org Een luie en zuiver func.onele programmeertaal
Lui? List makeList() { List current = new List(); current.value = 1; current.next = makeList(); return current; } makeList().getItem(10);
Oneindige lus!
Lui? makeList = 1 : makeList print makeList[10]
makeList maakt enkel de 10 eerste items aan Haskell gebruikt call-‐by-‐need seman&ek (zie later)
Zuiver? • Geen side effects • Een func.e die opgeroepen wordt met dezelfde parameters als voorheen zal gegarandeerd hetzelfde resultaat teruggeven • Referen.al transparancy (func.e en resultaat zijn uitwisselbaar) • Houdt zich strikt aan de lambda calculus
Nog wat specifieke Haskell eigenschappen • Case-‐sensi.ve – Func.enamen starten al.jd met kleine leper – Typenamen starten al.jd met een grote leper
• Indenta.e
Soeware • ghc (compiler) – ghci (interac.eve shell) • Hugs (interpreter) • hlint (code beau.fier) • hoogle (API documtenta.e search engine)
Haskell Plauorm
hpp://hackage.haskell.org/plauorm/
GHC • Compiler: – Schrijf Haskell programma en bewaar in een .hs bestand – Compileer met: “ghc –o naam naam.hs” – Voer ./naam uit
• Interpreter – Start ghci naam.hs – Of :load naam.hs als ghci opgestart is – Verlaat de shell met :quit
Hallo Wereld hallo.hs
main = putStrLn “Hallo Wereld” !
console
$> ghc –o hallo hallo.hs! $> ./hallo! Hallo Wereld! $>!
fac fac.hs
fac n = if n==0 then 1 else n * fac (n-1)! main = print (fac 42)!
console
$> ghc –o fac fac.hs! $> ./fac! $> 1405006117752879898543142606244511569936384000000000!
ifac.hs
fac
Wat code om user fac 0 = 1! fac n = n * fac (n-1)! input te main = do! ondersteunen !putStrLn ”in:" ! !nummer <- getLine! !print (fac (read nummer))! ! console
$> ghc –o ifac ifac.hs! $> ./ifac! $> in: 20! 2432902008176640000!
ifac.hs
fac
fac 0 = 1! fac n = n * fac (n-1)! Read zorgt voor automa&sche type conversie main = do! !putStrLn ”in:" ! !nummer <- getLine! !print (fac (read nummer))! ! console
$> ghc –o ifac ifac.hs! $> ./ifac! $> in: 20! 2432902008176640000!
fac fac.hs
fac 0 = 1! fac n = n * fac (n-1)! main = print (fac 42)!
Met paGern matching
console
$> ghc –o fac fac.hs! $> ./fac! $> 1405006117752879898543142606244511569936384000000000!
Basis bewerkingen Interac.ve shell: ghci
Prelude>5*2+8! 18! Prelude>sqrt 25! 5! Prelude>sqrt 2! 1.4142135623730951! Prelude>5*(2+8)! 50! !
Paren en Triples Interac.ve shell
Prelude>(8,20)! (8,20)! Prelude>(1,3,5)! (1,3,5)! Prelude>fst (“nul”,0)! nul! Prelude>snd (“nul”,0)! 0! !
First Second
Lijsten Interac.ve shell
Prelude>[1,3,5]! Element toevoegen [1,3,5]! met cons (:) operator Prelude>0:[1,3,5]! [0,1,3,5]! Prelude>0:1:3:5:[]! [0,1,3,5]! Prelude>[(1,1),(2,3),(4,8),(9,999)]! [(1,1),(2,3),(4,8),(9,999)]! !
Lijsten Interac.ve shell
Prelude>head [1,3,5]! 1! Prelude>tail [1,3,5]! [3,5]! Prelude>length [(1,1),(2,3),(4,8),(9,999)]! 4! Prelude>length (tail [1,3,5,9,4,8,999])! 6! ! !
Strings Interac.ve shell
Prelude> “h”:”a”:”l”:”l”:”o”:[]! “hallo”! Prelude>”hallo” ++ “ “ ++ “wereld”! “hallo wereld”! Prelude>”2 maal 5 is ” ++ show (2*5)! “2 maal 5 is 10”! ! show zorgt voor !
type conversie
Concatena.e • ++ concateneert twee lijsten ? ? ? ? ?
(x:xs) ++ (y:ys) [] ++ [] x ++ y (x:xs) ++ y (x:xs) ++ (y:[])
• : voegt een element toe vooraan een lijst ? x: [a,b,c] ? x:(y:xs) ? (y:xs):x
Probeer de voorbeeldjes uit met ghci. Wat werkt er en wat niet?
length length.hs
length length length main =
Met paGern matching
:: [a] -> Int! [] = 0! (x:xs) = 1 + length xs! print (length [1,2,3,4,5,6,7,8])!
console
$> ghc –o length length.hs! $> ./length! $> 8!
zip zip :: [a]-‐>[b]-‐>[(a,b)] zip [] ys = [] zip xs [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys zip voegt elementen van twee lijsten paarsgewijs samen in een nieuwe lijst
Signatures lezen zip :: [a]-‐>[b]-‐>[(a,b)] Input: twee lijsten [a] en [b] Output: nieuwe lijst van tuples [(a,b)] uit [a] en [b]
zip zip :: [a]-‐>[b]-‐>[(a,b)] zip (x:xs) (y:ys) = (x,y) : zip xs ys zip xs ys = [] zip voegt elementen van twee lijsten paarsgewijs samen in een nieuwe lijst
-‐-‐ geee een regel commentaar aan
zip
zipit.hs
-- zip is reeds gedefinieerd in prelude! -- zip (x:xs) (y:ys) = (x,y) : zip xs ys! -- zip xs ys = []! main = print ( zip [2,4,7,5] [1,0,4,8,37,25])!
console
$> ghc –o zipit zipit.hs! $> ./zip! $> [(2,1),(4,0),(7,4),(5,8)]!
foldr • Pas opera.e toe op de elementen van een lijst – Opera.es zijn eerste klasse waardes in een func.onele programmeertaal!
• foldr vervangt “:” door een opera.e en [] door een ini.eel element – foldr is rechts-‐associa.ef
foldr! !
+ 100! 1:0:3:5:10:[]! ! ! 1+0+3+5+10+100! ! 119! !
foldr
is een hogere orde func&e
Interac.ve shell
Prelude>foldr (*) 1 [2,5,4]! 40! Prelude>foldr (-) 2 [10,4,3]! 7! ! foldr :: (a -‐> b -‐> b) -‐> b -‐> [a] -‐> b foldr op u [] = u foldr op u (x:xs) = op x (foldr op u xs)
foldr is rechts associa&ef hGp://foldr.com
foldr
is een hogere orde func&e
Interac.ve shell
Prelude>foldr (*) 1 [2,5,4]! 40! Prelude>foldr (-) 2 [10,4,3]! 7! !
?
foldr :: (a -‐> b -‐> b) -‐> b -‐> [a] -‐> b foldr op u [] = u foldr op u (x:xs) = op x (foldr op u xs)
foldr is rechts associa&ef hGp://foldr.com
foldr foldr (-‐) 2 [10,4,3] 10 -‐ (foldr (-‐) 2 [4,3]) 10 -‐ (4 -‐ (foldr (-‐) 2 [3])) 10 -‐ (4 -‐ (3 -‐ (foldr (-‐) 2 []))) 10 -‐ (4 -‐ (3 -‐ 2)) 10 -‐ (4 -‐ 1) 10 – 3 7! + associa&ef !
-‐ niet
foldl Interac.ve shell
Prelude>foldl (*) 1 [2,5,4]! 40! Prelude>foldl (-) 2 [10,4,3]! 7! ! foldl :: (a -‐> b -‐> a) -‐> a -‐> [b] -‐> a foldl op u [] = u foldl op u (x:xs) = foldl op (op u x) xs
foldl is links associa&ef hGp://foldl.com
foldl foldl (-‐) 2 [10,4,3] foldl (-‐) (2-‐10) [4,3] foldl (-‐) ((2-‐10)-‐4) [3] foldl (-‐) (((2-‐10)-‐4)-‐3) [] ((2-‐10)-‐4)-‐3 (-‐8-‐4)-‐3 -‐12-‐3 -‐15 -‐ niet associa&ef !
map map :: (a-‐>b) -‐> [a] -‐> [b] map f [] = [] map f (x:xs) = f x : map f xs Map past een func&e toe op elk element van een lijst
map map :: (a-‐>b) -‐> [a] -‐> [b] map f [] = [] Func&e als f (x:xs) = f x : map f xs map argument Map past een func&e toe op elk element van een lijst
map map :: (a-‐>b) -‐> [a] -‐> [b] map f [] = [] Func&e m apt ef en type = f x : map f xs map (x:xs) a naar type b Map past een func&e toe op elk element van een lijst
map map :: (a-‐>b) -‐> [a] -‐> [b] map f [] = [] Lijst met elementen map f (x:xs) v=an f x : map f xs type a wordt omgezet
naar lijst met elementen van type b
Map past een func&e toe op elk element van een lijst
map map.hs
add x y = x + y! main = print (map (add 1) [3,4,5,6,7,8])!
console
$> ghc –o map map.hs! $> ./map! $> [4,5,6,7,8,9]!
map map2.hs
main = print (map fac [0,1,4,5,3,2])!
console
$> ghc –o map2 map2.hs! $> ./map2! $> [1,1,24,120,6,2]!
Quicksort in twee regels… quicksort.hs
qSort :: [Int] -> [Int]! qSort [] = []! qSort (x:xs) ! != qSort [y | y<-xs , y<=x] ++ [x] ++ ! qSort [y | y<-xs , y>x]! ! main = print (qSort [-4,5,9,9,1,25,6,3])! console
$> ghc –o quicksort quicksort.hs! $> ./quicksort! $> [-4,1,3,5,6,9,9,25]!
Quicksort
Quicksort in twee regels… qSort :: [Int] -> [Int]! qSort [] = []! qSort (x:xs) ! != qSort [y | y<-xs , y<=x] ++ [x] ++! ! !qSort [y | y<-xs , y>x]! ! main = print (qSort [-4,5,9,9,1,25,6,3])!
Een lege rij sorteren geee een lege rij…
Quicksort in twee regels… qSort :: [Int] -> [Int]! qSort [] = []! qSort (x:xs) ! [x] ++! != qSort [y | y<-xs , y<=x] ++ [x] ! !qSort [y | y<-xs , y>x]! ! main = print (qSort [-4,5,9,9,1,25,6,3])!
Als er elementen in de rij zipen: neem het eerste als spil
Quicksort in twee regels… qSort :: [Int] -> [Int]! qSort [] = []! qSort (x:xs) ! != qSort [y | y<-xs , y<=x] ++ ! [x] ++! ! !qSort [y | y<-xs , y>x]! ! main = print (qSort [-4,5,9,9,1,25,6,3])!
List comprehension Neem alle elementen uit xs die kleiner of gelijk zijn aan x
List comprehension compr.hs
isVeelvoudVanDrie :: Int -> Bool! isVeelvoudVanDrie x = (x `mod` 3 == 0) ! main = print ([x| x<-[1,8,9,999,5,6,2718]! ! ! ! ! ! ! !,! ! ! ! ! ! ! isVeelvoudVanDrie x)!
console
$> ghc –o compr compr.hs! $> ./compr! $> [9,999,6,2718]!
List comprehension sqrtpairs.hs
sqrtPairs :: [Int]->[Int]->[(Int,Int)]! sqrtPairs l r = [ (x,y) | x <- l , y <-r,! ! ! ! ! ! ! ! ! ! ! ! !x*x==y ]! main = print ( sqrtPairs [1,0,2,4,7,5] [1,0,4,8,37,25])!
console
$> ghc –o sqrtpairs sqrtpairs.hs! $> ./sqrtpairs! $> [(1,1),(0,0),(2,4),(5,25)]!
List comprehension sqrtpairs2.hs
sqrtPairs :: [Int]->[Int]->[(Int,Int)]! sqrtPairs l r = [ (x,y) | x <- l , y <-r,! ! ! ! ! ! ! ! ! ! ! ! !x*x==y, y>x ]! main = print ( sqrtPairs [1,0,2,4,7,5] [1,0,4,8,37,25])!
console
$> ghc –o sqrtpairs2 sqrtpairs2.hs! $> ./sqrtpairs2! $> [(2,4),(5,25)]!
List comprehension sqrtpairs3.hs
sqrtPairs :: [Int]->[Int]->[(Int,Int)]! sqrtPairs l r = [ ((x*2),(y*3)) |
! ! ! ! ! ! ! ! ! ! !x <- l , y <-r,! ! ! ! ! ! ! ! ! ! ! !x*x==y, y>x ]! main = print ( sqrtPairs [1,0,2,4,7,5] [1,0,4,8,37,25])!
console
$> ghc –o sqrtpairs3 sqrtpairs3.hs! $> ./sqrtpairs3! $> [(4,12),(10,75)]!
Guards: switch met papern matching • Condi.es in de func.e • Gelijkaardig met een switch statement in C mijnmax.hs
mijnmax :: Int -> Int -> Int! mijnmax x y ! ! !| x >= y! ! != x! ! !| otherwise != y!
• Evalua.e gebeurt na papern matching!
Guards: switch met papern matching Condi0e De expressie achter de condi.e wordt uitgevoerd als de condi.e waar is mijnmax.hs
mijnmax :: Int -> Int -> Int! mijnmax x y ! ! !| x >= y! ! != x! ! !| otherwise != y! Als geen van de voorgaande condi.es als waar evalueert
Guards: switch met papern matching facg.hs
Met guards fac n ! !| n==0 = 1! !| otherwise = n * fac (n-1)! main = print (fac 42)! console
$> ghc –o facg facg.hs! $> ./fac! $> 1405006117752879898543142606244511569936384000000000! Op hoeveel manieren kan men deze func.e wel niet schrijven? hpp://www.willamepe.edu/~fruehr/haskell/evolu.on.html
Guards: switch met papern matching functie_naam functie_args! ! !| guard1 = expressie_bij_guard1! !| guard2 = expressie_bij_guard2! !| guard3 = expressie_bij_guard1! !…! !| otherwise = expressie_bij_otherwise!
!
Betekent dus hetzelfde als
functie_naam functie_args! ! !if guard1 then expressie_bij_guard1! !else if guard2 then expressie_bij_guard2! !else if guard3 then expressie_bij_guard1! !…! !else expressie_bij_otherwise!
…iets moeilijker: priemfactorisa.e priemfact.hs
import System.IO! -- van haskell.org! ! primeFactors :: Int -> [Int]! primeFactors n = primeFactors2 n 2! ! primeFactors2 :: Int -> Int -> [Int]! primeFactors2 1 _ = []! primeFactors2 n factor! | n `mod` factor == 0 = factor :
! ! ! primeFactors2 (n `div` factor) factor! | otherwise = primeFactors2 n (factor + 1)! ! main = do! !putStrLn "Geef een geheel getal:" ! !nummer <- getLine! !print ( primeFactors (read nummer) )!
maar nog steeds makkelijker dan in een impera.eve taal!
priemfact.hs
import System.IO! -- van haskell.org!Deler gevonden: voeg toe ! vooraan de lijst primeFactors :: Int -> [Int]! primeFactors n = primeFactors2 n 2! Neem het volgende getal ! primeFactors2 :: Int -> Int -> [Int]! (n/f) en voer daarmee de primeFactors2 1 _ = []! factorisa.e verder uit primeFactors2 n factor! | n `mod` factor == 0 = factor :
! ! ! primeFactors2 (n `div` factor) factor! | otherwise = primeFactors2 n (factor + 1)! ! main = do! !putStrLn "Geef een geheel Anders: getal:" p!robeer volgende !nummer <- getLine! getal als deler !print ( primeFactors (read nummer) )!
Prelude.hs • De standaard Haskell library met een schat aan voorgedefinieerde func.es – hpp://haskell.org/ghc/docs/latest/html/libraries/ base/Prelude.html
• Ook handig om zelf Haskell mee te leren
Types • Karakters en Strings • Numerieke types: Integer, Float,… • Boolean: True en False – Logische en: &&, logische of: || en nega.e: not
• Polymorfe types “a” – Worden afgeleid door Haskell zelf
• Types makkelijk uitbreidbaar dankzij type classes (behandelen we niet)
console
:t vTypes raagt het type op in de interac.eve shell
$> ghci! Prelude> :t 42! 42 :: (Num t) => t! Prelude> :t "Hallo"! "Hallo" :: [Char]! Prelude> :t 3.1415! 3.1415 :: (Fractional t) => t! Prelude> :t x! Prelude> :t [1,2,45]! [1,2,45] :: (Num t) => [t]! Prelude> :t [1,2,45.4]! [1,2,45.4] :: (Fractional t) => [t]! Prelude> :t ["hallo", "h"]! ["hallo", "h"] :: [[Char]]! Prelude> :t ['h','a','l','l','o']! ['h','a','l','l','o'] :: [Char]!
!
Currying f: (X × Y) Z Currying: een func.e met meerdere parameters omzepen naar verschillende func.es met telkens 1 parameter
f: X (Y Z) f x y = z (f x) y = z ((f x) y) = z
f x = \y -‐> z f = \x -‐> \y -‐> z
Currying • Som :: (Int,Int)-‐>Int kan Som :: Int-‐>Int-‐>Int worden – “Som 5 6” is een func.e, maar “Som 5” kan evengoed gebruikt worden als argument voor een andere func.e (bijv. de map func.e)
• Func.es worden beter herbruikbaar -‐ “Par.ële” func.es als argument -‐ Func.es samenstellen (f en g wordt f.g)
Evalua.e Strategie • Op welke manier wordt een expressie geëvalueerd? – De manier waarop argumenten van een func.e worden geëvalueerd bij een func.e-‐oproep.
• Strikte versus niet-‐strikte evalua.e – Strikt: parameters func.e wordt geëvalueerd voor uitvoering func.e – Niet-‐strikt: parameters func.e worden niet geëvalueerd tenzij deze gebruikt worden. Evalua.e van de parameters gebeurt dan niet noodzakelijk voor de uitvoering van de func.e
Strikte evalua.e • Call-‐by-‐Value: parameter expressies worden geëvalueerd en toegekend aan een variabele naam (copy!) voor uitvoering func.e. Func.e aanroep: !int i=3; ! !bereken(i);! Func.e def: !int bereken(int j){! ! !j = j + j*2;! ! !return j;! !};! Java, ML, Scheme, C, Pascal,…
Strikte evalua.e • Call-‐by-‐Reference: : parameter expressies worden geëvalueerd en een variabelenaam verwijst naar de waarde (referen.e naar geheugen!) voor uitvoering van de func.e. Func.e aanroep: !int i=3; ! !bereken(i);! Func.e def: !int bereken(int& j){! ! !j = j + j*2;! ! !return j;! !}!
Func.e aanroep: !int i=3; ! !bereken(&i);! Func.e def: !int bereken(int* j){! ! !*j = *j + (*j)*2;! ! !return *j;! !}!
Niet-‐strikte evalua.e • Call-‐by-‐Name: iedere verwijzing naar de expressie wordt vervangen door de expressie zelf. De expressie wordt opnieuw geëvalueerd bij elk gebruik ervan. Func.e aanroep: !a[0]=3; a[1]=14;! !int i =0; ! !bereken(a[i],&i);!
!
Func.e def: !int bereken(int l, int i){! ! !l = l+1;! ! !i = i+1;! ! !l = l-1! ! !return l;! !}!
Niet-‐strikte evalua.e • Call-‐by-‐Name: iedere verwijzing naar de expressie wordt vervangen door de expressie zelf. De expressie wordt opnieuw geëvalueerd bij elk gebruik ervan. Func.e aanroep: !a[0]=3; a[1]=14;! !int i =0; ! !bereken(a[i],&i);!
!
Func.e def: !int bereken(int a[i], int i){! ! !a[i] = a[i]+1;! ! !i = i+1;! ! !a[i] = a[i]-1! ! !return a[i];! !}!
Zelden of nooit ondersteund in de meeste programmeertalen. Algol60 is de bekendste taal die call-‐by-‐name implementeert.
Niet-‐strikte evalua.e • Call-‐by-‐Need: werkt zoals call-‐by-‐name maar na de eerste evalua.e wordt die waarde verder gebruikt. In pure func.onele programmeertalen is het effect hetzelfde als call-‐by-‐name en wordt vaak “Lazy Evalua.on” genoemd. plus14 x y = x+x! plus14 (2*3) (4-2)! ! Haskell implementeert call-‐by-‐need. Verschillende andere talen ondersteunen deze seman.ek ook, naast call-‐by-‐value: D, Scheme, Nemerle, Python,…
Func.es samenvoegen • Verschillende func.es samen voegen met “.” • Uitvoer van func.e wordt invoer van andere func.e • “ f . g “ betekent dat de func.e f na g wordt uitgevoerd met als input van f de output van g f x = x*3! driekeer f = f . f . f! main = print ((driekeer f) 4)!
Func.es samenvoegen Leg uit wat het volgende stukje code doet: import List! letterT = last . transpose . group . sort! main = print (letterT "bladerdeeg”)!
Maak bijvoorbeeld gebruik van Hoogle: hpp://www.haskell.org/hoogle/
Oefeningen set 1 (makkelijk) • Schrijf de volgende func.es – Omdraaien van een lijst (in: [1,2,5], uit: [5,2,1]) – Roteren van een lijst (in: [1,2,3,4], uit: [4,1,2,3]) – Combineer (herbruik) beide func.es in een nieuwe func.e roteerdraaiom (in: [1,2,3,4], uit: [1,4,3,2])
• Schrijf de volgende func.es die een func.e toepassen – Gebruik de map func.e om de func.es “omdraaien” en “roteren” toe te passen op een lijst van lijsten – Schrijf een func.e max:: Int-‐>Int-‐>Int die het maximum van twee integers teruggeee en pas die met foldl (of foldr) toe op een constante en een lijst van integers
Oefeningen set 2 (makkelijk) • Schrijf een func.e optellen :: Int -‐> Int die de eenheden van een getal bij elkaar optelt. optellen 1500 = 6 optellen 123456 = 21 • Schrijf een func.e die graden celcius naar graden farenheit omzet. Schrijf tevens de func.e die graden farenheit naar celcius omzet. • Schrijf een func.e die gegeven een lijst de duplicaten uit die lijst verwijdert
Oefeningen set 3 (medium) • Schrijf een func.e die de lijst van fibonacci nummers genereert (gebruik de luie eigenschap van Haskell). Schrijf een andere func.e die de eerste n elementen uitschrije van de lijst. Laat de gebruiker n zelf ingeven. • Schrijf een func.e bevat :: [Int]-‐>[Int]-‐>Bool die gegeven twee lijsten teruggeee of de sequen.e van elementen van de eerste lijst ook voorkomt in de tweede lijst. Bijv. bevat [1,2] [6,10,1,2,8] = True en bevat [1,8] [8,8,7] = False
Oefeningen set 4 (medium-‐moeilijk) • Jolly Jumpers: een lijst getallen van lengte n noemt men jolly jumpers als het verschil tussen opeenvolgende getallen alle waardes tussen 0 en n aanneemt. Zo is de lijst 1,4,2,3 een jolly jumper omdat de verschillen tussen de opeenvolgende getallen 3,2 en 1 zijn. Schrijf een func.e jjumpers :: [Int] -‐> Bool die True teruggeee als de lijst een jolly jumper is.
Oefeningen set 4 (medium-‐moeilijk) • Schrijf een programma dat een nummer N in leest en een lijst teruggeee van alle Smith nummers tussen 0 en N. Hergebruik primefactors hiervoor. Een Smith getal is een getal waarvan de som van de eenheden van de priemfactorisa.e gelijk is aan de som van de eenheden van het getal. Bijvoorbeeld: 378 = 2 × 3 × 3 × 3 × 7 en 3 + 7 + 8 = 2 + 3 + 3 + 3 + 7 • Zorg ervoor dat er geen priemgetallen in de lijst voorkomen • Geef een lijst van alle “Smith broers”: twee opeenvolgende getallen die beide Smith getallen zijn zoals […,(94094, 94095), (94184, 94185), (94584, 94585), …] • Geef enkel Smith nummers die een palindroom zijn, zoals 454
Oefeningen • Meer oefeningen maken? – hpp://www.haskell.org/haskellwiki/99_Haskell_exercises – hpp://www.haskell.org/haskellwiki/Blog_ar.cles/ Exercises
Referen.es • Haskell: The Crae of Func.onal Programming (second edi.on), Simon Thompson • Haskell Wikibook; hpp://en.wikibooks.org/wiki/Haskell • A gentle introduc.on to Haskell, Paul Hudak, John Peterson, Joseph Fasel; hpp://www.haskell.org/tutorial/ • Yet Another Haskell Tutorial: hpp://en.wikibooks.org/wiki/Haskell/YAHT • hpp://www.haskell.org • Voor de beslagen programmeur: The Haskell School of Expression: Learning Func.onal Programming through Mul.media, Paul Hudak, hpp://www.haskell.org/soe/ • Leuk om te weten: Wearing the hair shirt: a retrospec.ve on Haskell, Simon Peyton Jones. hpp://research.microsoe.com/~simonpj/papers/haskell-‐ retrospec.ve/
Ook interessant (1)
hpp://www.cs.chalmers.se/ ~rjmh/Papers/whyfp.html
hpp://haskell.org/haskellwiki/ Why_Haskell_mapers
Ook interessant (2)
hpp://book.realworldhaskell.org/
Ook interessant (3)
A taste of Haskell hpp://research.microsoe.com/en-‐us/um/ people/simonpj/papers/haskell-‐tutorial/
Ook interessant (4)
hpp://labs.google.com/papers/mapreduce.html
