Boonusülesanded

Järgnevad boonusülesanded on laadilt nuputamisülesanded. Rahuldavad lahendused ei pruugi olla kuigi pikad, kuid nende väljatöötamine nõuab tugevat kombineerimisoskust, mis aga on igasuguses programmeerimises hädavajalik.

Raskemate ülesannete lahendamine annab lahendajale kokkuvõttes kindlasti parema Haskellis programmeerimise oskuse ja funktsionaalse programmeerimise tunnetuse kui vaid praktikumiülesannete juurde jäämine. Julge pealehakkamine on pool võitu (mitte küll pool hinnet)!

Tingimused

Lahendused tuleb esitada mulle (ka Kalmeri rühmade tudengitel), võib saata meiliga. Iga ülesande üks lahendus annab kuni 10 punkti ehk 1 hindepalli. Iga tudeng saab boonusülesannetest kokku teenida maksimaalselt 50 punkti. Rohkem lahendusi kelleltki vastu ei võta, et teistel ka midagi teha jääks.

Et üldse punkte teenida, peab programm

Loetavamad programmid teenivad segasematest rohkem. Kommentaarid koodis on abiks.

Kui ma lükkan esitatud lahenduse tagasi, siis ma juhin tähelepanu puudustele, mille pärast ma sellise otsuse langetasin. Sama tudeng võib sama ülesande lahenduse uuesti esitada, kui need puudused on kõrvaldatud. Mitmekordse esitamise eest punkte maha ei lähe.

Ühele ülesandele võib esitada uue lahenduse isegi juhul, kui mõni lahendus on juba aktsepteeritud, kuid siis annab uus lahendus punkte vaid niivõrd, kuivõrd temas on uusi endistest lahendustest paremaid osi. Mõnest varasemast lahendusest üle võetud osad tuleb korrektsuse mõttes varustada vastava kommentaariga ja need punkte ei anna.

Normaaleksamil võetakse arvesse parajasti nende lahenduste punktid, mis on esitatud hiljemalt 2 ööpäeva enne sessi ajal toimuva esimese eksami algust. Järeleksamil võetakse arvesse parajasti nende lahenduste punktid, mis on esitatud hiljemalt 2 ööpäeva enne järeleksami algust.

Kõik lahendused, mis on teeninud rohkem kui 0 punkti, ilmuvad siia kohe avalikult välja. Nii saavad hilisemad lahendajad vaadata, kuidas varasemad on lahendanud.

Küsimusi võib ülesannete kohta esitada ja võib juhtuda, et saate sellele ka abistavaid vastuseid, kuid üldpõhimõte on selline, et ülesande lahendamise juurde kuulub ka iseseisev vajaliku info otsimine — ka siis, kui see puudutab peale Haskelli, funktsionaalse programmeerimise ja informaatika mõnd muud valdkonda, millest konkreetne ülesanne juhtub olema.

Ülesanded

  1. Vaatleme ülesannet märkida 2×2n ruudustikus n ruutu nii, et ühelgi kahel märgitud ruudul poleks ühist tippu.

    Arvutis kujutame ruudu horisontaalset serva sidekriipsuga, ruudu vertikaalset serva püstkriipsuga, ruudu tippu plussiga, ruudu sisemust tühikuga ning märgitud ruutu tühikut asendava tärniga. Näiteks ülesande üks lahendus n=2 korral on

    +-+-+-+-+
| |*| |*|
+-+-+-+-+
| | | | |
+-+-+-+-+

    Ülearuseid tühisümboleid olla ei tohi; 2×2n ruudustiku korral on joonisel 5 rida ja igas reas 4n+1 sümbolit.

    Üht joonist esitame Haskellis ridade kaupa stringide listina. Mugavuse mõttes defineerime tüübisünonüümi:

    type Picture
  = [String]

    Olgu antud tüübisignatuur

    pics
  :: [[Picture]]

    Defineerida muutuja pics väärtuseks lõpmatu list, mille element number n on list algse ülesande kõigist lahendustest selle n korral. Listi elemente nummerdame alates 0-st. Lahenduste omavaheline järjekord pole oluline, kuid ükski neist ei tohi korduda.

    Näiteks mapM_ (mapM_ putStrLn) (pics !! 2) võib anda väljundi

    +-+-+-+-+
| |*| |*|
+-+-+-+-+
| | | | |
+-+-+-+-+
+-+-+-+-+
| |*| | |
+-+-+-+-+
| | | |*|
+-+-+-+-+
+-+-+-+-+
| | | |*|
+-+-+-+-+
| |*| | |
+-+-+-+-+
+-+-+-+-+
| | | | |
+-+-+-+-+
| |*| |*|
+-+-+-+-+
+-+-+-+-+
|*| | |*|
+-+-+-+-+
| | | | |
+-+-+-+-+
+-+-+-+-+
| | | |*|
+-+-+-+-+
|*| | | |
+-+-+-+-+
+-+-+-+-+
|*| | | |
+-+-+-+-+
| | | |*|
+-+-+-+-+
+-+-+-+-+
| | | | |
+-+-+-+-+
|*| | |*|
+-+-+-+-+
+-+-+-+-+
|*| |*| |
+-+-+-+-+
| | | | |
+-+-+-+-+
+-+-+-+-+
| | |*| |
+-+-+-+-+
|*| | | |
+-+-+-+-+
+-+-+-+-+
|*| | | |
+-+-+-+-+
| | |*| |
+-+-+-+-+
+-+-+-+-+
| | | | |
+-+-+-+-+
|*| |*| |
+-+-+-+-+

    Esitatud lahendused

  2. Bitistringi, mis on mingi koha pealt kaheks murtud, nimetame katkestusega bitistringiks. Märgime murdekohta sümboliga ‘/’; näiteks on katkestusega bitistringid 10/0, 01/110, 1/1, 110/, /0. Katkestusega bitistringi pikkuseks nimetame tema algset (katkestamata kujul) pikkust, st osade pikkuste summat.

    Toome sisse katkestusega bitistringi tüübi koodiga

    data Brk
  = Brk [Bool] [Bool]

    Andmekonstruktori Brk esimene ja teine argument on vastavalt katkestusega bitistringi osad enne ja pärast katkestust; tõene tähistab bitti 1 ja väär bitti 0. Et Brk-tüüpi väärtusi esitataks stringina nii, nagu katkestusega bitistringid said ülal kirjeldatud, muudame tüübi Brk klassi Show esindajaks koodiga

    instance Show Brk
  where

    showsPrec _ (Brk x y) s
      = let
          op b
            = (:) (if b then '1' else '0')
        in
        foldr op ('/' : foldr op s y) x

    Olgu antud tüübisignatuur

    brks
  :: [[Brk]]

    Defineerida muutuja brks väärtuseks lõpmatu list, mille element number n on list kõigist katkestusega bitistringidest pikkusega n. Listi elemente nummerdame alates 0-st. Sama pikkusega katkestusega bitistringide omavaheline järjekord pole oluline, küll aga ei tohi ükski neist korduda.

    Näiteks võib olla

    brks !! 2 ==> [/00,/10,/01,/11,0/0,1/0,0/1,1/1,00/,10/,01/,11/]

    Esitatud lahendused

  3. Defineerime jada s reegliga sn=(n+1)⋅2n.

    Olgu antud tüübisignatuurid

    shpGen
  :: (a -> a -> a) -> (a -> a) -> a -> [a]
picSum
  :: [Picture] -> [Picture] -> [Picture]
picDbl
  :: [Picture] -> [Picture]
picOne
  :: [Picture]
brkSum
  :: [Brk] -> [Brk] -> [Brk]
brkDbl
  :: [Brk] -> [Brk]
brkOne
  :: [Brk]

    Defineerida muutujad shpGen, picSum, picDbl, picOne brkSum, brkDbl, brkOne, nii, et

    snms
  = shpGen (+) (* 2) 1
    defineeriks muutuja snms väärtuseks jada s listi kujul, 
    pics
  = shpGen picSum picDbl picOne
    annaks 1. ülesande lahenduse ning 
    brks
  = shpGen brkSum brkDbl brkOne
    2. ülesande lahenduse.

    Esitatud lahendused

  4. Naturaalarvu 2-ndesitust käsitletakse tavaliselt kui lõplikku bitijärjendit. Kuid seda võib võtta ka kui lõpmatut bitijärjendit, kus mingist kohast alates järgu suurenemise suunas on kõik bitid nullid. Jättes lõpmatu 2-ndesituse käsitluses selle tingimuse ära, saame 2-aadilise täisarvu mõiste. 2-aadiline täisarv on niisiis suvaline algusotsast lõpmatu bitijärjend.

    2-aadiliste täisarvude liitmine defineeritakse analoogselt naturaalarvude 2-ndesituste liitmisalgoritmile. 2-aadiliste täisarvude liitmisel see protsess on küll lõpmatu, kuid summa iga bitt on üheselt määratud (iga konkreetse bitini algoritm varem või hiljem jõuab), mistõttu on ka kogu järjend üheselt määratud. On võimalik näidata, et selline liitmine on kommutatiivne ja assotsiatiivne ja 0 on tema ühikelement.

    Naturaalarvud kuuluvad 2-aadiliste arvude hulka oma lõpmatu 2-ndesitusena. Negatiivsed täisarvud kuuluvad sinna vastavalt järgmisele reeglile: kui n on positiivne naturaalarv, siis –n on selline 2-aadiline täisarv, millele arvu n liitmisel saame arvu 0. Sellega on iga täisarv 2-aadilise täisarvuna üheselt määratud. Muidugi jääb üle palju 2-aadilisi täisarve, mis pole tavalise täisarvuna interpreteeritavad.

    Olgu antud tüübisignatuur

    (#)
  :: Integer -> Integer -> Integer

    Defineerida infiksoperaatori # väärtuseks 2-aadiliste täisarvude bitikaupa xor-tehe ahendatuna tavalistele täisarvudele.

    Näiteks

    0 # 0 ==> 0
0 # 1 ==> 1
1 # 1 ==> 0
1 # 2 ==> 3
2 # 3 ==> 1
(-1) # (-1) ==> 0
(-1) # (-2) ==> 1
(-1) # 1 ==> -2

    Esitatud lahendused

  5. Kuitahes laia hargnemisega puud, mille tippudes on üht tüüpi andmed, toome sisse deklaratsiooniga

    data Rose a
  = Node a [Rose a]

    Väärtus kujul Node x l on puu, mille juurtippu on kirjutatud x ja vahetud alampuud on parajasti listi l elemendid. Leht on tipp, millel pole vahetuid alampuid.

    Olgu antud tüübisignatuur

    laiuti
  :: Rose a -> [a]

    Defineerida muutuja laiuti väärtuseks funktsioon, mis võtab argumendiks suvalise puu t ja annab tulemuseks listi, milles on kõik puu t tippudes olevad andmed laiutiläbimise järjekorras, st kõrgustasemete kaupa.

    Näiteks

    laiuti (Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 [], Node 6 [Node 7 []]])
  ==> [1, 2, 5, 6, 3, 4, 7]

    Eesmärgiks on programmeerida arvutus, mis kasutaks võimalikult vähe selliseid vaheandmestruktuure, mis pole algse puu ega tulemuslisti osad. Mittestruktuurseid abiväärtusi, kaasa arvatud funktsioone, võib vabalt kasutada.

    Esitatud lahendused

  6. Arvul 2 pole ratsionaalarvudes täpset ruutjuurt. Seega pole võimalik, et kaks nullist erinevat täisruutu oleksid täpselt suhtes 2:1. Küll on aga olemas täisarvud, mille ruutude suhe on “peaaegu 2” ehk millest ühe ruudu kahekordne erineb teise ruudust parajasti 1 võrra. Sellised on näiteks arvupaar (2,3) (sest 2⋅22+1=32), arvupaar (5,7) (sest 2⋅52–1=72) jpt. Diofantiliste võrrandite teoorias näidatakse, et selliseid paare on lõpmatult. Sellised arvupaarid annavad arvule √2 parima lähendi, mida taolises suurusjärgus täisarvudega saab üldse anda.

    Olgu antud signatuur

    sq2parim
  :: (Integral a)
  => a -> (Integer , Integer)

    Defineerida muutuja sq2parim väärtuseks funktsioon, mis naturaalarvulisel argumendil n annab tulemuseks komponentide summa suuruse järjekorras n-nda kirjeldatud tingimusi rahuldava naturaalarvupaari.

    Näiteks

    sq2parim 0
  ==> (0 , 1)
sq2parim 1
  ==> (1 , 1)
sq2parim 2
  ==> (2 , 3)
sq2parim 3
  ==> (5 , 7)
sq2parim 4
  ==> (12 , 17)
sq2parim 5
  ==> (29 , 41)
...............
sq2parim 50
  ==> (4866752642924153522 , 6882627592338442563)

    Negatiivsetel argumentidel peab funktsioon tulemuseks andma paari, mis on saadud vastandarvulisele argumendile vastavast paarist paaris argumendi puhul vasaku ja paaritu argumendi puhul parema komponendi asendamisel tema vastandarvuga.

    Esitatud lahendused

  7. Vaatleme naturaalarvude esitusi paarikaupa erinevate positiivsete täisruutude summana. Liidetavate arv pole fikseeritud; vaid järjekorra poolest erinevad esitused loeme samaks. Näiteks arvul 25 on kaks niisugust esitust: 16+9 (kahe liidetavaga) ja 25 (ühe liidetavaga). Arvul 8 selliseid esitusi pole, sest esitused 4+4, 4+1+1+1+1 jms ei tule arvesse liidetava kordumise tõttu.

    Nimetame naturaalarvu n ruudulisuseks tema selliste esituste arvu. Niisiis arvu 25 ruudulisus on 2, arvu 8 ruudulisus on 0.

    Olgu antud tüübisignatuur

    ruudulisused
  :: [Int]

    Defineerida muutuja ruudulisused väärtuseks lõpmatu list, mille element number n on arvu n ruudulisus. Listi elemente nummerdame alates 0-st.

    Esitatud lahendused

  8. Dokumendis rat.pdf lk 9–11 defineeritakse mittenegatiivse ratsionaalarvu maksegiptiline ja lahutusegiptiline esitus.

    Olgu antud tüübisignatuur

    maxEgipt, lahEgipt
  :: Rational -> [Integer]

    Defineerida muutuja maxEgipt väärtuseks funktsioon, mis võtab argumendiks ratsionaalarvu r ja kui see pole negatiivne, siis annab tulemuseks listi täisarvudest, mille pöördarvud on parajasti r maksegiptilise esituse liidetavad. Negatiivse argumendiga väärtustamine peab andma adekvaatse veateate. Analoogselt defineerida muutuja lahEgipt lahutusegiptilise esituse leidmiseks. Mõlemal juhul peavad arvud tulemuslistides olema järjestatud mittekahanevalt.

    Esitatud lahendused

  9. Teatavasti on listist indeksi järgi otsimine ebaefektiivne, keerukus on lineaarne. Olukorda saab parandada, kui andmed paigutada teistsuguse struktuuri järgi.

    Väleda listi tüübid olgu defineeritud deklaratsiooniga

    data VäleList a
  = Tühi
  | Puu (Puu a , [Int])

    kus kasutatavad puutüübid on kirjeldatud deklaratsiooniga

    data Puu a
  = Leht a
  | Harud (Puu a) (Puu a)

    Tühja ja üheelemendilised andmestruktuurid defineerime koodiga

    empty
  :: VäleList a
empty
  = Tühi

    singleton
  :: a -> VäleList a
singleton x
  = Puu (Leht x , [])
    Üldise vastavuse listide ja väledate listide vahel defineerib kood 
    puu -- abifunktsioon
  :: VäleList a -> (Puu a , [Int])
puu (Puu p)
  = p
  
jrgm -- abifunktsioon
  :: [Int] -> Int
jrgm (b : bs)
  = b + b
jrgm _
  = 1

fromList
  :: [a] -> VäleList a
fromList []
  = empty
fromList xs
  = let
      väle zs@ (x : xs)
        = case xs of
            _ : _
              -> let
                   kahekaupa ((t , as) : (u , bs) : ps)
                     = (Harud t u , jrgm as : bs) : kahekaupa ps
                   kahekaupa ps
                     = ps
                 in
                 väle (kahekaupa zs)
            _
              -> x
    in
    Puu (väle (map (puu . singleton) xs))

toList
  :: VäleList a -> [a]
toList (Puu (t , _))
  = let
      toList (Harud ut vt) as
        = toList ut (toList vt as)
      toList (Leht x)      as
        = x : as
    in
    toList t []
toList _
  = []
    Kirjutada definitsioonid muutujatele elemAt ja updateAt, mis rahuldaksid signatuure 
    elemAt
  :: Int -> VäleList a -> Maybe a

updateAt
  :: Int -> a -> VäleList a -> VäleList a
    ja annaksid neile muutujatele samad väärtused nagu naiivsed definitsioonid 
    elemAt n vl
  | 0 <= n && n < length (toList vl)
    = Just (toList vl !! n)
  | otherwise
    = Nothing

updateAt n x vl
  | 0 <= n && n < length (toList vl)
    = fromList (take n (toList vl) ++ [x] ++ drop (n + 1) (toList vl))
  | otherwise
    = vl

    Esitatud lahendused

  10. Täiendada ülesandes 9 defineeritud väledate listide teeki operaatoritega push ja pop. Need muutujad peavad vastama signatuuridele

    push
  :: (a , VäleList a) -> VäleList a
pop
  :: VäleList a -> Maybe (a , VäleList a)

    ja, kitsendatult operaatoriga fromList tekitatud struktuuridele, olema samade väärtustega nagu naiivsete definitsioonide

    push (x , vl)
  = fromList (toList vl ++ [x])
pop vl
  | null (toList vl)
    = Nothing
  | otherwise
    = Just (last (toList vl) , fromList (init (toList vl)))

    korral.

    Esitatud lahendused

Härmel Nestra

Ülemkataloogi indeksisse.