Matfyz Wiki
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ů.
-- 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]]