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
- 7.1. Generic comparisons with Eq and 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]