Funktsionaalprogrammeerimine 2024/25 sügis

Kodutöö 6

Liidesed

Selles praktikumis tegeleme liidestega.

Konspekt

Lisalugemine (vabatahtlik ja kui 4. praktikumis juba ei lugenud):

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

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)

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

Lisaülesanded

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

12. Range instantsi üldistamine

Üldistage Range Rat instansi, et see ei töötaks vaid ratsionaalarvude korral, vaid tingimusel et see rahuldab mingit konkreetset nimekirja liideseid. Mis liideseid oleks tarvis?

Näiteks: (samad testid mis eelmise ülesande juures)

Tärnülesanded

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

13*. 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]