Функционално програмиране (И) 2018/2019

Зад.1. Да се напише функция maxSumPath, която приема за аргумент двоично дърво с числа във възлите и намира максималната сума на числата по някой път от корен до листо.

Зад.2. Да се напише функция prune, която по дадено двоично дърво t връща ново дърво t', което представлява t, в което всички листа са премахнати.

Зад.3. Да се напише функция bloom, която по дадено двоично дърво t връща ново дърво t', което представлява t, в което на всички листа са добавени по два наследника - нови листа. Стойността в тези нови листа да е същата, като в оригиналното листо, от което са излезли.

Зад.4. Да се имплементират стандартните ротации на двоични дървета:

Зад.5. Да се напише функция treeМap, която map-ва дадена функция f на всички стойности в дадено дърво (тук не е задължително стойностите в дървото да са числа).

Зад.5*. Да се инстанцира класа от типове Functor за даден тип дърво с произволен брой наследници на всеки възел.

Зад.6. Да се дефинира тип BST, който да представлява двоично наредено дърво, съдържащо стойности от произволен тип във възлите си. Да се дефинират следните функции към него:
- bstInsert :: Ord a => a -> BST a -> BST a - добавяне на стойност в дървото
- bstSearch :: Ord a => a -> BST a -> Bool  - търсене на стойност в дървото
- bstValues :: BST a -> [a]                 - получаване на списък със всички стойности в дървото
- bstSize :: BST a -> Int                   - брой стойности, съдържани в дървото
- bstSort :: Ord a => [a] -> [a]            - сортиране, използвайки ДНД като междинна структура

Зад.7. Да се дефинира тип Map, който да представлява структурата от данни асоциативен списък, реализирана с двоично наредено дърво. Да се дефинират следните функции към нея:
- mapInsert :: Ord k => k -> v -> Map k v -> Map k v -- вмъкване на ключ със стойност в дървото. Ако стойност за този ключ съществува, нека тя да бъде заместена с новата.
- mapSearch :: Ord k => k -> Map k v -> Maybe v      -- търсене на стойност по ключ в дървото (обърнете внимание на върнатия тип)

Зад.8*. Да се дефинира тип Direction, който да символизира посока при търсене в двоично наредено дърво (ляво или дясно). Да се дефинира функция bstPath :: Ord a => a -> BST a => ???, която по даден елемент и двоично наредено дърво намира пътека (последователност от посоки) до елемента в дървото.

Упътване: какъв трябва да е типът на резултата?

Зад.9. Да се дефинира тип Expr, който да представлява математически израз - функция на един аргумент. Освен този аргумент, този израз може да съдържа само числа (Double), или следните операции: събиране, изваждане, умножение, деление или степенуване* на два израза. Да се дефинират следните функции към него:
- eval :: Expr -> Double -> Double -- изчислява стойността на функцията по дадена стойност на аргумента ѝ
- derive :: Expr -> Expr           -- изчислява производната на дадена функция
Производната на дадена функция е също функция, която искаме да можем отново да диференцираме или оценяваме точно.

* за улеснение ще позволяваме само повдигане на израз на степен число, както и число на степен израз. Това значи, че няма да можем да представяме функции като xx, (1+2)x или x(3+5)

Зад.10. Да се дефинира тип Currency, който да символизира точно една измежду валутите лев, долар, евро и виетнамски донги. Да се дефинира тип "сума", която съдържа число и валута. Напишете функция exchange, която конвертира дадена сума в друга валута (получавайки отново сума)