Functional Programming 2024/25 fall

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

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

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

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

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.

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

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

Lisaülesanded

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

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!