Задание 2.1

Реализуйте структуру данных "бинарное дерево поиска" для целых чисел без балансировки. Реализация включает функции:

  • Добавления элемента: insert :: BinaryTree -> Integer -> BinaryTree
  • Удаления элемента: remove :: BinaryTree -> Integer -> BinaryTree
  • Создания пустого дерева: emptyTree :: BinaryTree
  • Поиска элемента в дереве: containsElement :: BinaryTree -> Integer -> Bool
  • Поиска в дереве наименьшего элемента, который больше или равен заданному: nearestGE :: BinaryTree -> Integer -> Integer
  • Создания дерева из списка: treeFromList :: [Integer] -> BinaryTree
  • Создания списка из дерева: listFromTree :: BinaryTree -> [Integer]

Операторы insert и remove должны поддерживать цепочки вызовов в инфиксной форме:

listFromTree (emptyTree `insert` 1 `insert` 2 `insert` 3) === [1,2,3]

Задание 2.2

  1. Реализуйте функции foldl и foldr из лекции
  2. На основе функций foldl и foldr реализуйте свои версии функций
    map :: (a -> b) -> [a] -> [b]
    flatMap :: (a -> [b]) -> [a] -> [b]
    concat :: [a] -> [a] -> [a]
    filter :: (a -> Boolean) -> [a] -> [a]
    maxBy :: (a -> Integer) -> [a] -> a
    minBy :: (a -> Integer) -> [a] -> a
    reverse :: [a] -> [a]
    elementAt :: Integer -> [a] -> a
    indexOf :: String -> [String] -> Integer