Functional Programming 2022/23 fall

Kodutöö 6

Selles praktikumis tegeleme liidestega.

Liidesed

Lisalugemine (vabatahtlik ja kui eelmises 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

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 ratsionaalarvude {$\mathbb{Q}$} 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

-- abifunktsioon, tulevikus kasutada Data.Nat.gcd 
-- (praeguses versioonis pole Data.Nat.gcd täielik, idris kardab, et ei termineeru)
gcd' : Nat -> Nat -> Nat
gcd' 0 x = 0
gcd' x 0 = x
gcd' x y = assert_total $ gcd' y (mod x y)

-- normaliseerimine
norm : Rat -> Rat 
norm (0 :/: b) = 0 :/: 1
norm (a :/: 0) = 0 :/: 0
norm (a :/: b) = 
    let n = gcd' a b in
    a`div`n :/: 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.

Tagasiside

Kas teil oli meeles tagasisidet anda? Kommenteerige kindlasti, kui mingi ülesanne võttis ootamatult palju aega.