Kihagyás

22 - Funkcionális programozás

Lusta vs modó kiértékelés

Szükséges fogalmak:

  • strict semantics
  • call-by-name
    • A kiértékelés az argumentum hivatkozásakor történik
    • Ha az argumentumok sehol nem olvassa ahívó fél, nem kerül kiértékelésre
    • Ha az argomentum értékét több helyen is használja a hívó fél, minden alkalommal kiértékelődik
  • sharing
    • Írható/olvasható referencia átadása a hívó félnek

Mohó kiértékelés

Implementációja a szigorú szemantikának, imperatív programozási nyelveknél megszokott.

Minden hívási helyen az argumentum kiértékelésre kerül.

A viselkedés a call-by-value stratégiára hasonlít, mivel minden értéket először meg kell szerezni a függvéníy meghívása előtt.

A függvény értéke definíció szerint undefined, ha valamelyik paramétere undefined.

Szigorú szemantika: egy undefined paraméter undefined függvény eredményt okoz még akkor is, ha a függvény nem használja fel a paramétert kiértékeléskor

Lusta kiértékelés

Másnéven call-by-need, ami gyakorlatilag call-by-name és sharing keveréke. Az argumentum csak annak felhasználásakor kerül kiértékelésre, viszont egy tisztán funkcionális környezetben minden érték nem módosítható, így az egyszeri kiszámolás után a referencia megosztható a többi meghívási helyen is.

Ez továbbra is megengedi azt, hogy a nem használt argumentumokat sosem értékelünk ki, valamint azon nyelvek sebességét is elérjük, amik a call-by-reference alapján minden hivatkozást megosztanak egymással, megőrizve a konzisztenciát a tiszta funkcionalitás által.

Szigorú szemantikával ellentétben ha az undefined paramétereit a függvény nem használja fel kiértékeléskor, a függvény annak értékével helyesen visszatér.

Hivatkozási helyfüggetlenség

Az azonos kifejezések értéke mindig ugyanaz

Statikus típusozottság

A kifejezések típusa fordítási időben ismert

Curry-féle elv

Egy, több paramétert váró függvény átalakítása egy olyan függvénnyé, ami az első paraméter alapján egy másik függvényt ad vissza, aminek szintén csak egy függvényre van szüksége

f :: (a, b, c) -> d
-- Curry átalakítással
g :: a -> b -> c -> d
-- Zárójellel
g :: a -> (b -> (c -> d))

??? title="Prelude" A Haskell Prelude ajánl erre függvényt 

f = curry g
g = uncurry f

Haskell-ben minden függvény curry-zettnek értelmezett, ezen gondolatmenet engedi meg a parciális függvényalkalmazást, ahol a függvény alkalmazásának 'részeredménye' tovább adható, mint egy már kevesebb paramétert váró függvény.

margó szabály

Indentáció-érzékeny nyelveknél (mint amilyen Haskell is) a kódblokkok egymástól megkülönböztetése a konzisztens beljebbhúzásokkal történik.

A margó szabály (off-side rule) másik megnevezése a szignifikáns behúzás (significant indentation)

alaptípusok

  • Int
  • Integer
  • Float
  • Double
  • Bool
  • Char
  • String
  • [a]

konverziók

  • fromIntegral :: (Integral a, Num b) => a -> b
    • Átalakít bármilyen Integral-ból (like Int, Integer) bármilyen Num-ra, amit ki tud inferálni
  • round, floor, ceiling, truncate
    • ((RealFrac a, Integral b) => a -> b)
    • hasonlóan, mint a fromIntegral
  • toInteger :: Intergral a => a -> Integer
  • toRational :: Real a => a -> Rational
  • realToFrac :: (Real a, Fractional b) => a -> b
    • hasonlóan, mint a fromIntegral
  • show :: Shkow a => a -> String
  • words :: String -> [String] / unwords :: [String] -> String
  • lines / unlines
    • Ugyanaz mint a words csak sortöréssel
  • ord :: Char -> Int
    • (Unicode code-point)
  • chr :: Int -> Char
  • digitToInt
    • számjegy karakteréből Int-et csinál
    • Data.Char

függvények definiálása és típusozása

név :: (Megkötés a, Megkötés b ...) => Paraméter1 -> Paraméter2 ...

név a b ... = f a ...

Példa

numberSeven :: Int
numberSeven = 7

const7 :: Int -> Int
const7 _ = 7

id :: a -> a
id a = a

Tekintve, hogy Haskell képes egy szintig a típust inferálni, így egyes esetekben a függvény típusának megadása kihagyható

Totális függvények

Azon függvények, amik minden lehetséges bemenetre megoldással szolgálnak

Parciális függvények

Azon függvények, amik nem minden esetben szolgálnak eredménnyel, potenciális hibalehetőséggel (a szándékosan hibát dobó függvények is parciálisnak minősülnek, hiszen a Haskell-nem nincs hibakezelés)

Mintaillesztés

A függvény paraméterei mintákra illeszthetőek, és ha a minta illeszkedik, akkor a paraméterek értéke a minta megfelelő helyére kerül.

f :: (a, b) -> a
f (0, 0) = 0
f (0, y) = y
f (x, 0) = x
f (x, y) = x + y

A minták kiértékelése mindig felülről lefelé történik, tehát a legelső minta, ami illeszkedik a paraméterekre kerül kiértékelésre.

Ha egy minta sem illeszkedik, akkor a program futásidejű hibát dob. (totális vs. parciális függvény)

!!! title="EA"

Egy függvényt több alternatívával (vagy szabállyal) is definiálhatunk. A függvényalternatíváknak egymás mellett kell elhelyezkedni a modulban.

A függvényparaméterek helyén minták vannak. A minta fogalmával a következő diákon ismerkedünk meg.

A függvényalternatívákat a kiértékelés során fentről lefelé próbáljuk végig.

Minta lehet:

- Változó: `x, xs, a, ...`
- Joker: `_`
- Típus specifikus minták: `True, 0, (a, b), ...`

őrfeltételek, esetszétválasztás

A mintaillesztés mellett a függvények paraméterei őrfeltételekkel is kiegészíthetőek, amik a mintaillesztés után kerülnek kiértékelésre.

\[\min(x,y)=\begin{cases} x &\text{ha } x \le y \\ y &\text{egyébként} \end{cases}\]
min x y
    | x <= y    =  x
    | otherwise =  y

f :: (Integral a) => a -> a
f 0 = 0
f x | x < 0 = -x
    | otherwise = x

Minden őrfeltétel egy Bool értékre kell kiértékelődjön, amely ha True-t ad vissza, akkor a kód belép azon ágba. Az otherwise kulcsszó a True értéket adja vissza, így a legutolsó őrfeltétel mindig igaz lesz, ha az előzőek nem teljesültek.

rekurzió

Egy rekurzív függvény egy olyan függvény, ami a saját magát hívja meg.

A rekurzív függvényeknek jobb esetben van egy bázis esete, ami megállítja a rekurziót, és egy rekurzív eset, ami a bázis esetet hívja meg.

fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n - 1)

Amennyiben a bázis eset nem teljesül, a rekurzív eset hívja meg önmagát, amíg el nem érjük a bázis esetet.

Ha a rekurzív függvény nem tartalmazn bázis esetet, akkor a program verem túlcsordulással álhat meg, mivel a rekurzió sosem áll meg.

lokális definíciók

where és let .. in lehetőséget ad csak egy függvény kontextusában egy névtelen függvényt létrehozni, ami nem hívható meg máshol.

Hasznos segédfüggvények és accumulator-ok definiálására.

reverse'' :: [a] -> [a]
reverse'' [] = []
reverse'' xs = reverseAcc xs []
    where
        reverseAcc [] acc = acc
        reverseAcc (y:ys) acc = reverseAcc ys (y:acc)

reverse''' :: [a] -> [a]
reverse''' [] = []
reverse''' xs =
    let
        reverseAcc [] acc = acc
        reverseAcc (y:ys) acc = reverseAcc ys (y:acc)
    in
        reverseAcc xs []

magasabbrendű függvények

Azt mondjuk, hogy egy függvény magasabbrendű, ha: - egy másik függvényt vár paraméterül - egy másik függvényt ad vissza

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

Itt a f függvény egy másik függvényt vár paraméterül, és egy listát ad vissza, aminek minden eleme a bemeneti lista megfelelő elemének a g függvénnyel való kiértékelése.

Példák magasabbrendű függvényekre a Haskell Prelude-ben: - map - map :: (a -> b) -> [a] -> [b] - A bemeneti lista minden elemére alkalmazza a megadott függvényt - filter - filter :: (a -> Bool) -> [a] -> [a] - A bemeneti lista minden elemére alkalmazza a megadott függvényt, és csak azokat adja vissza, amik True-t adnak vissza

névtelen függvények

A névtelen függvények (lambda függvények) olyan függvények, amiknek nincs neve, és csak egyszer használatosak.

A Haskell-ben a \ karakterrel kezdődnek, és a paraméterek után egy -> karakter következik, ami a függvény törzsét jelöli.

f :: Num a => a -> a
f alma = alma * 2

f' = (\alma -> alma * 2) -- u.a. mint az `f`

függvénykompozíció

  • (.) :: (b -> c) -> (a -> b) -> a -> c
    • Visszaad egy olyan függvényt, ami a bemeneti két függvényt egymás után fogja alkalmazni a paraméterre
    • Magasabbrenddű fügvényeknél hasznos használni
f (g x) == (f . g) x

halmazkifejezések (list comprehensions)

Matematikai alak: \(\left{n^2\,|\, n\in \mathbb{N}\,|\,\text{n páros}\right\}\)

A Haskell-ben a listák halmazkifejezésekkel is definiálhatóak, amik a matematikai halmazkifejezésekhez hasonlítanak.

[x | x <- [1..10], x `mod` 2 == 0]

A fenti példa egy listát ad vissza, aminek minden eleme a [1..10] lista páros elemei. A | karakter után a lista elemeinek generálására szolgáló kifejezés található, ami a x <- [1..10] részben található. A , karakter után található kifejezés a szűrő, ami a lista elemeit szűri. A fenti példa a [2, 4, 6, 8, 10] listát adja vissza.

típusosztályok

A típusosztály lényegében metódusok halmaza, és minden típus, ami egy típusosztályból származik, garantálja, hogy a benne foglalt metódusokat definiálta.

Legegyszerűbb példa a Num típusosztály, ami felett (többek között) az összeadás (+) és kivonás (-) művelete értelmezett, így annak minden leszármazottjáról tudjuk, hogy annak elemei össze adhatóak (Int, Integer, ...)

??? title="Az Ord típusosztály definíciója" 

class Eq a => Ord a where
    (<), (<=), (>=), (>) :: a -> a -> Bool
    x <= y   =  x < y || x == y
    x <  y   =  not (x >= y)
    x >= y   =  x > y || x == y
    x >  y   =  not (x <= y)
Az összehasonlításkor feltételezzük, hogy már van egyenlőségvizsgálat.

Ord alosztálya az Eq osztálynak
Eq ősosztálya az Ord osztálynak

??? title="deriving" Az Eq, Ord, Enum, Show, Read példányosítása rábízható a fordítóra. Ezt az igényünket az adattípus definíciójánál a deriving kulcsszóval kell jeleznünk:

```hs
data Maybe a
    = Nothing
    | Just a
        deriving (Eq, Ord, Show, Read)
```

parametrikus (paraméteres) és ad-hoc polimorfizmus

Parametrikus polimorfizmus

A függvény a megadott típus sajátosságait nem használja fel, általánosan működik a legtöbb típussal

reverse :: [a] -> [a]

Ad-hoc polimorfizmus

A függvényt a típusosztály várja el, viselkedése eltérhet típusok között

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

típusszinonimák

Típusszinonimák segítségével új típusokat hozhatunk létre, amik a már meglévő típusok aliasai.

type Szam = Int
type Lista a = [a]

Crazy shit.

algebrai adattípusok definiálása

sum type:

data Bool = True | False

product type:

data (,) a b = (,) a b

ADT:

data Point = Point
  { x :: Double
  , y :: Double
  }
  deriving (Show, Eq)

data Point = Point2D Double Double | Point3D Double Double Double
  deriving (Show, Eq)