Programmeerimiskeeled 2020/21 sügis

5. Haskelli praktikum

Selles praktikumis harjutame andmestruktuuride ja tüübiklasside kasutamist.

Näiteülesanded

E-maili andmestruktuur

data Email = E String String 

kalmer, varmo, simmo :: Email
kalmer = E "kalmer.apinis" "ut.ee"
varmo  = E "varmo.vene"    "ut.ee"
simmo  = E "simmo.saan"    "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,
  saajad   :: [Email],
  pealkiri :: String,
  sisu     :: String
}  deriving (Show)

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

 
testkiri :: Kiri
testkiri = undefined

Kirjuta funktsioon pealkiriSisu :: Kiri -> String, mis tagastab kirja kujul pealkiri: sisu.

Puu andmestruktuur

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

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

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 (Branch (Branch (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) 'x' Leaf) 'x' (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 täieliku kahendpuu. 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 keskjärjestuses. 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.

Ülesanne 7

Kirjuta Functor tüübiklassi instants Tree tüübile.

instance Functor Tree where
  fmap f t = undefined

Ülesanne 8

Kirjuta Foldable tüübiklassi instants Tree tüübile foldr kaudu. Võid proovida seda teha ka foldMap kaudu.

instance Foldable Tree where
  foldr f b t = undefined
  -- või
  -- foldMap f t = undefined

Veendu, et nüüd saab meie puudel muuhulgas kasutada standardseid length, elem ja toList (impordi Data.Foldable) funktsioone, mis peaks käituma nagu ülaldefineeritud size, memberOf ja tree2list.

Ülesanded*

2×2 maatriksi andmestruktuur

data Mat22 a = Mat22 a a a a  deriving (Show, Eq)

Näiteks Mat22 1 2 3 4 esitab 2×2 maatriksit {$ \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} $}.

Ülesanne 9

Kirjuta Semigroup ja Monoid tüübiklasside instantsid Mat22 tüübile nii, et (<>) operaator korrutaks maatriksid ja mempty oleks ühikmaatriks. 2×2 maatriksite korrutis avaldub järgnevalt:

{$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} e & f \\ g & h \end{pmatrix} = \begin{pmatrix} ae+bg & af+bh \\ ce+dg & cf+dh \end{pmatrix} $}

instance Num a => Semigroup (Mat22 a) where
  (Mat22 a b c d) <> (Mat22 e f g h) = undefined
  stimes = stimesMonoid -- fibMonoid jaoks vajalik definitsioon

instance Num a => Monoid (Mat22 a) where
  mempty = undefined

Korrektse lahenduse korral arvutab järgnevalt antud funktsioon n-inda Fibonacci arvu efektiivselt keerukusega {$ \mathcal{O}(\log n) $}, kasutades äsjadefineeritud maatriksite korrutamise monoidi:

fibMonoid :: (Integral a, Num b) => a -> b
fibMonoid n = fn
  where Mat22 _ fn _ _ = stimes n (Mat22 1 1 1 0)

Selle matemaatilist tausta võib lugeda näiteks Wikipediast.

Ülesanne 10

Kirjuta Num tüübiklassi instants Mat22 tüübile.

instance Num a => Num (Mat22 a) where
  (Mat22 a b c d) + (Mat22 e f g h) = undefined
  (Mat22 a b c d) * (Mat22 e f g h) = undefined
  abs (Mat22 a b c d) = undefined
  negate (Mat22 a b c d) = undefined
  -- järgnevaid definitsioone pole vaja muuta
  fromInteger 0 = Mat22 0 0 0 0
  fromInteger 1 = mempty
  fromInteger _ = error "fromInteger: Mat22"
  signum _ = error "signum: Mat22"

Korrektse lahenduse korral arvutab järgnevalt antud funktsioon n-inda Fibonacci arvu efektiivselt keerukusega {$ \mathcal{O}(\log n) $}, kasutades äsjadefineeritud maatriksite aritmeetikat:

fibNum :: (Integral a, Num b) => a -> b
fibNum n = fn
  where Mat22 _ fn _ _ = (Mat22 1 1 1 0) ^ n