Teine Praktikum
Kõige "madalam" tase Haskellis on puhaste funktsioonide kirjutamine. Oskus kirjutada puhtaid rekursiivseid funktsioone on Haskelli alus --- teoorias polegi midagi rohkemat vaja. Selles praktikumis harjutame rekursiivseid funktsioone täisarvudel.
Näiteülesanded
sumInt
Kirjuta funktsioon sumInt, mis saades sisendiks naturaalarvu x tagastab x-st väiksemate või võrdsete arvude summa.
{$ \textsf{sumInt}(x) = \begin{cases} 0 & \text{kui }x = 0 \\ \textsf{sumInt}(x-1)+ x & \text{muidu } \end{cases} $}
sumInt :: Int -> Int sumInt n = undefined
Redutseeri avaldis sumInt 3.
fib
Kirjuta funktsioon fib, mis leiab n-da Fibonacci arvu.
{$ \textsf{fib}(x) = \begin{cases} 0 & \text{kui }x = 0\\ 1 & \text{kui }x = 1\\ \textsf{fib}(x-1) + \textsf{fib}(x-2) & \text{muidu } \end{cases} $}
fib :: Int -> Int fib n = undefined
Redutseeri avaldis fib 3.
modulo
Kirjutada jäägiga jagamise funktsioon modulo.
{$
\begin{align*}
\textsf{modulo}(x,y) =&{}\; f(x)
&{} \text{kus}
\quad f(n) =
\begin{cases}
n & \text{kui }n < y\\
f(n-y)& \text{muidu}
\end{cases}
\end{align*}
$}
modulo :: Int -> Int -> Int modulo x y = undefined
Redutseeri avaldis modulo 5 2.
Harjutusülesanded
Ülesanne 1
Kirjuta funktsioon syt, mis leiab suurima ühisteguri läbi Eukleidese algoritmi.
{$
\textsf{syt}(x,y) =
\begin{cases}
x & \text{kui }y = 0 \\
\textsf{syt}(y,\textsf{mod}\;x\;y) & \text{muidu }
\end{cases}
$}
kus mod on Haskelli jagamise jäägi operaator (või eelnevalt defineeritud modulo)
syt :: Int -> Int -> Int syt x y = undefined
Redutseeri avaldis syt 12 8.
Ülesanne 2
Kirjutada McCarthy ??-funktsioon, kus ?? asemel on üks arv. Testida funktsiooni sisenditega 0-i ja 100 vahel. Mis arv see on?
{$ \textsf{mc}(x) = \begin{cases} x-10 & \text{kui }x > 100\\ \textsf{mc}(\textsf{mc}(x+11)) & \text{muidu } \end{cases} $}
mc :: Int -> Int mc n = undefined
Ülesanne 3
Kirjutada Hanoi funktsioon.
{$ \textsf{hanoi}(n) = \begin{cases} 1 & \text{kui }n = 1\\ 2*\textsf{hanoi}(n-1)+1 & \text{kui }n > 1 \\ \end{cases} $}
hanoi :: Int -> Int hanoi n = undefined
Ülesanne 4
Kirjutada Ackermanni funktsioon.
{$ A(m,n) = \begin{cases} n+1 & \text{kui }m = 0\\ A(m-1,1) & \text{kui }m > 0 \text{ ja } n = 0\\ A(m-1,A(m,n-1)) & \text{muidu } \end{cases} $}
ack :: Int -> Int -> Int ack m n = undefined
Ülesanne 5
Kirjutage Programmeerimiskeelte kursuse hinde arvutamise funktsioon, nii et
hinne hb sb kodu loeng eks arvutaks välja hinde tähena (A, B, ..., F),
- `hb' on Haskelli baastesi punktid
- `sb' on Scala baastesi punktid
- `kodu' on kodutööde punktid
- `loeng' on loengutestide punktid
- `eks' on eksami punktid
hinne :: Int -> Int -> Int -> Int -> Int -> Char hinne = undefined
Ülesanded*
Olgu antud sellised definitsioonid:
korda :: Int -> (Int -> Int) -> Int -> Int korda 0 f x = x korda n f x = f (korda (n-1) f x) inc :: Int -> Int inc x = x + 1
Kirjutada liitmise funktsioon add, mis
kasutavb ainult oma argumente ning funktsioone inc ja korda.
add :: Int -> Int -> Int add x y = undefined
Kirjutada korrutamise funktsioon mul, mis
kasutavb ainult oma argumente, konstanti 0 ning funktsioone add ja korda.
mul :: Int -> Int -> Int mul x y = undefined
Lahendada ülesanded 2 ja 3 kasutades püsipunktioperaatorit
fixedPt f = g where g = f g
hanoi' :: Int -> Int
hanoi' = fixedPt h
where h = undefined
fixedPt f = g where g = f g
mc' :: Int -> Int
mc' = fixedPt h
where h = undefined
fixedPt f = g where g = f g
{$ $}