Funktsionaalprogrammeerimine 2023/24 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 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

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

Tagasiside

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