Funktsionaalprogrammeerimine 2022/23 sügis

Kodutöö 1

Lahendamiseks loo näiteks fail K1.idr sellise sisuga:

Katsetamiseks ja testimiseks käivita käsurealt Idris loodud failiga samas kaustas: rlwrap 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.

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

1. Funktsioon sumInt

Kirjutage funktsioon sumInt, mis saades sisendiks naturaalarvu x tagastab x-st väiksemate või võrdsete arvude summa. (Vt. onspektis 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}$

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}$

Redutseerige avaldis fib 3.

3. Funktsioon modulo

Kirjutage jäägiga jagamise funktsioon modulo. (Vt. onspektis 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*}$

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)

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).

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}$

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}$

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}$

NB! Funktsioonid hanoi ja ack võivad negatiivsete argumentide korral minna lõpmatusse tsüklisse.

8. Liitmise ja korrutamise funktsioonid

Olgu antud sellised definitsioonid:

Kirjutage liitmise funktsioon add, mis kasutab ainult oma argumente ning funktsioone inc ja korda.

Kirjutage korrutamise funktsioon mul, mis kasutab ainult oma argumente, konstanti 0 ning funktsioone add ja korda.

9. Naiivne astendamise funktsioon

Kasutades rekursiooni, implementeeri naiivne astendamise funktsioon

kasutades eeskirja

$\operatorname{aste}(x,n) = \underbrace{x \cdot x \cdot \ldots \cdot x}_{n \text{ tegurit}}$.

Kasuta rekursiooni, mitte Idrisesse sisseehitatud astendamisoperaatoreid!

10. Kiire astendamise funktsioon

Implementeeri kiire astendamise funktsioon

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.

11. Naiivne jagamise funktsioon

Implementeeri naiivne jagamise funktsioon

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.