Eksamiülesannete harjutamine
Eksamil on aega 3.5 tundi, et lahendada
- baastest (kellel veel pole arvestust), ja
- eksamiülesanded.
Eksamiülesannetest kolm on Haskelli kohta ja kolm Scala kohta. Mõlema keele kohta on kaks lihtsamat ülesannet ja üks raskem.
Pidades silmas piiratud eksamiaega (3.5h), on arvestatud sellega, et hindeid E ja D väärivad tudengid peaks oskama lihtsamaid ülesandeid lahendada ning A/B väärivad tudengid peaks oskama ka raskemaid lahendada.
Kõik ülesanded annavad kaheksa punkti ning kokku on võimalik saada 40 punkti. S.t maksimumpunktide saamiseks piisab lahendada kõik lihtsamad ülesanded ning kas Scala või Haskelli raskem ülesanne.
Ülesannete esitamine käib läbi Moodle. Seega eeldame arvuti kasutamist. Muidu kehtivad standardsed eksami reeglid: ei tohi kasutada teiste inimeste abi. Arusaamatuste vältimiseks on keelatud ülesannete lahendamiseks mittevajalike programmide/(veebi-)teenuste kasutamine eksami ajal.
Ülesanne H1 (8 punkti)
Funktsioon h :: [a -> b] -> [(a,b)] -> [b]
saab argumendiks funktsioonide listi ja paaride listi.
Iga paaride listi element (x,y) genereerib
lõpptulemusse kõigepealt väärtuse y,
seejärel teisendatud x väärtused.
h [(+1), (*2), id] [(2,400),(3,100)]
= [400, 2+1, 2*2, id 2, 100, 3+1, 3*2, id 3]
= [400,3,4,2,100,4,6,3]
h [const "x", show] [(2,"a"),(3,"b")]
= ["a",const "x" 2, show 2, "b", const "x" 3, show 3]
= ["a","x","2","b","x","3"]
H1.hs
h :: [a -> b] -> [(a,b)] -> [b] h = undefined
Ülesanne H2 (8 punkti)
Kasutades järgnevaid definitsioone:
data Puu a = Leht a | Haru (Puu a) a (Puu a) deriving (Show, Eq)
Kirjuta protseduur f :: (a -> IO ()) -> Puu a -> IO (),
mis võtab argumendiks protseduuri ja puu.
Protseduur
- rakendab eesjärjekorras argumentprotseduuri (3p)
- vahetult enne rakendamist trükib kauguse juurest (4p)
- enne vasema alampuu töötlemist trükib "vasem:" (0.5p)
- enne parema alampuu töötlemist trükib "parem:" (0.5p)
Näiteks:
*Main> f print p1 0'd' vasem: 1'b' vasem: 2'a' parem: 2'c' parem: 1'f' vasem: 2'e' parem: 2'g'
H2.hs
-- Näide:
p1 = Haru (Haru (Leht 'a') 'b' (Leht 'c'))
'd'
(Haru (Leht 'e') 'f' (Leht 'g'))
f :: (a -> IO ()) -> Puu a -> IO ()
f h p = undefined
Ülesanne H3 (8 punkti)
Kasutades järgnevaid definitsioone:
data KahendPuu a = Leht | Haru (KahendPuu a) a (KahendPuu a)
deriving (Eq, Show)
Kirjutada KahendPuu-le Ord instants, nii et <= operaator oleks
järjestus sisalduvuse mõttes. S.t. väiksema puu andmed sisalduvad
suuremas puus. NB! Puu ei pruugi olla sorteeritud.
Näiteks:
*H3> puu1 <= puu1 True *H3> puu1 <= puu2 False *H3> puu1 <= puu3 True *H3> puu1 <= puu5 True *H3> puu2 <= puu1 False *H3> puu2 <= puu2 True *H3> puu2 <= puu3 False
H3.hs
puu1, puu2, puu3, puu5 :: KahendPuu Int puu1 = Haru Leht (-1) Leht puu2 = Haru (Haru Leht 0 Leht) (-2) (Haru Leht 0 Leht) puu3 = Haru (Haru (Haru Leht 1 Leht) 2 (Haru Leht 0 Leht)) (-3) (Haru (Haru Leht 0 Leht) 2 (Haru Leht (-1) Leht)) puu5 = Haru (Haru (Haru (Haru (Haru Leht 1 Leht) 2 (Haru Leht 1 Leht)) (-1) (Haru (Haru Leht (-1) Leht) 2 (Haru Leht 1 Leht))) (-4) (Haru (Haru (Haru Leht (-1) Leht) 2 (Haru Leht 1 Leht)) (-1) (Haru (Haru Leht (-1) Leht) 0 (Haru Leht 1 Leht)))) 3 (Haru (Haru (Haru (Haru Leht 0 Leht) 2 (Haru Leht (-1) Leht)) 2 (Haru (Haru Leht (-1) Leht) 1 (Haru Leht (-1) Leht))) 1 (Haru (Haru (Haru Leht 0 Leht) 0 (Haru Leht 0 Leht)) 2 (Haru (Haru Leht (-1) Leht) 2 (Haru Leht 1 Leht))))
Ülesanne S1 (8 punkti)
a) (4p) Defineeri funktsioon
neighbour(w1: String, w2: String): Boolean
See tagastab true siis ja ainult siis, kui tema argumendid
erinevad täpselt ühes kohas.
Näiteks: “kala” ja “kaja” või “karu” ja “maru”. Võib eeldada, et argumendid on ühepikkused.
def neighbour(w1: String, w2: String): Boolean = ???
b) (4p) Meil on defineeritud globaalne muutuja:
val dict = Set("kala", "koer", "pala", "maja", "kaja")
Defineerida järgmine funktsioon:
neighboursOf(word: String): Set[String]
mis tagastab sõne word kõik naabrid hulgast dict.
Näiteks võiks ülaloleva sõnade hulga puhul olla neighboursOf("kala") tulemus Set("pala", "kaja").
def neighboursOf(word: String): Set[String] = ???
Ülesanne S2 (8 punkti)
sealed trait Num case object Zero extends Num case class Succ(n: Num) extends Num case class Pred(n: Num) extends Num
Nendega saab täisarve defineerida. Täisarv on kas 0 või mõne teise teisarvule järgnev arv või eelnev arv.
Näiteks saab kodeerida arvud 2 ja -2 vastavalt:
val two = Succ(Succ(Zero)) val minusTwo = Pred(Pred(Zero))
Arve saab ka rumalalt kodeerida, näiteks on kahte võimalik ka väljendada järgmiselt:
val stupidTwo = Succ(Pred(Succ(Succ(Zero))))
a) (4p) Defineeri funktsioon, mis tagastab selliste kodeeritud arvude puhul nende tegelik väärtus:
def numToInt(n: Num): Int = ???
b) (4p) Defineeri funktsioon, mis kodeerib etteantud täisarvu nende case klassidega
def intToNum(i: Int): Num = ???
Kindlasti tasub kontrollida, et iga arvu puhul saad edasi-tagasi konverteerides esialgse arvu tagasi: numToInt(intToNum(n)) == n
Ülesanne S3 (8 punkti)
Implementeerim mittetühjade listide andmestruktuur MTList.
- Traiti
MTListinstantsidel olgu defineeritudMTListiOp[T, MTList]meetodid (3p). - Lisaks peab kompanjonobjekstis olema
MTList-ideEhitaja[A, MTList[A]](5p).
Andmestruktuur peab läbima all toodud testid.
object Kolmas {
trait Ehitaja[El, C] {
def +=(e: El): Unit
def tulemus: C
}
trait MTListiOp[+T,+CC[_]]{
def listiks: List[T] // 1p
def map[U](f: T => U): CC[U] // 1p
def +:[U >: T](x:U): CC[U] // 1p
}
trait MTList[+T] extends MTListiOp[T, MTList]
case class Yks[T](x: T) extends MTList[T] {
// ???
}
case class Lisa[T](x: T, xs: MTList[T]) extends MTList[T] {
// ???
}
object MTList {
// 5p
def uusEhitaja[A]: Ehitaja[A, MTList[A]] = ???
def apply[T](xs: T*): MTList[T] = {
val b = uusEhitaja[T]
for (x <- xs.reverse) b += x
b.tulemus
}
}
def main(args: Array[String]): Unit = {
val x = MTList(1,2,3,4)
val y = MTList(2)
val z = MTList('a','b')
assert(x.map(_+1).listiks == List(2,3,4,5))
assert(y.map(_*2).listiks == List(4))
assert((1 +: y).listiks == List(1,2))
assert(z.map(_.toUpper).listiks == List('A', 'B'))
}
}