Functional Programming 2023/24 fall

Kodutöö 4

Selles praktikumis õpime ja harjutame andmestruktuuride ja liideste 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. 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.

2. 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

3. 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.

4. 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

Vihje

Idrises on sisseehitatud funktsioon max, mis võtab kaks argumenti ja tagastab neist suurima.

5. 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

6. 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

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

8. 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

9. 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

Vihje

Idrises on sisseehitatud funktsioon abs, mis võtab ühe argumendi ja tagastab selle absoluutväärtuse.

10. 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)
         . . .

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

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))

Vihje 1: võite kasutada Idrisesse sisse ehitatud funktsiooni splitAt, selleks peate aga importima mooduli import Data.List. Abiks tuleb mustrisobitus case-of või with süntaksiga.

Vihje 2: naturaalarvude jagamiseks kasuta infix operaatori / asemel funktsiooni div, selleks lisa ka import import Data.Nat.