od jans » 29. 5. 2012 18:05
Zdravím,
dnešní zadání zkoušky bylo takovéto:
Prolog 1: Definovat predikát, který obdrží ohodnocení výrokových proměnných, tj. asociativní seznam a vrátí všechna ohodnocení těchto proměnných, která se liší alespoň ve dvou hodnotách.
Nástin řešení: vytáhnout si z předaného ohodnocení názvy proměnných, vygenerovat si všechna možná ohodnocení a z nich vyházet ta, která se od zadaného ohodnocení buď neliší nebo se liší právě v hodnotě jedné proměnné.
Prolog 2: Na vstupu máme orientovaný graf bez smyček a multihran. Graf je zadán jako seznam ve tvaru vrchol-hrany, kde hrany je seznam sousedů vrcholu. Dále máme zadán seznam ekvivalentních vrcholů a máme provést kontrakci těchto vrcholů do jednoho, tj. hrana povede z tohoto vrcholu do nějakého vrcholu mimo tento seznam pouze pokud vedla alespoň z jednoho vrcholu v tomto seznamu a naopak. Je třeba dát pozor, aby nevznikly smyčky a multihrany, případně je poté odstranit.
Haskell 3: Máme zadaný datový typ (Bag a = Item a | Items [a]) a typ funkce fold, která má tuto strukturu procházet. Máme definovat tuto funkci a poté ještě funkci listy, která vrátí seznam všech položek v Item a v této datové struktuře.
Haskell 4: Dostaneme číslo n a máme vygenerovat nekonečný seznam posloupností délky n, které jsou uspořádány maximo-lexikograficky, někde to tu již na fóru je, nicméně přikládám řešení těchto posledních dvou příkladů.
Kód: Vybrat vše
-- Zkouskovy priklad cislo 3:
data Bag a = Item a | Items [Bag a]
-- a) Definovat funkci fold pro obecny pruchod datovou strukturou.
fold :: (a -> b) -> ([b] -> b) -> Bag a -> b
fold func listFunc (Item x) = func x
fold func listFunc (Items xs) = listFunc [fold func listFunc bag | bag <- xs]
-- b) Definovat funkci listy, ktera vrati seznam polozek s datovymi konstruktory Item.
listy :: Bag a -> [a]
listy bag = fold makeList joinLists bag
makeList :: a -> [a]
makeList x = [x]
joinLists :: [[a]] -> [a]
joinLists [] = []
joinLists (x:xs) = x ++ joinLists xs
-- > listy (Items [Item 1, Item 2, Items [Item 3, Item 4], Item 5])
-- [1,2,3,4,5]
-------------------------------------------------------------------
-- Zkouskovy priklad cislo 4 - vygenerovat nekonecny seznam posloupnosti
-- delky n usporadanych v maximolexikografickem usporadani.
gen :: Int -> [[Int]]
gen n = genWithMax n 1
genWithMax :: Int -> Int -> [[Int]]
genWithMax n max = [xs | xs <- var n max, max `elem` xs] ++ genWithMax n (max + 1)
var :: Int -> Int -> [[Int]]
var 0 _ = [[]]
var k n = [x:xs | x <- [1..n], xs <- var (k - 1) n]
-- > take 10 (gen 2)
-- [[1,1],[1,2],[2,1],[2,2],[1,3],[2,3],[3,1],[3,2],[3,3],[1,4]]
Zdravím,
dnešní zadání zkoušky bylo takovéto:
[b]Prolog 1[/b]: Definovat predikát, který obdrží ohodnocení výrokových proměnných, tj. asociativní seznam a vrátí všechna ohodnocení těchto proměnných, která se liší alespoň ve dvou hodnotách.
Nástin řešení: vytáhnout si z předaného ohodnocení názvy proměnných, vygenerovat si všechna možná ohodnocení a z nich vyházet ta, která se od zadaného ohodnocení buď neliší nebo se liší právě v hodnotě jedné proměnné.
[b]Prolog 2[/b]: Na vstupu máme orientovaný graf bez smyček a multihran. Graf je zadán jako seznam ve tvaru vrchol-hrany, kde hrany je seznam sousedů vrcholu. Dále máme zadán seznam ekvivalentních vrcholů a máme provést kontrakci těchto vrcholů do jednoho, tj. hrana povede z tohoto vrcholu do nějakého vrcholu mimo tento seznam pouze pokud vedla alespoň z jednoho vrcholu v tomto seznamu a naopak. Je třeba dát pozor, aby nevznikly smyčky a multihrany, případně je poté odstranit.
[b]Haskell 3[/b]: Máme zadaný datový typ (Bag a = Item a | Items [a]) a typ funkce fold, která má tuto strukturu procházet. Máme definovat tuto funkci a poté ještě funkci listy, která vrátí seznam všech položek v Item a v této datové struktuře.
[b]Haskell 4[/b]: Dostaneme číslo n a máme vygenerovat nekonečný seznam posloupností délky n, které jsou uspořádány maximo-lexikograficky, někde to tu již na fóru je, nicméně přikládám řešení těchto posledních dvou příkladů.
[code]-- Zkouskovy priklad cislo 3:
data Bag a = Item a | Items [Bag a]
-- a) Definovat funkci fold pro obecny pruchod datovou strukturou.
fold :: (a -> b) -> ([b] -> b) -> Bag a -> b
fold func listFunc (Item x) = func x
fold func listFunc (Items xs) = listFunc [fold func listFunc bag | bag <- xs]
-- b) Definovat funkci listy, ktera vrati seznam polozek s datovymi konstruktory Item.
listy :: Bag a -> [a]
listy bag = fold makeList joinLists bag
makeList :: a -> [a]
makeList x = [x]
joinLists :: [[a]] -> [a]
joinLists [] = []
joinLists (x:xs) = x ++ joinLists xs
-- > listy (Items [Item 1, Item 2, Items [Item 3, Item 4], Item 5])
-- [1,2,3,4,5]
-------------------------------------------------------------------
-- Zkouskovy priklad cislo 4 - vygenerovat nekonecny seznam posloupnosti
-- delky n usporadanych v maximolexikografickem usporadani.
gen :: Int -> [[Int]]
gen n = genWithMax n 1
genWithMax :: Int -> Int -> [[Int]]
genWithMax n max = [xs | xs <- var n max, max `elem` xs] ++ genWithMax n (max + 1)
var :: Int -> Int -> [[Int]]
var 0 _ = [[]]
var k n = [x:xs | x <- [1..n], xs <- var (k - 1) n]
-- > take 10 (gen 2)
-- [[1,1],[1,2],[2,1],[2,2],[1,3],[2,3],[3,1],[3,2],[3,3],[1,4]]
[/code]