Programming Languages 2019/20 fall

Kuues Praktikum

Selles praktikumis harjutame andmestruktuuride ja tüübiklasside kasutamist.

Näiteülesanded

E-maili andmestruktuur

data Email = E String String  

kalmer, vesal, varmo :: Email
kalmer = E "kalmer.apinis" "ut.ee"
vesal  = E "vesal"         "ut.ee"
varmo  = E "varmo.vene"    "ut.ee"

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

Kirja (kirje) andmestruktuur

data Kiri = K {
    saatja   :: Email,
    saaja    :: [Email],
    pealkiri :: String,
    sisu     :: String
}  

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

 
testkiri :: Kiri
testkiri = undefined

Puu andmestruktuur

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

Defineerige puudele võrdsuskontroll (==) ja puu kõrguse funktsioon height::Tree a -> Int.

Harjutusülesanded

Ülesanne 1

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

size :: Tree a -> Int
size = undefined

Ülesanne 2

Defineerige Tree a andmetüübi jaoks sisalduvusoperaator memberOf.

memberOf :: Eq a => a -> Tree a -> Bool
memberOf = undefined

Ülesanne 3

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

  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 :: Tree a -> Bool
  balanced = undefined

Ülesanne 4

Defineerige funktsioon gen mis tagastab mittenegatiivse täisarvu jaoks täpselt sellise kõrgusega puu. 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)
         . . .

gen :: Int -> a -> Tree a
gen = undefined

Ülesanne 5

Defineerige funktsioon tree2list mis teisendab puu listiks. Näiteks:

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

tree2list :: Tree a -> [a]
tree2list = undefined

Ülesanne 6

Defineerige funktsioon list2tree, mis teisendab listi puuks. Näiteks:

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

list2tree :: [a] -> Tree a
list2tree = undefined

Püüdke lahendada ülesanne nii, et tagastatud puu oleks balanseeritud.

Ülesanded*

Tee andmetüübist Tree a klassi Foldable isend implementeerides selle jaoks foldr. Testi oma lahendust.