FP Laboratory 10/cs

Binární strom

• Vytvořte datový typ Tree, který definuje binární strom, kde jsou hodnoty uloženy v listech a také ve větvích.

data Tree a = Leaf a 
            | Branch a (Tree a) (Tree a) deriving (Show)

• Připravte si příklad binárního stromu.

testTree1 :: Tree Int            
testTree1 = Branch 12 (Branch 23 (Leaf 34) (Leaf 45)) (Leaf 55)

testTree2 :: Tree Char            
testTree2 = Branch 'a' (Branch 'b' (Leaf 'c') (Leaf 'd')) (Leaf 'e')

• Vytvořte funkci, která sečte všechny hodnoty uložené ve stromu celých čísel.

sum' :: Tree Int -> Int

sum' :: Tree Int -> Int
sum' (Leaf x) = x
sum' (Branch x l r) = sum' l + x + sum' r

• Vytvořte funkci, která extrahuje všechny hodnoty ze stromu do seznamu.

toList :: Tree a -> [a]

toList :: Tree a -> [a]
toList (Leaf x) = [x]
toList (Branch x l r) = toList l ++ [x] ++ toList r

• Vytvořte funkci, která najde maximální hodnotu uloženou ve stromu.

maxTree :: Ord a => Tree a -> a

maxTree :: Ord a => Tree a -> a
maxTree (Leaf x) = x
maxTree (Branch x l r) = maximum [x, maxTree l, maxTree r]

• Vytvořte funkci, která vrátí maximální hloubku stromu.

depthTree :: Tree a -> Int

depthTree :: Tree a -> Int
depthTree (Leaf x) = 1
depthTree (Branch x l r) = max (depthTree l) (depthTree r) + 1

• Vytvořte funkci, která vrátí jako seznam ty prvky seznamu, které jsou větší než zadaná hodnota.

getGreaterElements :: Ord a => Tree a -> a -> [a]

getGreaterElements :: Ord a => Tree a -> a -> [a]
getGreaterElements (Leaf x) y | x > y = [x]
                              | otherwise = []
getGreaterElements (Branch x l r) y | x > y = [x] ++  getGreaterElements l y ++ getGreaterElements r y 
                                    | otherwise = getGreaterElements l y ++ getGreaterElements r y

• Jednou z možností, jak reprezentovat strom v textové podobě, je a(b(d,e),c(e,f(g,h))). Vytvořte funkci, která bude schopna načíst a uložit strom z takového zápisu.

toString :: Show a => Tree a -> String
fromString :: Read a => String -> Tree a

toString :: Show a => Tree a -> String
toString (Leaf x) = show x
toString (Branch x l r) = show x ++ "(" ++ (toString l) ++ "," ++ (toString r) ++ ")"

fromString :: Read a => String -> Tree a
fromString inp = fst (fromString' inp) where
  fromString' :: Read a => String -> (Tree a,String)
  fromString' inp = 
    let
      before = takeWhile (\x ->  x /='(' &&  x /=',' &&  x/=')') inp 
      after = dropWhile (\x ->  x /='(' &&  x /=',' && x/=')') inp
      value = read before
    in if null after || head after /= '(' then (Leaf value, after) else 
        let
          (l,after') = fromString' (tail after)
          (r,after'') = fromString' (tail after') 
        in (Branch value l r, tail after'')

Doplňková cvičení

• Vytvořte funkci, která spočítá všechny listy ve stromu.

leafCount :: Tree a -> Int

• Vytvořte funkci, která spočítá všechny větve stromu.

branchCount :: Tree a -> Int

• Vytvoření funkce, která zkontroluje, zda je daný prvek uložen ve stromu.

contains :: Eq a => Tree a -> a -> Bool

• Vytvoření funkce, která vrátí počet prvků větší než zadaná hodnota.

greaterThan :: Ord a => Tree a -> a -> Int

• Uvažujme následující alternativní definici binárního stromu.

data Tree2 a = Null | Branch a (Tree2 a) (Tree2 a)

• Je tato definice ekvivalentní předchozí definici? Pokud ne, vysvětlete proč a uveďte příklad stromu, který lze zkonstruovat podle první definice, ale ne podle druhé, nebo naopak.

• Implementujte všechny výše uvedené funkce upravené pro alternativní definici binárního stromu.

Abstraktní datové typy

• Vytvořte implementaci abstraktního datového typu Stack s následujícími funkcemi:

push :: a -> Stack a -> Stack a
pop :: Stack a -> Stack a
top :: Stack a -> a
isEmpty :: Stack a ->Bool

module Stack(Stack, emptyS, push, pop, top, isEmpty) where
  data Stack a = Stack [a] deriving Show

  emptyS :: Stack a
  emptyS = Stack []

  push :: a -> Stack a -> Stack a
  push x (Stack y) = Stack (x:y)
  
  pop :: Stack a -> Stack a
  pop (Stack (_:xs)) = Stack xs

  top :: Stack a -> a
  top (Stack (x:_)) = x

  isEmpty :: Stack a ->Bool
  isEmpty (Stack []) = True
  isEmpty _ = False

• Vytvořte implementaci abstraktního datového typu Queue s následujícími funkcemi:

isEmpty :: Queue a -> Bool
addQ :: a -> Queue a -> Queue a
remQ :: Queue a -> (a, Queue a)

module Queue(Queue, emptyQ, isEmptyQ, addQ, remQ) where
    data Queue a = Qu [a] deriving Show

    emptyQ :: Queue a
    emptyQ = Qu []
    
    isEmptyQ :: Queue a -> Bool
    isEmptyQ (Qu q) = null q
    
    addQ :: a -> Queue a -> Queue a
    addQ x (Qu xs) = Qu (xs++[x])
    
    remQ :: Queue a -> (a,Queue a)
    remQ q@(Qu xs) | not (isEmptyQ q) = (head xs, Qu (tail xs))
                   | otherwise        = error "remQ"