1. Praktikum
Lahendamiseks loo näiteks fail P1.idr sellise sisuga:
module P1 -- kirjutage funktsioonid siia
Katsetamiseks ja testimiseks käivita käsurealt Idris loodud failiga samas kaustas: rlwrap idris2 P1.idr. Failis defineeritud funktsioone saad käivitada Idrise süntaksiga, nt sumInt 10. Kui muudad ja salvestad faili, siis võid anda spetsiaalse käsu :r, et fail uuesti laadida, ilma et peaks iga muudatuse järel Idrise sulgema ja taaskäivitama. Idrise sulgemiseks käsureal kasuta käsku :q.
Lisalugemine (vabatahtlik):
Type-Driven development with Idris peatükid:
- 1. Introduction, alampeatükid:
- Chapter 2. Getting started with Idris, alampeatükid:
Praktikumi ja kodutöö ülesanded
1. Funktsioon sumInt
Kirjutage 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 = ?rhs_sumInt
Redutseerige avaldis sumInt 3.
2. Funktsioon fib
Kirjutage 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 = ?rhs_fib
Redutseerige avaldis fib 3.
3. Funktsioon modulo
Kirjutage 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 = ?rhs_modulo
Redutseerige avaldis modulo 5 2.
4. Funktsioon syt
Kirjutage 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 Idrise jagamise jäägi operaator (või eelnevalt defineeritud modulo)
syt : Int -> Int -> Int syt x y = ?rhs_syt
Redutseerige avaldis syt 12 8.
5. McCarthy funktsioon
Kirjutage McCarthy ??-funktsioon, kus ?? asemel on üks arv. Testige 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 = ?rhs_mc
6. Hanoi funktsioon
Kirjutaga 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 = ?rhs_hanoi
7. Ackermanni funktsioon
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 = ?rhs_ack
NB! Funktsioonid hanoi ja ack võivad negatiivsete argumentide korral minna lõpmatusse tsüklisse.
8. Liitmise ja korrutamise funktsioonid
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
Kirjutage liitmise funktsioon add, mis
kasutab ainult oma argumente ning funktsioone inc ja korda.
add : Int -> Int -> Int add x y = ?rhs_add
Kirjutage korrutamise funktsioon mul, mis
kasutab ainult oma argumente, konstanti 0 ning funktsioone add ja korda.
mul : Int -> Int -> Int mul x y = ?rhs_mul
9. Naiivne astendamise funktsioon
Implementeeri naiivne astendamise funktsioon
aste : Int -> Int -> Int aste x n = ?rhs_aste
kasutades eeskirja
{$\operatorname{aste}(x,n) = \underbrace{x \cdot x \cdot \ldots \cdot x}_{n \text{ tegurit}} $}.
Kasuta rekursiooni, mitte Idrisesse sisseehitatud astendamisoperaatoreid!
10. Permutatsioonide arvu funktsioon
Implementeeri permutatsioonide arvu funktsioon
p : Int -> Int -> Int p n k = ?rhs_p
kasutades eeskirja
{$\operatorname{p}(n,k) = \underbrace{n \cdot (n-1) \cdot \ldots \cdot (n-(k-1))}_{k \text{ tegurit}} $}
Kasuta vahetut rekursiooni, mitte faktoriaali!
Rekursiooni väljamõtlemisel võid inspiratsiooni saada 6. ülesande lahendusest.
11. Kombinatsioonide arvu funktsioon
Implementeeri kombinatsioonide arvu funktsioon
c : Int -> Int -> Int c n k = ?rhs_c
kasutades eeskirja
{$\operatorname{c}(n,k) = \binom{n}{k}, $} kus binoomkordaja avaldub reeglitega:
- {$\binom{n}{0} = \binom{n}{n} = 1$},
- {$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, \quad\text{kui $1\leq{}k\leq n-1$ } $}.
Kasuta antud binoomkordaja rekursioonireegleid, mitte faktoriaali!
12. Kiire astendamise funktsioon
Implementeeri kiire astendamise funktsioon
qaste : Int -> Int -> Int qaste x n = ?rhs_qaste
kasutades eeskirja
{$\begin{align*} \operatorname{qaste}(x,n) = &{} \begin{cases} 1 & \text{kui } n = 0 \\ y \cdot y & \text{kui } n \;\texttt{`mod`}\; 2 == 0 \\ x \cdot y \cdot y & \text{muidu} \end{cases}\\ &\text{kus} \quad y = \operatorname{qaste}(x, n \;\texttt{`div`}\; 2). \end{align*} $}.
Trükimasina kirjas operaatorid `mod` ja `div` kirjuta/kopeeri täpselt nii rõhumärkide (backtick) vahel, et seda funktsiooni kasutada binaarse operaatorina.
Defineeri abimuutuja y kasutades where või let konstruktsiooni.
13. Naiivne jagamise funktsioon
Implementeeri naiivne jagamise funktsioon
ndiv : Int -> Int -> Int ndiv x y = ?rhs_ndiv
kasutades eeskirja
{$\begin{align*} \operatorname{ndiv}(x,y) ={} &{} f(x,0)\\ &{} \text{kus} \quad f(n,z) = \begin{cases} z & \text{kui }n < y\\ f(n-y,z+1)& \text{muidu} \end{cases} \end{align*}$}.
Defineeri abifunktsioon f kasutades where või let konstruktsiooni.