Funktsionaalprogrammeerimine 2026/27 sügis

Kodutöö 1

Lahendamiseks loo fail K1.idr sellise sisuga:

module K1

-- kirjutage funktsioonid siia

Katsetamiseks ja testimiseks käivita käsurealt Idris loodud failiga samas kaustas: rlwrap idris2 K1.idr. (Kui teil rlwrap-i ei ole, siis lihtsalt idris2 K1.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.

Konspekt

Lisalugemine (vabatahtlik):

Type-Driven development with Idris peatükid:

• 1. Introduction, alampeatükid:
  • 1.4. A quick tour of Idris
    • 1.4.1. The interactive environment
    • 1.4.2. Checking types
    • 1.4.3. Compiling and running Idris programs
    • 1.4.4. Incomplete definitions: working with holes
    • 1.4.5. First-class types
• Chapter 2. Getting started with Idris, alampeatükid:
  • 2.1. Basic types
    • 2.1.1. Numeric types and values
    • 2.1.3. Characters and strings
    • 2.1.4. Booleans
  • 2.2. Functions: the building blocks of Idris programs, sissejuhatus ja alampeatükid:
    • 2.2.1. Function types and definitions
    • 2.2.7. Local definitions: let and where

Praktikumi ja kodutöö ülesanded

Funktsioon sumInt

Kirjutage funktsioon sumInt, mis saades sisendiks naturaalarvu x tagastab x-st väiksemate või võrdsete arvude summa. (Vt. konspektis Baasväärtused ja tüübid peatükk Funktsioonid)

{$ \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

Praktikumis, redutseerige avaldis sumInt 3.

Oma koodi testimiseks kopeerige oma kood Moodle-sse ja käivitage (Evaluate-nupuga) automaatkontroll. Moodle süsteem kontrollib vaid, kas sumInt 1 == 1 ja kas sumInt 5 == 15 tagastavad True. Aga pane tähele, et sinu praksijuhendaja vaatab lahenduse üle ja täiendab vajadusel hinnangut.

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

Praktikumis, redutseerige avaldis fib 3.

Funktsioon modulo

Kirjutage jäägiga jagamise funktsioon modulo. (Vt. konspektis Baasväärtused ja tüübid peatükk Lokaalsed funktsioonid: let ja where)

{$ \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

Praktikumis, redutseerige avaldis modulo 5 2.

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

Praktikumis, redutseerige avaldis syt 12 8.

NB! Kui matemaatiline süntaks on {$\textsf{syt}(y,\textsf{mod}(x,y))$}, siis Idrise süntaks samaväärsele avaldisele on syt y (mod x y).

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

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. Te ei pea selle pärast muretsema.

Naiivne astendamise funktsioon

Kasutades rekursiooni, 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!

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.

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.

Liitmise ja korrutamise funktsioonid

Pane tähele! Käesolev ülesanne on toodud siia motivatsiooniks, et näidata funktsionaalse programeerimise peamist võlu: saame arvutada funktsioonidega samamoodi nagu muude andmetega.

Üldiselt on need keerukad teemad, mida vaatame alles mõnes hilisemas loengus.

Antud ülesande teeb litsamaks asjaolu, et meil on piiratud arv (s.t. väga vähe) komponente, mida omavahel kombineerida.

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

Implementeeri mittenegatiivsete täisarvude liitmise funktsioon add, kirjutades augu ?rhs_add asemel vajalik avaldis. Vaja on kobineerida argumente x ja y, sulge ning funktsioone inc ja korda.

add : Int -> Int -> Int
add x y = ?rhs_add

Implementeeri mittenegatiivsete täisarvude korrutamise funktsioon mul, kirjutades augu ?rhs_mul asemel vajalik avaldis. Vaja on kobineerida argumente x ja y, sulge ning funktsioone add ja korda.

mul : Int -> Int -> Int
mul x y = ?rhs_mul

Lisaülesanded

Lisaülesannete lahendamine on vabatahtlik. Lisaülesanded on lahendamiseks neile, kes on oma oskustes ebakindlad ja tahavad veel harjutada --- need ei sisalda uut materjali ega vaja erilisi oskusi. Lisaülesanded on raskuse poolest sarnased tavalistele kodutöö ülesannetele.

(Järgmises kodutöös on ka tärnülesanded, mis on keerukamad vabatahtlikud ülesanded. Nood on mõeldud pakkuma väljakutset tublimatele tudengitele.)

McCarthy funktsioon

Kirjutage McCarthy ??-funktsioon, kus ?? asemel on üks konkreetne 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

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!