Funkcion´alis programoz´as 2. el˝oad´as ´ MARTON Gy¨ ongyv´er Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania
[email protected]
2016, tavaszi f´ el´ ev
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Mir˝ol volt sz´o?
Programoz´ asi paradigm´ ak: imperat´ıv, funkcion´ alis, logikai programoz´ asi technik´ ak. Alapt´ıpusok, megjegyz´esek haszn´ alata. A funkcion´ alis programoz´ as, a Haskell programoz´ asi nyelv f˝ obb jellemz˝ oi: felt´etelek megad´ asa, rekurzi´ o, mintailleszt´es, szigor´ u, statikus t´ıpusoss´ ag, marg´ o szab´ aly, halmazkifejez´esek, magasabb rend˝ u f¨ uggv´enyek.
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Mir˝ol lesz sz´o?
lambda kifejez´esek f¨ uggv´enykompoz´ıc´ı´ o magasabb rend˝ u f¨ uggv´enyek r´eszleges param´eterez´ese felt´eteles kifejez´esek a Haskell ki´ert´ekel´esi strat´egi´ aja GHC parancsok k¨ onyvt´ armodul import´ al´ asa alaposzt´ alyok a tuple t´ıpus, k¨ onyvt´ arf¨ uggv´enyek
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Lambda kifejez´esek A f¨ uggv´enyek egy alternat´ıv defini´ al´ asi m´ odja. 1. feladat: a megadott param´eter ´ert´ek´et 1-el n¨ oveli: my_inc :: (Num a) => a -> a my_inc = \x -> x + 1 Prelude> my_inc 23.5 24.5 2. feladat: a lista minden egyes elem´enek ´ert´ek´et 1-el n¨ oveli: l_inc :: (Num a) => [a] -> [a] l_inc ls = map (\x -> x + 1) ls Prelude> l_inc [1..10] [2,3,4,5,6,7,8,9,10,11]
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
F¨uggv´enykompoz´ıci´o A matematik´ ab´ ol ismert m˝ uvelet megfelel˝ oje. 3. feladat: a lista p´ aratlan elemeinek meghat´ aroz´ asa (kisz˝ ur´ese) paratlanL :: (Integral a) => [a] -> [a] paratlanL ls = filter (not . even) ls Prelude> paratlanL [1..20] [1,3,5,7,9,11,13,15,17,19] A f¨ uggv´enyparam´eter elhagyhat´ o: paratlanL_1 :: (Integral a) => [a] -> [a] paratlanL_1 = filter (not . even) Prelude> paratlanL_1 [1..20] [1,3,5,7,9,11,13,15,17,19]
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
F¨uggv´enykompoz´ıci´o 4. feladat: a kor´ abbi my_inc megh´ıv´ asa my_twice2 :: (Num a) => a -> a my_twice2 = my_inc . my_inc Prelude> my_twice2 12 14 5. feladat: init, tail k¨ onyvt´ arf¨ uggv´enyek Prelude> init [1..10] [1,2,3,4,5,6,7,8,9] Prelude> tail [1..10] [2,3,4,5,6,7,8,9,10] suffL :: [a] -> [a] suffL = (init.tail) Prelude> suffL "gezakekazeg" "ezakekaze" ´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Magasabb rend˝u f¨uggv´enyek r´eszleges param´eterez´ese angol terminol´ ogia: partial parameterization, curry-z´es, Haskell Curry angol matematikus neve ut´ an, a f¨ uggv´enyh´ıv´ as megengedett kevesebb param´eterrel is, mint ahogy az a f¨ uggv´eny szignatur´ aj´ aban meg van hat´ arozva 6. feladat: adott sz´ am hatv´ any´ert´ekei 0-t´ ol 10-ig (a kitev˝ o v´ altozik): hatv1 :: (Integral a) => a -> a -> a hatv1 x n | n < 0 = error "Negativ kitevo" | n == 0 = 1 | mod n 2 == 0 = hatv1 (x*x) (div n 2) | otherwise = x * hatv1 (x*x) (div n 2) fugv1 :: (Integral a) => a -> [a] fugv1 x = map (hatv1 x) [0..10] > fugv1 3 [1,3,9,27,81,243,729,2187,6561,19683,59049] ´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Magasabb rend˝u f¨uggv´enyek r´eszleges param´eterez´ese 7. feladat: a sz´ amok hatv´ anyai 0-t´ ol 10-ig (az alap v´ altozik): hatv2 :: (Integral a) => a -> a -> a hatv2 n x | n < 0 = error "Negativ kitevo" | n == 0 = 1 | mod n 2 == 0 = hatv2 (div n 2) (x*x) | otherwise = x * hatv2 (div n 2) (x*x) fugv2 :: (Integral a) => a -> [a] fugv2 n = map (hatv2 n) [0..10] > fugv2 3 [0,1,8,27,64,125,216,343,512,729,1000]
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Magasabb rend˝u f¨uggv´enyek r´eszleges param´eterez´ese 8. feladat: adott sz´ am hatv´ any´ert´ekei 0-t´ ol 10-ig (a kitev˝ o v´ altozik): fugv3 :: (Integral a) => a -> [a] -> [a] fugv3 kit ls = map ((\x n -> x ^ n) kit) ls > fugv3 3 [0..10] [1,3,9,27,81,243,729,2187,6561,19683,59049] 9. feladat: a sz´ amok hatv´ anyai 0-t´ ol 10-ig (az alap v´ altozik): fugv4 :: (Integral a) => a -> [a] -> [a] fugv4 alap ls = map ((\n x -> x ^ n) alap) ls > fugv4 3 [0..10] [0,1,8,27,64,125,216,343,512,729,1000]
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Magasabb rend˝u f¨uggv´enyek r´eszleges param´eterez´ese
10. feladat: v´ alasszuk ki egy adott list´ ab´ ol az x-el oszthat´ o sz´ amokat: oszthato :: (Integral a) => a -> a -> Bool oszthato x y | mod y x == 0 = True | otherwise = False fugv :: (Integral a) => a -> [a] -> [a] fugv x ls = filter (oszthato x) ls > fugv 7 [1..100] [7,14,21,28,35,42,49,56,63,70,77,84,91,98]
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Felt´eteles kifejez´esek M´ asik f¨ uggv´eny az oszthat´ os´ ag vizsg´ alat´ ara: oszthato1 :: (Integral a) => a -> a -> Bool oszthato1 x y = if mod y x == 0 then True else False M´ asik f¨ uggv´eny a hatv´ anyoz´ asra: hatv3 :: (Integral a) => a -> a -> a hatv3 x n = if n < 0 then error "negativ kitevo" else if n == 0 then 1 else if mod n 2 == 0 then hatv3 (x*x) (div n 2) else x * hatv3 (x*x) (div n 2) > hatv3 2 100 1267650600228229401496703205376 Az if a Haskell-ben nem utas´ıt´ as (vagy ´ all´ıt´ as), hanem egy felt´eteles kifejez´es, ez´ert az else ´ ag k¨ otelez˝ o.
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
A Haskell ki´ert´ekel´esi strat´egi´aja funkcion´ alis programoz´ asi nyelvek eset´en k´etf´ele ki´ert´ekel´esi strat´egi´ at ismer¨ unk: lusta (lazy), moh´ o (eager) a Haskell ki´ert´ekel´esi strat´egi´ aja lusta, Lusta ki´ert´ekel´esi strat´egia: a legbaloldalibb, legk¨ uls˝ o redex (reduk´ alhat´ o kifejez´es) helyettes´ıt´ese t¨ ort´enik el˝ osz¨ or, pontosabban egy alkifejez´es csak akkor ´ert´ekel˝ odik ki, ha sz¨ uks´eg van az ´ert´ek´ere (ha a kifejez´es f¨ uggv´enymegad´ assal kezd˝ odik el˝ obb a f¨ uggv´enydefin´ıci´ o lesz alkalmazva) mindig megtal´ alja a norm´ al form´ at, ha az l´etezik Pl. Clean, Haskell, Miranda lehets´egess´e v´ alik a f¨ uggv´enyek k¨ otetlen defini´ al´ asa: egy f¨ uggv´eny akkor is k´epes ´ert´eket visszaadni, ha egyik argumentuma nem defini´ alt, lehets´egess´e v´ alik a v´egtelen adatszerkezetek l´etrehoz´ asa, a moh´ o ki´ert´ekel´esi strat´egi´ ahoz k´epest kev´esb´e hat´ekony. ´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
A moh´o (eager) ki´ert´ekel´esi strat´egia
a legbaloldalibb, legbels˝ o redex, az argumentumok helyettes´ıt´ese t¨ ort´enik meg el˝ osz¨ or, nem mindig ´er v´eget a ki´ert´ekel´esi folyamat, hat´ekonyabb mint a lusta rendszer, Pl. Lisp, SML, Hope, a lusta ki´ert´ekel´esi strat´egia hat´ekonys´ ag´ at oly m´ odon lehet jav´ıtani, hogy az azonos r´eszkifejez´eseket megjel¨ olj¨ uk, az eredm´enyt megjegyezz¨ uk ´es ah´ anyszor sz¨ uks´eg van r´ a mindig a megjegyzett eredm´enyt haszn´ aljuk.
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
P´elda, ki´ert´ekel´esi strat´egi´akra my_inc :: Num a => a -> a my_inc x = x+1 negyzet :: Num a => a -> a negyzet x = x*x negyzet_inc :: Num a => a -> a negyzet_inc x = negyzet (my_inc x) > negyzet_inc 6 A lusta ki´ert´ekel´esi strat´egia: negyzet_inc 6 -> negyzet(my_inc 6) -> (my_inc 6)*(my_inc 6) -> (6+1) * (6+1) -> 7 * 7 -> 49 ´ MARTON Gy¨ ongyv´ er
A moh´ o ki´ert´ekel´esi strat´egia: negyzet_inc -> negyzet( -> negyzet( -> negyzet( -> 7 * 7 ->
6 my_inc 6 ) 6 + 1 ) 7 ) 49
2016, Funkcion´ alis programoz´ as
GHC parancsok mindegyiket lehet r¨ ovid´ıtett form´ aban is haszn´ alni, csak a parancs kezd˝ obet˝ uj´evel: :reload fnev az fnev.hs nev˝ u´ allom´ any u ´jrabet¨ olt´ese, :type kif a kif kifejez´ese t´ıpus´ anak a lek´erdez´ese, :? az o ¨sszes GHC parancs lek´erdez´ese, :quit kil´ep´es a GHC-b˝ ol, :set +t a ki´ert´ekel´es ut´ an a kifejez´es t´ıpusa is megjelenik :unset +t az el˝ oz˝ o be´ all´ıt´ as visszavon´ asa :set +s a ki´ert´ekel´es ut´ an megjelenik az eltelt id˝ o ´es a lefoglalt b´ ajtok sz´ ama stb. Fenntartott szavak: case class data default deriving do else if import in infix infixl infixr instance let module newtype of then type where ´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
K¨onyvt´armodul import´al´asa import Data.Char my_isDigit :: Char -> Bool my_isDigit x = x >=’0’ && x <=’9’ > my_isDigit ’3’ True > isDigit ’3’ True > isDigit ’w’ False > import Data.List > tails "hello" ["hello","ello","llo","lo","o",""] ´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Alaposzt´alyok az Eq azokat a t´ıpusokat tartalmazza, amelyek az egyenl˝ os´eg ´es nem egyenl˝ os´eg oper´ atorokkal o ¨sszehasonl´ıthat´ oak: (==) :: a -> a -> Bool (/=) :: a -> a -> Bool az Ord mag´ aba foglalja az Eq oszt´ alyba tartoz´ o t´ıpusokat ´es a sorba rendezhet˝ o t´ıpusokat (Bool, Char, String, Int, Integer, Float, Double, Lista, Tuple): (<) :: a -> a -> Bool (<=) :: a -> a -> Bool (>) :: a -> a -> Bool (>=) :: a -> a -> Bool min :: a -> a -> Bool max :: a -> a -> Bool
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Alaposzt´alyok
a Show azokat a t´ıpusokat tartalmazza, amelyek ´ert´ekei ´ atalak´ıthat´ oak karakterl´ ancc´ a (String-´e). mag´ aba foglalja az alapt´ıpusokat (Bool, Char, String, Int, Integer, Float, Double, Lista, Tuple): show :: a -> String > show 579 "579" > show (’b’, True) "(’b’, True)"
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Alaposzt´alyok
a Read azokat a t´ıpusokat tartalmazza, amelyek ´ert´ek´et meg lehet hat´ arozni karakterl´ ancb´ ol, mag´ aba foglalja az alapt´ıpusokat (Bool, Char, String, Int, Integer, Float, Double, Lista, Tuple): read :: String -> a > read "False" :: Bool False > read "[10, 11, 12, 13]" :: [Int] [10, 11, 12, 13]
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Alaposzt´alyok
a Num azokat a t´ıpusokat tartalmazza, amelyeknek numerikus ´ert´ek¨ uk van mag´ aba foglalja az Eq ´es Show oszt´ alyokba tartoz´ o t´ıpusokat ´es a k¨ ovetkez˝ o alapt´ıpusokat (Int, Integer, Float, Double) (+) :: (-) :: (*) :: negate abs :: signum
a -> a -> a -> :: a a -> :: a
a -> a a -> a a -> a -> a a -> a
nem rendelkezik oszt´ asi oper´ atorral
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Alaposzt´alyok
az Integral mag´ aba foglalja a Num oszt´ alyokba tartoz´ o t´ıpusokat ´es azokat a t´ıpusokat is amelyeken eg´esz oszt´ as ´es marad´ekos oszt´ as v´egezhet˝ o (div) :: a -> a -> a (mod) :: a -> a -> a
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
Alaposzt´alyok
a Fractional mag´ aba foglalja a Num oszt´ alyokba tartoz´ o t´ıpusokat ´es azokat a t´ıpusokat is amelyeken val´ os oszt´ as ´es reciprok ´ert´ek hat´ arozhat´ o meg (/) :: a -> a -> a (recip) :: a -> a > recip 2.0 0.5
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
A standard Haskell oszt´alydiagramm
´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
A rendezett n-es (tuple) t´ıpus k¨ ul¨ onb¨ oz˝ o t´ıpus´ u elemek (´ert´ekek) halmaza. Jel¨ ol´es´ere a kerek z´ ar´ ojelt haszn´ aljuk: (), az elemek sz´ ama r¨ ogz´ıtett. > > > > > > > >
let my_tuple = ("Marika", 3, 8.75) let (nev, evf, jegy) = my_tuple print nev "Marika" print evf 3 print jegy 8.75
egy 2 elem˝ u tuple t´ıpuson alkalmazhat´ oak az fst ´es snd k¨ onyvt´ arf¨ uggv´enyek: > > > > >
let my_tuple1 = ("Marika", 8.75) fst my_tuple1 "Marika" snd my_tuple1 8.75 ´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
A tuple t´ıpus 12. feladat: m´ asodfok´ u egyenlet gy¨ okeinek a meghat´ aroz´ asa, az eredm´eny egy tuple t´ıpus gyok :: Double -> Double -> Double -> (String, Double, Double) gyok a b c = if delta < 0 then error "Komplex gyokok" else if delta == 0 then ("egyforma gyokok, ", x1, x1) else ("ket gyok", x1, x2) where x1 = (-b + sqrt delta) / nev x2 = (-b - sqrt delta) / nev delta = b * b - 4 * a * c nev = 2 * a > gyok 1 3 2 ("ket gyok",-1.0,-2.0) > gyok 1 4 4 ("egyforma gyokok, ",-2.0,-2.0) ´ MARTON Gy¨ ongyv´ er
2016, Funkcion´ alis programoz´ as
