Písemka z Haskellu - 21.5.2010

1. (10 bodů)
   Byl zadán datový typ pro Binární stromy, něco jako
   data Strom a = List a | Vrchol (Strom a) (Strom a)
   tzn, bez hodnoty ve vnitřních uzlech. Pak tam byla funkce zahada (pokud jsem to měl dobře, tak vracela seznam hodnot listů v pre-order průchodu, ale na přesný znění si už nevzpomenu), úkolem bylo určit:

a) typovou signaturu funkce zahada
b) co vrátí aplikace funkce na nakreslený strom
c) slovy popsat co funkce dělá
d) napsat výstup funkce, která tam byla nadefinovaná (vyskytovaly se tam nějaký nekonečný datový struktury, z toho se bralo prvních 5 prvků atd, docela jednoduchý)

2. (10 bodů)
   Funkce pro převod čísla v číselné soustavě o daném základu na číslo v desítkové soustavě

Příklady:
prevod 2 [1,1,1,0]
14
prevod 64 [1,63]
127

a) napsat typovou signaturu
b) napsat funkci prevod pomocí rekurze
c) napsat funkci prevod pomocí použití jedné z funkcí - map, filter, foldl, foldr
d) napsat funkci prevod pomocí stručných seznamů, ale bez použití funkcí z c)

3. (15 bodů)
   Úkolem bylo nadefinovat funkci
   gen n str, která vracela množinu všech slov, která vznikla záměnou n písmen z řetězce str, množina navíc měla být seřazená podle abecedy (ale nevim, jestli podle klasický, nebo podle tý co vracela funkce abeceda).

K dispozici byla funkce abeceda, která vracela seznam možných písmen.

Příklad:
abeceda
["a","b","c"]

gen 1 "aac"
["aaa","aab","abc","acc","bac","cac"]

4. (15. bodů)
   Dva zakořeněné stromy (obecné - ne binární, s hodnotou ve všech uzlech) a,b jsou ekvivalentní, pokud existuje ve stromu b permutace podstromů (a jejich postromů... - rekurzivně do hloubky), taková že je shodná se stromem a. Snažil jsem se to napsat nějak zjednodušeně, ale nevim, jestli se mi to povedlo :D . Z příkladu to bylo jednoduše vidět, ale strom sem moc čitelně nedostanu...

a) napsat datovou strukturu pro reprezentaci takových stromů
b) napsat funkci ekviv, která zjistí, zda dva zadané stromy jsou ekvivalentní

Jookyn wrote:4. (15. bodů)
Dva zakořeněné stromy (obecné - ne binární, s hodnotou ve všech uzlech) a,b jsou ekvivalentní, pokud existuje ve stromu b permutace podstromů (a jejich postromů... - rekurzivně do hloubky), taková že je shodná se stromem a. Snažil jsem se to napsat nějak zjednodušeně, ale nevim, jestli se mi to povedlo :D . Z příkladu to bylo jednoduše vidět, ale strom sem moc čitelně nedostanu...

a) napsat datovou strukturu pro reprezentaci takových stromů
b) napsat funkci ekviv, která zjistí, zda dva zadané stromy jsou ekvivalentní

ja sa pokusim spravit nejako ten stromcek ;)

           1                                            1         
       /   |   \                                    /   |   \     
    2      3      4            ~~~               3      4      2  
         /   \                                 /   \       
        5     6                               6     5      

snad je to aspon priblizne jasne, ako ta ekvivalencia mala vyzerat ;)

K prvnímu příkladu - pokud se dobře pamatuji, zadání stromu a funkce zahada bylo toto:

data BStrom a = List a | Vetev (BStrom a) (BStrom a)
zahada x = zahada' x []
  wherezahada' (List l) = (l:)zahada' (Vetev l p) = zahada' l . zahada' p

Zadaný strom odpovídal definici

strom = Vetev (Vetev (Vetev (List 3) (List 4)) (List 2)) (List 1)

Nekonečná DS byla zadaná jako

stromOd n = Vetev (List n) (stromOd (n+2))

a za úkol bylo určit, co vrátí take 5 (zahada (stromOd 1))

Moje řešení:

1. 1. Typ funkce zahada:

   zahada :: BStrom a -> [a]

   1. zahada strom vrátí seznam [3,4,2,1]

   2. zahada vrací seznam listů v průchodu zleva doprava (tedy preorder)

   3. hodnota funkce je [1,3,5,7,9]{: style="list-style-type:lower-alpha"}

2. prevod :: Integral a => a -> [a] -> a

   prevod _ [] = 0 prevod b (x:xs) = x*b^(length xs) + prevod b xs

   prevod b xs = foldl (\mezivysledek cislice -> mezivysledek*b + cislice) 0 xs

   prevod b xs = let delka' = length xs - 1 in sum [ x * (b^(delka'-n)) | n <- [0..delka'], let x = xs !! n]

{: style="list-style-type:lower-alpha"}

1. to jsem nestihl

2. data Strom a = Vetev a [Strom a]

   ekviv :: Eq a => Strom a -> Strom a -> Bool ekviv (Vetev a xs) (Vetev b ys) | a /= b = False | length xs /= length ys = False | otherwise = (not.null) [ps | ps <- permutace ys, ekviv' xs ps] whereekviv' xs ys = all ((x,y) -> ekviv x y) (zip xs ys)permutace [] = [[]]permutace xs = [(y:ps) | (y,ys) <- (vyber xs), ps <- permutace ys]wherevyber [x] = [(x,[])]vyber (prvni:zbytek) = (prvni,zbytek) : map ((x,xs)->(x,prvni:xs)) (vyber zbytek){- vyber xs vrátí seznam všech dvojic (x,xs'), kde x je jeden prvek xs a xs' jsou ostatní prvky -}

{: style="list-style-type:lower-alpha"} {: style="list-style-type:decimal"}

Mate nekdo uz vysledky ?

Návštěvník wrote:Mate nekdo uz vysledky ?

Dneska odpoledne se mi objevily v grupíčku, bohužel v součtu 57 bodů :-/

Ja tam mam nevyplneno :/

Návštěvník wrote:Ja tam mam nevyplneno :/

tiez sa mi tam objavil riadok pre Haskell ale zostal prazdny, aj ked som na pisomke bol... znamena to, ze este nemaju opravene vsetky pisomky, alebo mam radsej zacat spamovat Hrica s Dvorakom? ;)

Zdravim,
viem ze je uz trocha pozde, ale nemohol by niekto naznacit riesenie k trojke, snazim sa to spravit v ramci priprav na skusku ale jedine co viem spravit je ze si vygenerujem jednotlive n-tice ktore chcem zamenit. Na ich miesta vsak neviem nijak rozumne dosadit nove znaky.

Dik, za help

H8me wrote:Zdravim,
viem ze je uz trocha pozde, ale nemohol by niekto naznacit riesenie k trojke, snazim sa to spravit v ramci priprav na skusku ale jedine co viem spravit je ze si vygenerujem jednotlive n-tice ktore chcem zamenit. Na ich miesta vsak neviem nijak rozumne dosadit nove znaky.

Nevim, jestli moje řešení je ideální (ale musel jsem za něj mít minimálně 10 bodů), ale dělal jsem to rekurzivně, tak že výsledná (zatim neseřazená množina) byla sjednocení:

• první písmeno jsem ponechal a doobměnil k němu n písmen ze zbytku

• první písmeno jsem zaměnil postupně za ostatní písmena v abecedě a dogeneroval k tomu slova obměněná o n-1 písmen

Takže ta hlavní část vypadala zhruba takhle:

gen (x:xs) n = [x:y | y <- gen xs n] ++ [z:y | y <- gen xs (n-1) , z <- abeceda, x /= z]

K tomu je ještě potřeba nadefinovat dno rekurze a potom odřezat slepé větve (kdy je potřeba obměnit víc písmen než je délka slova).

No a nakonec jsem to celý seřadil, napsal jsem si vlastní quicksort, kterej respektoval pořadí abecedy, tak jak jí vracela funkce abeceda (možná to ani nebylo nutné, ale pro jistotu jsem to dělal).

Diky, tak ako vzdy to bolo ovela jednoduchsie ako som si myslel :]
Cela verzia ak by to niekoho zaujimalo vyzera:

gen s 0 = [s]
gen [] _ = []
gen (x:xs) n = [x:y | y <- gen xs n] ++ [z:y | y <- gen xs (n-1) , z <- abeceda, x /= z]