Funktsionaalprogrammeerimine 2024/25 sügis

Kodutöö 5

Selles praktikumis õpime ja harjutame andmestruktuuride kasutamist.

Lisalugemine (vabatahtlik):

Type-Driven development with Idris peatükid:

Andmestruktuurid:

• Chapter 4. User-defined data types, sissejuhatus ja alampeatükid:
  • 4.1. Defining data types
    • 4.1.1. Enumerations
    • 4.1.2. Union types
    • 4.1.3. Recursive types
  • 4.3. Type-driven implementation of an interactive data store
    • 4.3.1. Representing the store
• Chapter 6. Programming with first-class types, alampeatükid:
  • 6.3. Enhancing the interactive data store with schemas, alampeatükid:
    • 6.3.1. Refining the DataStore type
    • 6.3.2. Using a record for the DataStore

Liidesed:

• 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

1. Reduktsioon

Redutseeri väärtuseks (s.t. nii palju kui saab) a) normaaljärjekorras ja b) aplikatiivjärjekorras.

1. {$(\lambda{}f.\ f f) ((\lambda{}x.b) (\lambda{}x.x))$}
2. {$(\lambda{}f.\ (\lambda{}g. f) f) ((\lambda{}x.\ b) (\lambda{}x.\ x))$}
3. {$((\lambda{}x.\ x) (\lambda{}x.\ (\lambda{}y.\ x\ w) r) (\lambda{}x.\ y))$}

2. E-maili andmestruktuur

data Email = E String String

varmo     : Email
kalmer    : Email
karoliine : Email
varmo     = E "varmo.vene"       "ut.ee"
kalmer    = E "kalmer.apinis"    "ut.ee"
karoliine = E "karoliine.holter" "ut.ee"

Implementeerige e-maili andmestruktuuri jaoks show funktsioon (liideses Show) nii, et ülaldefineeritud aadressid näidataks standardsel kujul: show kalmer == "kalmer.apinis@ut.ee"

Show Email where
  show (E nimi domeen) = ?rhs_kiri_show

NB! Liidestest räägime järgnevates praksides pikemalt.

3. Kirja (kirje) andmestruktuur

record on ainult ühe konstruktoriga andmetüüp, millele genereeritakse automaatselt funktsioonid, mis selle väljasid projetseerivad.

record Kiri where
  constructor MkKiri
  saatja   : Email
  saajad   : List Email
  pealkiri : String
  sisu     : String

Kirjutage Kiri tüüpi väärtus, mis tähistaks kirja teilt arvutiteaduse instituudi juhatajale.

testkiri : Kiri
testkiri = ?rhs_testkiri

Kirjuta funktsioon pealkiriSisu, mis tagastab kirja kujul pealkiri: sisu.

pealkiriSisu : Kiri -> String
pealkiriSisu = ?rhs_pealkiriSisu

4. Puu andmestruktuur

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

Defineerige puude võrdsuskontroll (==) (defineerides puudele liidese Eq).

Eq a => Eq (Tree a) where
    x == y = ?rhs_Eq_tree

Näiteks:

(==) (Branch Leaf 1 Leaf) (Branch Leaf 1 Leaf) == True
(==) (Branch Leaf 1 Leaf) (Branch Leaf 1 (Branch Leaf 2 Leaf)) == False

Eq a => tähendab siin, et puid tüübiga Tree a saame võrrelda ainult eeldusel, et tüübil a on juba Eq liides defineeritud ehk oskame juba a tüüpi elemente omavahel võrrelda.

5. Funktsioon height

Defineerige puu kõrguse funktsioon height.

height : Tree a -> Int
height = ?rhs_height

Näiteks:

height Leaf == 0
height (Branch Leaf 'x' Leaf) == 1
height (Branch (Branch Leaf "2" Leaf) "1" (Branch (Branch Leaf "4" Leaf) "3" (Branch Leaf "5" Leaf))) == 3

6. Funktsioon fold

Püüdke aru saada, kuidas on puu fold-i tüüp tuletatud. Seejärel defineerige puule fold funktsioon.

fold : (a -> b -> a -> a) -> a -> Tree b -> a 
fold = ?rhs_fold

Näiteks:

fold (\ a, b, c => a+b+c) 0 (Branch Leaf 1 (Branch Leaf 2 Leaf)) == 3

7. Funktsioon size

Defineerige Tree a andmetüübi jaoks elementide arvu funktsioon size.

size : Tree a -> Nat
size = ?rhs_size

size Leaf == 0
size (Branch (Branch (Branch Leaf 1 Leaf) 7 Leaf) 8 Leaf) == 3

8. Funktsioon heightFold

Defineerige puu kõrguse funktsioon heightFold, kasutades fold-i.

heightFold : Tree a -> Int
heightFold = ?rhs_heightFold

heightFold Leaf == 0
heightFold (Branch Leaf 'x' Leaf) == 1
heightFold (Branch (Branch Leaf "2" Leaf) "1" (Branch (Branch Leaf "4" Leaf) "3" (Branch Leaf "5" Leaf))) == 3

9. Funktsioon memberOf

Defineerige Tree a andmetüübi jaoks sisalduvusoperaator memberOf.

memberOf : Eq a => a -> Tree a -> Bool
memberOf = ?rhs_memberOf

memberOf 7 Leaf == False
memberOf 7 (Branch (Branch (Branch Leaf 1 Leaf) 7 Leaf) 8 Leaf) == True
memberOf 3 (Branch (Branch (Branch Leaf 1 Leaf) 7 Leaf) 8 Leaf) == False

10. Funktsioon balanced

Defineerige predikaat balanced : Tree a -> Bool, mis kontrollib et harude kõrgused ei erineks rohkem kui ühe võrra.

balanced : Tree a -> Bool
balanced = ?rhs_balanced

balanced Leaf == True
balanced (Branch (Branch Leaf 'x' Leaf) 'x' (Branch Leaf 'x' Leaf)) == True
balanced (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) == True
balanced (Branch Leaf 'x' (Branch Leaf 'x' Leaf)) == True
balanced (Branch (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) 'x' Leaf) == False
balanced (Branch (Branch (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) 'x' Leaf) 'x' (Branch (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) 'x' Leaf)) == False

11. Funktsioon gen

Defineerige funktsioon gen mis tagastab mittenegatiivse täisarvu jaoks täpselt sellise kõrgusega täieliku kahendpuu, mis koosneb ainult elementidest a.

gen : Int -> a -> Tree a
gen = ?rhs_gen

Näiteks:

gen 0 'x' == Leaf
gen 1 'x' == Branch Leaf 'x' Leaf
gen 2 'x' == Branch (Branch Leaf 'x' Leaf) 'x' (Branch Leaf 'x' Leaf)
         . . .

12. Funktsioon tree2list

Defineerige funktsioon tree2list mis teisendab puu listiks keskjärjestuses.

tree2list : Tree a -> List a
tree2list = ?rhs_tree2list

Näiteks:

tree2list Leaf == []
tree2list (Branch Leaf 1 Leaf) == [1]
tree2list (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)) == [1,2,3]
 . . .

13. Funktsioon bOrs

Idrises on tüübid esimest klassi väärtused, mis sisuliselt tähendab seda, et saame defineerida näiteks funktsiooni f : Bool -> Type, mis tagastab mingi tüübi, näiteks Int. Defineerige funktsioon bOrs, mis tagastab tüübi Int, kui sisend on False ja tüübi String, kui sisend on True.

bOrs : Bool -> Type 
bOrs b = ?rhs_bOrs

Näiteks:

bOrs False == Int

14. Funktsioon hundred

Defineerige funktsioon hundred, mis tõese sisendi korral tagastab sõne "hundred" (tüüpi String) ning väära sisendi korral arvu 100 (tüüpi Int). Funktsiooni tagastustüübi pead seekord ise välja mõtlema.

hundred : (isString : Bool) -> ?rhs_Type
hundred b = ?rhs_hundred

Näiteks:

hundred False == 100
hundred True == "hundred"

15. Funktsioon add_all

Defineerige funktsiooni reprodT abil funktsioon add_all, mis saab sisendiks naturaalarvu k (k on argumentide arv), akumulaatori acc ning nii mitu naturaalarvulist argumenti, kui arv k lubab. Kokkuvõttes liidab add_all kõik argumendid kokku.

reprodT : Nat  -> Type
reprodT 0  = Nat
reprodT (S k)  = Nat -> reprodT k

add_all : (k : Nat) -> (acc : Nat) -> reprodT k
add_all k acc = ?rhs_add_all

Näiteks:

add_all 5 0 1 2 3 4 5 == 15
add_all 3 0 10 10 10 == 30
add_all 1 0 509 == 509

Tärnülesanded

Funktsioon list2tree

Defineerige funktsioon list2tree, mis teisendab listi puuks. Püüdke lahendada ülesanne nii, et tagastatud puu oleks balansseeritud.

list2tree : List a -> Tree a
list2tree = ?rhs_list2tree

Näiteks:

list2tree []  == Leaf 
list2tree [1] == (Branch Leaf 1 Leaf)
list2tree [1,2,3] == (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf))