Funktsionaalprogrammeerimine 2025/26 sügis

Liidesed & IO

Selles praktikumis tegeleme liideste ja sisendi-väljundiga.

Lisalugemine:

Type-Driven development with Idris peatükid:

• Chapter 7. Interfaces: using constrained generic types, sissejuhatus ja alampeatükid:
  • 7.1. Generic comparisons with Eq and Ord
    • 7.1.1. Testing for equality with Eq
    • 7.1.2. Defining the Eq constraint using interfaces and implementations
    • 7.1.3. Default method definitions
    • 7.1.4. Constrained implementations
    • 7.1.5. Constrained interfaces: defining orderings with Ord
• Chapter 1. Overview, alampeatükk:
  • 1.3.2. Side-effecting programs
• Chapter 5. Interactive programs: input and output processing, sissejuhatus ja alampeatükid:
  • 5.1. Interactive programming with IO
    • 5.1.1. Evaluating and executing interactive programs
    • 5.1.2. Actions and sequencing: the >>= operator
    • 5.1.3. Syntactic sugar for sequencing with do notation
  • 5.2. Interactive programs and control flow
    • 5.2.1. Producing pure values in interactive definitions

Praktikumi ja kodutöö ülesanded

Kahendpuud

1. map-i liides

Kirjuta Functor liidese instants Tree tüübile.

data Tree a = Leaf | Branch (Tree a) a (Tree a)

Eq a => Eq (Tree a) where
  Leaf == Leaf = True
  (Branch x y z) == (Branch w v s) =  x==w && y==v && z==s
  _ == _ = False

Functor Tree where
  map f t = ?rhs_map

Näiteks:

map (+10) (Branch Leaf 5 Leaf) == (Branch Leaf 15 Leaf)
map (+10) (Branch (Branch Leaf 4 Leaf) 3 (Branch Leaf 5 Leaf)) == (Branch (Branch Leaf 14 Leaf) 13 (Branch Leaf 15 Leaf))

2. fold-i liides

Kirjuta Foldable liidese instants Tree tüübile foldr kaudu. Pane tähele, et tegemist pole Tree andmestruktuuri "loomuliku" foldiga, vaid listi-foldr-ga.

Foldable Tree where
  foldr f b t = ?rhs_foldr

Veendu, et nüüd saab meie puudel muuhulgas kasutada toList funktsiooni, mis peaks käituma nagu eelmise praktikumi tree2list.

Näiteks:

toList Leaf == []
toList (Branch Leaf 5 Leaf) == [5]
toList (Branch (Branch Leaf 3 Leaf) 5 (Branch Leaf 7 Leaf)) == [3, 5, 7]

3. Üldine pikkus

Kirjuta len funktsioon, millega saab arvutada nii listi pikkust kui ka puu suurust.

len : Foldable t => t a -> Int

Näiteks:

len [1,2,3] == 3
len (Branch Leaf 5 Leaf) == 1

Ratsionaalarvud

NB! Tüübi Nat kasutamiseks lisa faili algusesse import Data.Nat.

Järgnevalt on defineeritud positiivsete ratsionaalarvude tüüp Rat ning näiteks ka ratsionaalarvude normaliseerimise funktsioon norm. Lisaks on skitseeritud mõned operatsioonid ratsionaalarvudel ning näitena väärtused pool ja neljandik.

infix 7 :/:
data Rat = (:/:) Nat Nat

-- normaliseerimine
norm : Rat -> Rat
norm (_   :/:   0) = 0 :/: 0
norm (0   :/:   _) = 0 :/: 1
norm (S a :/: S b) =
    let n = gcd (S a) (S b) in
    (S a) `div` n :/: (S b) `div` n

-- muud operatsioonid:
-- (a :/: b) == (c :/: d) = a*d == b*c
-- (a :/: b) +  (c :/: d) = a*d + b*c :/: b*d
-- (a :/: b) *  (c :/: d) = a*c :/: b*d 
-- (a :/: b) /  (c :/: d) = a*d :/: b*c 
-- pöörd (a :/: b) = b :/: a

neljandik : Rat
neljandik = 1 :/: 4

pool : Rat
pool = 1 :/: 2

4. Eq liides

Defineerige Eq liides ratsionaalarvudele.

1 :/: 2 == pool
2 :/: 4 == pool

5. Num liides

Defineerige Num liides ratsionaalarvudele.

pool + pool == 1
2 * pool == 1
pool * pool == neljandik

6. Fractional liides

Defineerige Fractional liides ratsionaalarvudele.

pool / pool == 1
2 / pool == 4
recip pool == 2

recip on lühend sõnast reciprocal, inglise keeles pöördväärtus.

7. Ord liides ratsionaalarvudele

Defineerige Ord liides ratsionaalarvudele.

compare (1:/:2) (1:/:3) == GT
compare (1:/:4) (1:/:3) == LT
compare (3:/:3) (2:/:2) == EQ

8. Monus liides

Naturaalarvudel ei saa defineerida tavalist lahutamist aga saab defineerida monus operaatori.

infixl 8 -.
interface Monus t where
  (-.) : t -> t -> t

Esmalt, defineerige Monus liides arvudele millel on minus ja pöördväärtus (Neg).

Neg a => Monus a where
  x -. y = ?rhs_monus_neg

0.5 -. 0.3 == 0.2
5 -. 3 == 2
3 -. 5 == -2

9. Monus liides naturaalarvudele

Nüüd, defineerige Monus liides naturaalarvudele.

S (S Z) -. S Z == S Z
S (S Z) -. S (S Z) == Z
S (S Z) -. S (S (S Z)) == Z

10. Monus liides ratsionaalarvudele

Nüüd, defineerige Monus liides ratsionaalarvudele.

(1 :/: 3)  -. (1 :/: 6)  ==  (1 :/: 6)
(1 :/: 6)  -. (1 :/: 3)  ==  (0 :/: 1)
(1 :/: 2)  -. (1 :/: 3)  ==  (1 :/: 6)

Do-notatsioon ja Sisend-väljund

11. Protseduur t2ring

Kirjuta protseduur t2ring, mis trükib konsooli juhusliku arvu ühest kuueni. Soovitatav on kasutada mooduli System.Random funktsiooni randomRIO mille tüüp on lihtsustatult Random a => (a, a) -> IO a.

t2ring : IO ()
t2ring = ?rhs_t2ring

NB! Miskipärast on Idrises Random defineeritud vaid Int32 täisarvutüübi jaoks. (vihje: the)

REPLis do-notatsiooni kasutava funktsiooni jooksutamiseks kirjuta funktsiooni kutse ette :exec

12. Protseduur dialoog

Kirjuta protseduur dialoog, mis küsib kasutajalt nime ja tervitab teda sellega.

dialoog : IO ()
dialoog = ?rhs_dialoog

13. Listi trükk

Kirjuta funktsioon, mis prindib talle argumendina antud arvude listi. Iga prinditav arv peab tulema eraldi reale. Näiteks:

> :exec prindiArvud [1,66,99]
1
66
99

prindiArvud : List Int32 -> IO ()
prindiArvud xs = ?rhs_prindiArvud

14. Nimekirja trükkimine

Nüüd kirjutame sõnede trükkimise funktsiooni, mis trükib järjest iga listis (teine argument) oleva sõne. Iga rea alguses peab olema järgmine täpipunkt (bullet point) esimesest argumendist.

trükiNimekiri : Stream String -> List String -> IO ()
trükiNimekiri = ?rhs_trükiNimekiri

tärnid : Stream String
tärnid = "*" :: tärnid

pannkoogid : List String
pannkoogid = ["3 muna", "30g suhkrut", "100g nisujahu","250g piima", "20g võid", "näpuotsaga soola"]

> :exec trükiNimekiri tärnid pannkoogid
* 3 muna
* 30g suhkrut
* 100g nisujahu
* 250g piima
* 20g võid
* näpuotsaga soola

15. Nimekirja numereerimine

Nüüd defineeri arvud nii, et tulemus klapiks näitega all.

arvud : Stream String
arvud = ?rhs_arvud

> :exec trükiNimekiri arvud pannkoogid
1. 3 muna
2. 30g suhkrut
3. 100g nisujahu
4. 250g piima
5. 20g võid
6. näpuotsaga soola

16. Arvude sisetamine

Kirjuta protseduur, mis esmalt küsib kasutajalt naturaalarvu. Kui kasutaja sisestab midagi, mis pole Int32 tüübi sisse mahtuv naturaalarv, tuleb veast teatada ning uuesti arvu küsida. Protseduur tagastab edukalt sisestatud arvu.

readMaybe : IO (Maybe Int32)
readMaybe = do
  input <- getLine
  if all isDigit (unpack input)
    then pure (Just (cast input))
    else pure Nothing

loeArv : IO Int32
loeArv = ?rhs_loeArv

Näide:

> :exec loeArv
Sisesta arv:
ei sisesta
Viga! Ei tunne sellist arvu!
Sisesta arv:
10

17. Kahe arvu summa

Kirjuta protseduur, mis küsib kasutajalt kaks naturaalarvu ning trükib nende summa.

summa2 : IO ()
summa2 = ?rhs_summa2

Näide:

> :exec summa2
Sisesta arv:
20
Sisesta arv:
6
26

Lisaülesanded

(Valikuliselt tehtavad ülesanded, mis on sarnase keerukusega kui kodutöö ülesanded.)

18. Arvude summa

Kirjuta protseduur, mis esmalt küsib arvu n, seejärel loeb n naturaalarvu ning lõpuks trükib viimati loetud n arvu summa. Proovige lahendada seda lihtrekursiooniga kui ka kasutades näiteks sequence funktsiooni.

Lihtsustatult, võtab sequence : List (IO a) -> IO (List a) listi arvutusi ja teeb need järjest ning tagastab listi tulemustega. Sarnaselt töötab ka traverse : (a -> IO b) -> List a -> IO (List b).

summaN1 : IO ()
summaN1 = ?rhs_summaN1

summaN2 : IO ()
summaN2 = ?rhs_summaN2

Näide:

> :exec summaN1
Mitu liidetavat? Sisesta arv:
3
Sisesta arv:
1
Sisesta arv:
2
Sisesta arv:
3
6
> :exec summaN2
Mitu liidetavat? Sisesta arv:
2
Sisesta arv:
9
Sisesta arv:
8
17

19. Range liides ratsionaalarvudele

Nüüd, defineerige Range liides ratsionaalarvudele.

[1:/:1 .. 5] == [(1 :/: 1), (2 :/: 1), (3 :/: 1), (4 :/: 1), (5 :/: 1)]
[1:/:2 .. 5:/:1] == [(1 :/: 2), (3 :/: 2), (5 :/: 2), (7 :/: 2), (9 :/: 2)]

[0, 1:/:2 .. 2] == [(0 :/: 1), (1 :/: 2), (1 :/: 1), (3 :/: 2), (2 :/: 1)]
[0, 1:/:8 .. 1] == [(0 :/: 1), (1 :/: 8), (1 :/: 4), (3 :/: 8), (1 :/: 2), (5 :/: 8), (3 :/: 4), (7 :/: 8), (1 :/: 1)]

take 5 [0:/:1..] == [(0 :/: 1), (1 :/: 1), (2 :/: 1), (3 :/: 1), (4 :/: 1)]
take 5 [0:/:1, 1:/:3 ..] == [(0 :/: 1), (1 :/: 3), (2 :/: 3), (1 :/: 1), (4 :/: 3)]

Tärnülesanded

(Valikuliselt tehtavad ülesanded, mis on keerulisemad/raskemad kui kodutöö ülesanded.)

Traversable liides

Tahame arvutada kõik variandid puudest, kus puu olevatest väärtustest võidakse võtta vastandarv.

Kui puude asemel võtta listid, saame seda lahendada traverse funktsiooniga nii:

variandidList : List Int -> List (List Int)
variandidList = traverse (\ x => [x,-x])

Et selline kood töötaks puude puhul, tuleb esmalt implementeerida Traversable liides.

Traversable Tree where
  traverse g t = ?tree_trav 

variandidTree : Tree Int -> List (Tree Int)
variandidTree = traverse (\ x => [x,-x])

Testkood

variandidTree (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)) ==
[Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf),
 Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf -3 Leaf),
 Branch (Branch Leaf 1 Leaf) -2 (Branch Leaf 3 Leaf),
 Branch (Branch Leaf 1 Leaf) -2 (Branch Leaf -3 Leaf),
 Branch (Branch Leaf -1 Leaf) 2 (Branch Leaf 3 Leaf),
 Branch (Branch Leaf -1 Leaf) 2 (Branch Leaf -3 Leaf),
 Branch (Branch Leaf -1 Leaf) -2 (Branch Leaf 3 Leaf),
 Branch (Branch Leaf -1 Leaf) -2 (Branch Leaf -3 Leaf)]

Vihjeks, traverse on map-i abstraktne vorm, kus on lisatud pure ja <*>-id. Listide Functor ja Traversable on implementeeritud nii:

Functor List where
  --map :  (a -> b) -> List a -> List b
  map f []          = []
  map f ((::) x xs) = (::) (f x) (map f xs)
Traversable List where
  --traverse :  Applicative h => (a -> h b) -> List a -> h (List b)
  traverse f []      =  pure []
  traverse f (x::xs) =  pure (::) <*> (f x) <*> (traverse f xs)

Funktsiooni traverse kasutatakse tihti sisendi-väljundiga. Proovi REPL-ist käivitada

:exec traverse printLn [1,2,3]

Arvu arvamise mäng

Implementeeri klassikaline mäng, mis valib juhusliku arvu nullist sajani ning kasutaja peab selle ära arvama. Kasutaja saab pakkuda arve ja programm ütleb, kas pakutud arv on suurem, võrdne või väiksem. Kui vastus on võrdne (s.t. pakutud arv on võrdne juhuslikult valitud arvuga) on mäng läbi ja trükitakse pakkumiste arv.

> :exec m2ng
Arva ära täisarv vahemikus nullist sajani!
Sisesta arv: 50
Ei! Minu number on suurem
Sisesta arv: 62
Ei! Minu number on väiksem
Sisesta arv: 61
Ära arvasid! Oligi 61. Pakkusid 3 korda.

m2ng : IO ()
m2ng = ?rhs_m2ng

m2ngR

Implementeeri arvu äraarvamise mängu pöördversioon, kus kasutaja valib mõttes (juhusliku) arvu ja programm püüab seda ära arvata. Programm peaks ära tundma sohitegemise, kui kasutaja on vastanud enesele vasturääkivalt.

m2ngR : IO ()
m2ngR = ?rhs_m2ngR