Exercises week 4

[ichko]

Тук може да споделяте решенията си на задачите от седмица 4. Самите задачи са дефинирани тук, а тук може да намерите нашите решения.

Публикувайте решенията като коментари в това issue или като линкове към ваши хранилища/gist.
Заградете кода на решението си по следния начин за да се highlight-не правилно (ако поствате коментар с кода тук):

```hs
-- solution
```

[dimitroffangel]

quicksort [] = []
quicksort (xHead : xTail) = 
    quicksort lesser ++ (xHead : quicksort greater)
    where 
        lesser = filter (< xHead) xTail
        greater = filter (>= xHead) xTail 

createIthElementList (head: tail) index result
    | null tail = result ++ [head !! index]
    | otherwise = createIthElementList tail index (result ++ [ head !! index ])

assertElementLength [] = False
assertElementLength list = 
    assertElementLengthHelper list 0 (length (head list))
    where
        assertElementLengthHelper list index currentLength 
            |index == length list = True
            |length (list !! index) /= currentLength = False
            |otherwise = assertElementLengthHelper list (index + 1) currentLength

transposeList list = 
    transposeListHelper list 0 []
    where 
        transposeListHelper list index result
            | not (assertElementLength list) = []
            | index == length (head list) = result
            | otherwise = transposeListHelper list (index + 1) (result ++ [createIthElementList list index []])


data Vector a = Vector a a a deriving (Show, Read, Eq)

vec = Vector 

zeroVec = vec 0 0 0

instance (Num a) => Num (Vector a) where
    Vector x1 y1 z1 + Vector x2 y2 z2 = Vector (x1 + x2) (y1 + y2) (z1 + z2)
    Vector x1 y1 z1 * Vector x2 y2 z2 = Vector (x1 * x2) (y1 * y2) (z1 * z2)
    negate (Vector x1 y1 z1) = Vector (-x1) (-y1) (-z1)
    abs (Vector x y z) = Vector (abs x) (abs y) (abs z)
    signum (Vector x y z) = Vector (signum x) (signum y) (signum z)
    fromInteger i = Vector (fromInteger i) (fromInteger i) (fromInteger i)
    
productRowColVector _ [] result = result
productRowColVector currentRow (currentCol : restOfCols) result 
    = productRowColVector currentRow restOfCols $ sum (zipWith (*) currentRow currentCol) : result

    
multiply lhsMatrix rhsMatrix = 
    reverse $ multiplyHelper lhsMatrix listOfColsRhsMatrix []
        where 
            listOfColsRhsMatrix = transposeList rhsMatrix
            multiplyHelper [] _ result = result
            multiplyHelper (currentRowLHS : restOfRowsLHS) listOfColsRhsMatrix result =
                multiplyHelper restOfRowsLHS listOfColsRhsMatrix 
                   $ reverse (productRowColVector currentRowLHS listOfColsRhsMatrix []) : result
    
                   
data KV key value = KV [(key, value)]
fooTest = KV [('a', 5)]

type Histogram = KV Char Integer

makeHistogram list = 
    reverse $ histrogramHelper sortedSymbols (head sortedSymbols, 0) [] 
        where 
            sortedSymbols = quicksort list
            histrogramHelper [] (savedSymbol, occurenceOfSavedSymbol) result = 
                (savedSymbol, occurenceOfSavedSymbol) : result
            histrogramHelper (currentSymbol : restOfSymbols) (savedSymbol, occurenceOfSavedSymbol) result 
                | currentSymbol == savedSymbol = 
                    histrogramHelper restOfSymbols (savedSymbol, occurenceOfSavedSymbol + 1) result
                | otherwise = histrogramHelper restOfSymbols (currentSymbol, 1) 
                   $ (savedSymbol, occurenceOfSavedSymbol) : result


fooHist = makeHistogram ['a', 'b', 'c', 'a', 'a', 'c','d']                   
plotHistogram :: (Num b, Ord b) => [(Char, b)] -> [Char]
plotHistogram histogram = 
    plotHistogramHelper histogram (findMaxOccurence histogram (snd (head histogram))) []
    where 
        findMaxOccurence [] currentMax = currentMax
        findMaxOccurence (currentElement : restOfElements) currentMax 
            | snd currentElement > currentMax = findMaxOccurence restOfElements $ snd currentElement
            | otherwise = findMaxOccurence restOfElements currentMax    

        drawHistogramStatsSymbols [] result = result 
        drawHistogramStatsSymbols (currentSymbolStat : restOfSymbolsStats) result = 
            drawHistogramStatsSymbols restOfSymbolsStats (result ++ [fst currentSymbolStat])
        drawEmptyRow histogram = 
            concat ["=" | x<- [1.. length histogram]] ++ "\n" ++ drawHistogramStatsSymbols histogram []
        drawSymbol [] _ result = result
        drawSymbol (currentSymbolStat : restOfSymbolsStats) currentLevel result 
            | snd currentSymbolStat >= currentLevel =  
                drawSymbol restOfSymbolsStats currentLevel (result ++ "#")
            | otherwise = drawSymbol restOfSymbolsStats currentLevel result ++ " "
        plotHistogramHelper histogram 0 result = result ++ drawEmptyRow histogram ++ "\n" 
        plotHistogramHelper histogram currentLevel result = 
            plotHistogramHelper histogram (currentLevel - 1) 
                $ result ++ drawSymbol histogram currentLevel [] ++ "\n" 


data BinaryTree a = EmptyTree
    | Node a (BinaryTree a) (BinaryTree a)

foo = EmptyTree
foo2 = Node 1 
            (Node 2 
                (Node 4 EmptyTree EmptyTree)
                EmptyTree
            )
            (Node 3
                (Node 5 (Node 7 EmptyTree EmptyTree) EmptyTree)
                (Node 6 EmptyTree EmptyTree)
            )

insertBST element EmptyTree = Node element EmptyTree EmptyTree
insertBST element (Node currentNode leftTree rightTree) 
    |  element <= currentNode = Node currentNode (insertBST element leftTree) rightTree
    | otherwise = Node currentNode leftTree (insertBST element rightTree)

elementBST element EmptyTree = False
elementBST element (Node currentNode leftTree rightTree) 
    | element == currentNode = True
    | element > currentNode = elementBST element rightTree
    | element < currentNode = elementBST element leftTree


printFoo binaryTree = 
    printFooHelper binaryTree 0
        where
            printTabs 0 result = result
            printTabs numberOfTabs result = printTabs (numberOfTabs - 1) ('\t' : result) 
            printFooHelper EmptyTree depth = printTabs depth [] ++  "|-x"
            printFooHelper (Node currentNode leftTree rightTree) depth = 
                printTabs depth [] ++ "|" ++
                    show currentNode ++ "\n" ++ 
                    printFooHelper leftTree (depth + 1) ++ "\n" ++ 
                    printFooHelper rightTree (depth + 1)


instance (Show a) => Show (BinaryTree a) where
    show = printFoo

[Ivaylo-Valentinov]

import Data.List (transpose)

data Vector a = Vector a a a
  deriving (Show)

instance Num a => Num (Vector a) where
  (+) (Vector a1 b1 c1) (Vector a2 b2 c2) = Vector (a1 + a2) (b1 + b2) (c1 + c2)
  (-) (Vector a1 b1 c1) (Vector a2 b2 c2) = Vector (a1 - a2) (b1 - b2) (c1 - c2)
  (*) (Vector a1 b1 c1) (Vector a2 b2 c2) = Vector (a1 * a2) (b1 * b2) (c1 * c2)
  abs (Vector a b c) = Vector (abs a) (abs b) (abs c)
  signum (Vector a b c) = Vector (signum a) (signum b) (signum c)
  fromInteger int = Vector (fromInteger int) (fromInteger int) (fromInteger int)

calcRow :: Num a => [a] -> [[a]] -> [a]
calcRow row matrix2 = [sum $ zipWith (*) row matrixRow | matrixRow <- matrix2]

myMatrixMult :: Num a => [[a]] -> [[a]] -> [[a]]
myMatrixMult [] _ = []
myMatrixMult a b = [calcRow row b | row <- a]

multiply :: Num a => [[a]] -> [[a]] -> [[a]]
multiply a b = myMatrixMult a $ transpose b

data Histogram a = Histogram [(a, Integer)]
  deriving (Show)

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x : xs) =
  let smallerSorted = quicksort [a | a <- xs, a <= x]
      biggerSorted = quicksort [a | a <- xs, a > x]
   in smallerSorted ++ [x] ++ biggerSorted

contains :: Ord a => a -> [a] -> Bool
contains el list = (fromIntegral $ length $ filter (\x -> x == el) list) > 0

getDistinctElements :: Ord a => [a] -> [a] -> [a]
getDistinctElements [] res = res
getDistinctElements (h : t) res =
  if not $ contains h res
    then getDistinctElements t (h : res)
    else getDistinctElements t res

histogram :: Ord a => [a] -> Histogram a
histogram l = Histogram [(a, (fromIntegral $ length $ filter (\x -> x == a) l)) | a <- quicksort $ getDistinctElements l []]

getMaxFromHist (Histogram []) res = res
getMaxFromHist (Histogram ((_, num) : t)) res
  | num > res = getMaxFromHist (Histogram t) num
  | otherwise = getMaxFromHist (Histogram t) res

remove' [] res = res
remove' (h : t) res
  | h == '\'' = remove' t res
  | otherwise = remove' t (res ++ [h])

getlistFromHist (Histogram []) res = res ++ "\n"
getlistFromHist (Histogram ((a, _) : t)) res = getlistFromHist (Histogram t) (res ++ (remove' (show a) "") ++ " ")

plotHistogram h = putStr $ iter (getMaxFromHist h 0) ""
  where
    iter last res
      | last == -1 = res ++ (getlistFromHist h "")
      | otherwise = iter (last - 1) (res ++ getRowUsingNumAndHis last h "")
      where
        getRowUsingNumAndHis _ (Histogram []) res = (res ++ "\n")
        getRowUsingNumAndHis el (Histogram ((_, num) : t)) res
          | el == 0 = getRowUsingNumAndHis el (Histogram t) (res ++ "==")
          | num >= el = getRowUsingNumAndHis el (Histogram t) (res ++ "# ")
          | otherwise = getRowUsingNumAndHis el (Histogram t) (res ++ "  ")

data BinTree a = BinTree a (BinTree a) (BinTree a) | EmptyTree

insertBST :: Ord a => a -> BinTree a -> BinTree a
insertBST el EmptyTree = BinTree el EmptyTree EmptyTree
insertBST el t@(BinTree root left right)
  | el == root = t
  | el > root = BinTree root left (insertBST el right)
  | otherwise = BinTree root (insertBST el left) right

elemBST :: Ord t => t -> BinTree t -> Bool
elemBST _ EmptyTree = False
elemBST el (BinTree root left right)
  | el == root = True
  | el > root = elemBST el right
  | otherwise = elemBST el left