import Data.List

{- Дефиниция на типа Tree a описващ произволно двоично дърво. -}
data Tree a = Empty | Node a (Tree a) (Tree a)
    deriving (Read, Show)

-- помощна ф-я, връщаща стойностите на ниво k.
nodesAtLevel :: (Eq b, Num b) => Tree a -> b -> [a]
nodesAtLevel Empty _ = []
nodesAtLevel (Node x _ _) 0 = [x]
nodesAtLevel (Node _ left right) n = nodesAtLevel left (n - 1) ++ nodesAtLevel right (n - 1)


{-
Задача 1.
а). Напишете функцията distance f xys, която приема едноместна функция f
    и списък от двойки (x, y) и връща сбора от разстоянията |y - f(x)| между f(x)
    и y, за всички елементи от списъка (в случая |a| означава абсолютната стойност
    на числото а).

    Ще наричаме резултата на тази функция, разстояние на функцията f от xys.

Примери:
    distance (\x -> x ^ 2) [(1, 1), (2, 4), (3, 9), (4, 15)] = 1
    distance (\x -> x + 1) [(1, 1), (2, 4), (3, 9), (4, 15)] = 17

б). Напишете функцията closest fs xys, която приема списък от едноместни функции fs
    и списък от двойки xys и връща фукцията от fs, която е на най-малко разстояние от xys.

Примери:
    (closest [(\x -> x ^ 2), (\x -> x + 1)] [(1, 1), (2, 4), (3, 9), (4, 15)]) 5 = 25
-}
-- 1.а.
distance :: (Double -> Double) -> [(Double, Double)] -> Double
distance f xys = sum [abs(y - f x) | (x, y) <- xys]

-- 1.б.
closest' :: [(Double -> Double)] -> [(Double, Double)] -> (Double -> Double)
closest' fs xys = argmin (\f -> distance f xys) fs

argmin f xs = head [ x | x <- xs, f x == m] where
       m = minimum (map f xs)


closest :: [(Double -> Double)] -> [(Double, Double)] -> (Double -> Double)
closest [] _       = error "empty list"
closest [f] _      = f
closest (f:fs) xys =
  let
      mf = closest fs xys
  in
      if distance f xys < distance mf xys
        then f
        else mf

{-
Задача 2.
а). Дефинирайте типа Book, който има следните атрибути (компоненти): заглавие, година на
    издаване и брой продадени копия.
б). Дефинирайте "помощните" функции title, published и sales, който връщат съответно
    заглавието, годината на издаване и броя продадени копия на дадена книга.
в). Дефинирайте фукцията bestsellers books, която приема списък от книги и връща всички
    бестселъри (книги, който са били продадени в повече от 1 милион екземпляра).
г). Дефинирайте функцията newTitles books year, която приема списък от книги и година,
    и връща заглавията на тези от тях, които са издадени през дадената година.
-}
data Book = Book String Int Int
    deriving (Read, Show)

type Title = String
type Published = Year
type Year = Int
type CopiesSold = Int

title :: Book -> String
title (Book t _ _) = t

published :: Book -> Int
published (Book _ p _) = p

sales :: Book -> Int
sales (Book _ _ s) = s

bestsellers :: [Book] -> [Book]
bestsellers books = filter (\b -> sales b > 1000000) books

newTitles :: [Book] -> Int -> [String]
newTitles books year = [title b | b <- books, published b == year]


{-
Задача 3. Дефинирайте функциата treePaths tree, която връща всички пътища
от корена на дървото до листата му.
-}
treePaths :: Tree a -> [[a]]
treePaths Empty = []
treePaths (Node x Empty Empty) = [[x]]
treePaths (Node x left right) = [x:ps | ps <- treePaths left ++ treePaths right]

{-
Задача 4. Нека е дадено двоично дърво tree. Дефинирайте функцията
findMeanNodes tree, която връща списък с всички нодове на tree, чиято
стойност е равна на средното аритметично на родителя (ако има такъв)
и децата на дадения нод.
-}

avg xs = sum xs / fromIntegral(length xs)

children tree  = nodesAtLevel tree 1

findMeanNodes' :: (Eq a, Fractional a) => Tree a -> [a]
findMeanNodes' Empty = []
findMeanNodes' tree@(Node x left right)
   | x == avg (children tree) = x : meanChildren
   | otherwise                = meanChildren where
         meanChildren = helper x left ++ helper x right
         helper _ Empty = []
         helper parent node@(Node x left right)
           | x == avg (parent:children node) = x : meanChildren2
           | otherwise                       = meanChildren2 where
              meanChildren2 = helper x left ++ helper x right


findMeanNodes :: (Eq a, Fractional a) => Tree a -> [a]
findMeanNodes tree = helper tree (children tree) where
  helper Empty _ = []
  helper(Node x left right) nodes
    | null nodes     = []
    | x == avg nodes = x:meanChildren
    | otherwise      = meanChildren where
      meanChildren = helper left(x:children left) ++ helper right(x:children right)


{-
Задача 5. Да се дефинира функция findGrandpas tree, която за дадено двоично дърво от
естествени числа tree намира списък от всички числа - върхове на tree, които са равни на
сумата от внуците си. Напишете и примерни извиквания на дефинираната функция.
-}
findGrandpas :: (Eq a, Num a) => Tree a -> [a]
findGrandpas tree = undefined


-- примерни извиквания --
main :: IO()
main =
  let
    books = [
          Book "Gone with the Wind" 1936 35000000,
          Book "To Kill a Mockingbird" 1960 32000000,
          Book "Chocolate" 1999 995000]
    b = head books
    {-
    В примерите ще използваме следното дърво (tree):

                                  3
                                /   \
                               1     4
                              / \   / \
                             0   2     5
                            / \ / \   / \
                                         6
    -}
    tree = (Node 3 (Node 1 (Node 0 Empty Empty) (Node 2 Empty Empty)) (Node 4 Empty (Node 5 Empty (Node 6 Empty Empty))))
  in do
    -- Задача 1.
    print $ distance (\x -> x ^ 2) [(1, 1), (2, 4), (3, 9), (4, 15)]
    print $ distance (\x -> x + 1) [(1, 1), (2, 4), (3, 9), (4, 15)]
    print $ closest [(\x -> x ^ 2), (\x -> x + 1)] [(1, 1), (2, 4), (3, 9), (4, 15)] 5

    -- Задача 2.
    print $ b
    print $ title $ b
    print $ published $ b
    print $ sales $ b
    print $ bestsellers books
    print $ newTitles books 1999

    -- Задача 3.
    print $ treePaths tree

    -- Задача 4.
    print $ findMeanNodes Empty
    print $ findMeanNodes tree
    print $ findMeanNodes (Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty))

    -- Задача 5.
    print $ findGrandpas Empty
    print $ findGrandpas tree