Arvutiteaduse instituut
  1. Kursused
  2. 2021/22 sügis
  3. Funktsionaalprogrammeerimine (LTAT.03.019)
EN
Logi sisse

Funktsionaalprogrammeerimine 2021/22 sügis

  • Üldinfo
    • Õppekorraldus
  • Loengud ja Praksid
    • Installimine
    • 1. Praktikum
    • 2. Praktikum
    • 3. Praktikum
    • 4. Praktikum
    • 5. Praktikum
    • 6. - 7. Praktikum
    • 9. Praktikum
    • 10. Praktikum
    • 11. Praktikum
    • 12. Praktikum
    • 13. Praktikum
    • Projektid
  • Moodle
  • Fleep

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:
    • 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.

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

  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo